Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Социальные группы Поиск Сообщения за день Заказать работу  
 
Рейтинг 4.90/29: Рейтинг темы: голосов - 29, средняя оценка - 4.90
1458 / 795 / 257
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
1

Реализация примитивного STL совместимого контейнера

20.12.2013, 00:07. Показов 5555. Ответов 7
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Как то застрял на этом. Как правильно объявить все typedef для итератора? Нужен минимальный набросок такого контейнера.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

template<typename T>
class array
{
   T* data;
   size_t size;
public:
   stuct iterator : public std::iterator
   {
      //???
   };
 
   typedef  T                                      value_type;
   typedef  std::size_t                            size_type;
   typedef  std::ptrdiff_t                         difference_type;
   typedef  value_type&                            reference;
   typedef  const value_type&                      const_reference;
   typedef  value_type*                            pointer;
   typedef  const value_type*                      const_pointer;
   typedef  iterator                               iterator;
   typedef  std::reverse_iterator<iterator>        reverse_iterator;
   typedef  std::reverse_iterator<const_iterator>  const_reverse_iterator;
 
   explicit array(size_t size_, T value_ = T()) : size(size_), data(new data[size_])
   {
      for (size_t i = 0; i < size; ++i) { data[i] = value_; }
   }
 
   ~array() { delete data[]; }
 
   iterator begin();
   const_iterator begin() const;
   const_iterator cbegin() const;
 
   iterator end();
   const_iterator end() const;
   const_iterator cend() const;
};
Добавлено через 6 часов 12 минут
Поправил код на это:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include <iostream>
#include <iterator>
#include <algorithm>
 
template<typename T>
struct Iter //: public std::iterator<std::random_access_iterator_tag, T>
{
private:
   T* p;
public:
   typedef T value_type;
   typedef T* pointer;
   typedef T& reference;
   typedef std::random_access_iterator_tag iterator_category;
   typedef ptrdiff_t difference_type;
 
 
   Iter() : p(nullptr) {}
   Iter(pointer p_) : p(p_) {}
   Iter(const Iter& other) :p(other.p) {}
   Iter& operator =(const Iter& other)
   {
      if (this != &other)
         p = other.p;
      return *this;
   }
 
   Iter& operator ++()
   {
      ++p;
      return *this;
   }
 
   Iter  operator ++(int)
   {
      Iter tmp(*this);
      operator ++();
      return tmp;
   }
 
   reference operator *() { return *p; }
   pointer operator ->() { return p; }
 
   bool operator ==(const Iter& other) { return p == other.p; }
   bool operator !=(const Iter& other) { return !(*this == other); }
 
   difference_type operator -(const Iter& value) const {
      return p - value.p;
   }
};
 
template<typename T>
class array
{
   T* data;
   size_t size;
public:
   typedef  T                                      value_type;
   typedef  std::size_t                            size_type;
   typedef  std::ptrdiff_t                         difference_type;
   typedef  value_type&                            reference;
   typedef  const value_type&                      const_reference;
   typedef  value_type*                            pointer;
   typedef  const value_type*                      const_pointer;
 
   typedef  Iter<T>                                iterator;
   typedef  const Iter<T>                          const_iterator;
   typedef  std::reverse_iterator<iterator>        reverse_iterator;
   typedef  std::reverse_iterator<const_iterator>  const_reverse_iterator;
 
   explicit array(size_t size_, T value_ = T()) : data(new T[size_]), size(size_)
   {
      for (size_t i = 0; i < size; ++i) { data[i] = value_; }
   }
 
   ~array() { delete[] data; }
 
   iterator begin() {return iterator(data);}
   iterator end() {return iterator(data+size);}
};
 
int main()
{
   array<int> ar(10, 5);
 
   std::copy(ar.begin(), ar.end(), std::ostream_iterator<int>(std::cout, " "));
   return 0;
}
Если же унаследовать Iter от std::iterator и комментировать тайпдефы, то не работает. Я же хочу наследованием сделать. Почему так?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 20.12.2013, 00:07
Ответы с готовыми решениями:

Реализация STL-совместимого списка
Как известно (курим Мейерса), в STL для класса list обычно выбирается O(1) время работы метода...

Из STL контейнера
Из STL контейнера создать 3-х мерный массив и класс который содержит этот 3-х мерный массив и вывод...

Выбор контейнера в STL
Здраствуйте! Нужно выбрать к этой задаче контейнер STL, который более выгодно подойдет, кроме...

Обработка STL контейнера vector
Текст дан в виде вектора. Отсортировать элементы этого вектора и превратить на два списка так,...

7
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
20.12.2013, 01:12 2
не работает - это не компилится или в рантайме ошибки?
для студии добавил operator <,
для вот этого: http://www.compileonline.com/c... online.php
добавил #include <cstddef> и nullptr заменил на 0 (хз как там в новый стандарт переключиться).
в результате компилится и печатает пятерки:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstddef>
 
template<typename T>
struct Iter : public std::iterator<std::random_access_iterator_tag, T>
{
private:
   T* p;
public:
   typedef T value_type;
   typedef T* pointer;
   typedef T& reference;
   typedef std::random_access_iterator_tag iterator_category;
   typedef ptrdiff_t difference_type;
 
 
   Iter() : p(0) {}
   Iter(pointer p_) : p(p_) {}
   Iter(const Iter& other) :p(other.p) {}
   Iter& operator =(const Iter& other)
   {
      if (this != &other)
         p = other.p;
      return *this;
   }
 
   Iter& operator ++()
   {
      ++p;
      return *this;
   }
 
   Iter  operator ++(int)
   {
      Iter tmp(*this);
      operator ++();
      return tmp;
   }
 
   reference operator *() { return *p; }
   pointer operator ->() { return p; }
 
   bool operator ==(const Iter& other) const { return p == other.p; }
   bool operator !=(const Iter& other) const { return !(*this == other); }
 
   difference_type operator -(const Iter& value) const {
      return p - value.p;
   }
 
   bool operator < (const Iter& other) const { return false; }
};
 
template<typename T>
class array
{
   T* data;
   size_t size;
public:
   typedef  T                                      value_type;
   typedef  std::size_t                            size_type;
   typedef  std::ptrdiff_t                         difference_type;
   typedef  value_type&                            reference;
   typedef  const value_type&                      const_reference;
   typedef  value_type*                            pointer;
   typedef  const value_type*                      const_pointer;
 
   typedef  Iter<T>                                iterator;
   typedef  const Iter<T>                          const_iterator;
   typedef  std::reverse_iterator<iterator>        reverse_iterator;
   typedef  std::reverse_iterator<const_iterator>  const_reverse_iterator;
 
   explicit array(size_t size_, T value_ = T()) : data(new T[size_]), size(size_)
   {
      for (size_t i = 0; i < size; ++i) { data[i] = value_; }
   }
 
   ~array() { delete[] data; }
 
   iterator begin() {return iterator(data);}
   iterator end() {return iterator(data+size);}
};
 
int main()
{
   array<int> ar(10, 5);
 
   std::copy(ar.begin(), ar.end(), std::ostream_iterator<int>(std::cout, " "));
   return 0;
}
1
Неэпический
17869 / 10634 / 2054
Регистрация: 27.09.2012
Сообщений: 26,736
Записей в блоге: 1
20.12.2013, 01:26 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

template<typename T>
struct Iter : public std::iterator<std::random_access_iterator_tag, T>
{
private:
   T* p;
   typedef std::iterator<std::random_access_iterator_tag, T> base_template ;
public:
   typedef typename base_template::value_type           value_type;
   typedef typename base_template::pointer              pointer;
   typedef typename base_template::reference            reference;
   typedef typename base_template::iterator_category    iterator_category;
   typedef typename base_template::difference_type      difference_type;
 
 
   Iter() : p(nullptr) {}
   Iter(pointer p_) : p(p_) {}
   Iter(const Iter& other) :p(other.p) {}
   Iter& operator =(const Iter& other)
   {
      if (this != &other)
         p = other.p;
      return *this;
   }
 
   Iter& operator ++()
   {
      ++p;
      return *this;
   }
 
   Iter  operator ++(int)
   {
      Iter tmp(*this);
      operator ++();
      return tmp;
   }
 
   reference operator *() { return *p; }
   pointer operator ->() { return p; }
 
   bool operator ==(const Iter& other) { return p == other.p; }
   bool operator !=(const Iter& other) { return !(*this == other); }
 
   difference_type operator -(const Iter& value) const {
      return p - value.p;
   }
};
1
1458 / 795 / 257
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
20.12.2013, 12:05  [ТС] 4
Почему тогда в шаблонах надо снова переопределять унаследованные тайпдефы?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <iterator>
 
struct A : std::iterator<std::random_access_iterator_tag, int>
{
   value_type foo() {value_type t = 100; return t;} // Good
};
 
template<typename T>
struct B : std::iterator<std::random_access_iterator_tag, T>
{
   typedef std::iterator<std::random_access_iterator_tag, T> base_template;
   typedef typename base_template::value_type value_type;
 
   value_type foo() {value_type t = 200; return t;} // Good
};
 
template<typename T>
struct C : std::iterator<std::random_access_iterator_tag, T>
{
   value_type foo() {value_type t = 300; return t;} // Error
};
 
int main()
{
   A a;
   std::cout << a.foo() << "\n";
   B<int> b;
   std::cout << b.foo() << "\n";
   C<int> C;
   std::cout << c.foo() << "\n";
 
   return 0;
}
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
20.12.2013, 14:24 5
MyIterator.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#ifndef _MYITERATOR_H_
#define _MYITERATOR_H_
#include <iterator>
 
template <typename T>
class MyIterator
{
public:
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef std::forward_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;
 
    // конструкторы
    MyIterator();
    MyIterator(T *);
    MyIterator(const MyIterator &);
    // оператор присваиваний
    MyIterator& operator =(const MyIterator &);
 
    // сдвиги операторов
    MyIterator& operator ++();    // префиксный инкремент
    MyIterator  operator ++(int); // постфиксная инкремент
 
    // операторы обращения
    T& operator *();
    T* operator ->();
 
    // операторы сравнения
    bool operator ==(const MyIterator &);
    bool operator !=(const MyIterator &);
 
private:
    T* current;
};
 
 
template <typename T>
MyIterator<T>::MyIterator() : current(0)
{}
 
template <typename T>
MyIterator<T>::MyIterator(T* curr) : current(curr)
{}
 
template <typename T>
MyIterator<T>::MyIterator(const MyIterator& other) : current(other.current)
{}
 
template <typename T>
MyIterator<T>& MyIterator<T>::operator =(const MyIterator& other)
{
    // исключаем присваивание самому себе
    if (this != &other)
        current = other.current;
 
    return *this;
}
 
//префиксная версия возвращает значение после инкремента
template <typename T>
MyIterator<T>& MyIterator<T>::operator ++()
{
    ++current;
    return *this;
}
 
//постфиксная версия возвращает значение до инкремента
template <typename T>
MyIterator<T> MyIterator<T>::operator ++(int)
{
    MyIterator tmp(*this);
    operator++();
    return tmp;
}
 
template <typename T>
T& MyIterator<T>::operator *()
{
    return *current;
}
 
template <typename T>
T* MyIterator<T>::operator ->()
{
    return current;
}
 
template <typename T>
bool MyIterator<T>::operator ==(const MyIterator &other)
{
    return current == other.current;
}
 
template <typename T>
bool MyIterator<T>::operator !=(const MyIterator &other)
{
    return !(*this == other);
}
 
#endif
Array.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

#ifndef _ARRAY_H_
#define _ARRAY_H_
#include <cstddef>
#include <algorithm>
#include <stdexcept>
#include "MyIterator.h"
 
template <typename T>
class Array
{
public:
    typedef MyIterator<T> iterator;
    typedef const MyIterator<T> const_iterator;
    typedef size_t size_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
 
    // конструкторы
    Array();
    Array(const size_t size);
    Array(const Array &);
    // оператор присвоений
    Array& operator =(const Array &);
    // деструктор
    ~Array();
 
    // итераторы начала и конца контейнера
    MyIterator<T> begin() const;
    MyIterator<T> end() const;
 
    // операторы доступа
    T& operator [](size_t );
    const T& operator [](size_t ) const;
 
    // прочие методы
    size_t size() const;
    bool empty() const;
 
private:
    void swap(Array &, Array &);
    T* arr_;
    size_t sz_;
};
 
 
 
template <typename T>
Array<T>::Array() : arr_(new T[0]), sz_(0)
{}
 
template <typename T>
Array<T>::Array(const size_t sz) : arr_(new T[sz]), sz_(sz)
{
    // вызываем конструкторы для каждого элемента
    std::fill(arr_, arr_ + sz_, T());
}
 
template <typename T>
Array<T>::Array(const Array& arr)
{
    sz_ = arr.sz;
    arr_ = new T[sz_];
    // копируем элементы в новый контейнер
    std::copy(arr.arr_, arr.arr_ + sz_, arr_);
}
 
template <typename T>
Array<T>& Array<T>::operator =(const Array& arr)
{
    // исключаем работу при присваивании самому себе
    if (this != &arr)
    {
        Array tmp(arr);
        swap(tmp);
    }
    return *this;
}
 
template <typename T>
Array<T>::~Array()
{
    delete[] arr_;
}
 
template <typename T>
MyIterator<T> Array<T>::begin() const
{
    return MyIterator<T>(arr_);
}
 
template <typename T>
MyIterator<T> Array<T>::end() const
{
    return MyIterator<T>(arr_ + sz_);
}
 
template <typename T>
T& Array<T>::operator [](size_t index)
{
    if (index >= sz_)
        throw std::out_of_range("Array subscript out of range");
    return arr_[index];
}
 
template <typename T>
const T& Array<T>::operator [](size_t index) const
{
    if (index >= sz_)
        throw std::out_of_range("Array subscript out of range");
    return arr_[index];
}
 
template <typename T>
size_t Array<T>::size() const
{
    return sz_;
}
 
template <typename T>
bool Array<T>::empty() const
{
    return sz_ == 0;
}
 
template <typename T>
void Array<T>::swap(Array& first, Array& second)
{
    std::swap(first.arr_, second.arr_);
    std::swap(first.sz_, second.sz_);
}
 
#endif
1
1458 / 795 / 257
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
20.12.2013, 14:40  [ТС] 6
MrGluck, я больше спрашивал про наследование. Вот как в книге написано:
Мюссер Д., Дердж Ж., Сейни А. - C++ и STL. Справочное руководство. 2-е издание
20.6.1. Базовый класс iterator
Для упрощения определения типов, требуемых iterator_traits, библиотека
предоставляет шаблон класса с необходимыми определениями. Класс итератора может
использовать iterator в качестве базового класса для автоматической генерации
необходимых определений.
В шаблоне как то не получается автоматическая генерация необходимых определений - надо ж вручную все типы переопределять. Получается, лучше вообще не наследовать от std::iterator
0
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
21.12.2013, 14:49 7
от итератора наследоваться все же полезно. Croessmah показал как лучше тайпдефить нужные типы.
по поводу того, почему это нужно тайпдефить:
возможно описание этого дела есть в главе 9.4 Наследование и шаблоны классов вот такой книги:
Дэвид Вандевурд, Николай М. Джосаттис Шаблоны C++: справочник разработчика = C++ Templates: The Complete Guide. — М.: «Вильямс», 2003. — С. 544. — ISBN 0-201-73484-2
ссылка с картинкой: http://www.williamspublishing.... 513-3.html

Попробовал унаследоваться вот от такого std::iterator<std::random_access_iterator_tag, int> - все скомпилилось без перетайпдефов. тут наследование
от конкретного класса и все имена в нем вполне однозначные.

В общем там всякие зависимые от аргумента шаблона имена и т.д. и т.п. Лучше найти и почитать.
0
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
21.12.2013, 15:05 8
Пользовательский итератор наследует типы из std::iterator, тут всё в порядке. Но если самому шаблону контейнера надо вынуть их из итератора, следует пользоваться typename.

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iterator>
 
template<typename T>
struct MyIt: public std::iterator<std::random_access_iterator_tag, T>{};
 
template<typename T>
struct MyCon{
  typedef MyIt<T> It;
  typedef typename It::value_type value_type;
};
 
int main()
{
    MyCon<int>::value_type x = 0;
    MyIt<int>::value_type y = 0;
}
0
21.12.2013, 15:05
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 21.12.2013, 15:05
Помогаю со студенческими работами здесь

Возврат контейнера STL из функции
Как правильно вернуть STL контейнер из функции НЕ ПО ЗНАЧЕНИЮ? std :: map&lt;std :: string,...

Адаптация контейнера под STL
Учу C++, на данный момент было задание: реализовать односвязный список. Пока что реализовано не...

Алгоритм выбора контейнера STL
Привет. Существует ли некая таблица по таким контейнерам с кратким описанием плюсов и минусов...

STL итератор на конец контейнера
Подскажите пожалуйста у меня задача сделать дерево и слизать интерфейс с STL std::map. Вопрос в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru