Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
20.12.2013, 00:07     Реализация примитивного STL совместимого контейнера #1
Как то застрял на этом. Как правильно объявить все 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 и комментировать тайпдефы, то не работает. Я же хочу наследованием сделать. Почему так?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2013, 00:07     Реализация примитивного STL совместимого контейнера
Посмотрите здесь:

C++ Структура, с использованием контейнера библиотеки STL
C++ Копирование контейнера vector в конструкторе (STL)
C++ Шаблонная функция вывода для любого stl контейнера
Из STL контейнера C++
Реализация STL-совместимого списка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
20.12.2013, 01:12     Реализация примитивного STL совместимого контейнера #2
не работает - это не компилится или в рантайме ошибки?
для студии добавил operator <,
для вот этого: http://www.compileonline.com/compile_cpp_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;
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11828 / 6807 / 769
Регистрация: 27.09.2012
Сообщений: 16,878
Записей в блоге: 2
Завершенные тесты: 1
20.12.2013, 01:26     Реализация примитивного STL совместимого контейнера #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;
   }
};
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
20.12.2013, 12:05  [ТС]     Реализация примитивного STL совместимого контейнера #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;
}
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,416
20.12.2013, 14:24     Реализация примитивного STL совместимого контейнера #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
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
20.12.2013, 14:40  [ТС]     Реализация примитивного STL совместимого контейнера #6
MrGluck, я больше спрашивал про наследование. Вот как в книге написано:
Мюссер Д., Дердж Ж., Сейни А. - C++ и STL. Справочное руководство. 2-е издание
20.6.1. Базовый класс iterator
Для упрощения определения типов, требуемых iterator_traits, библиотека
предоставляет шаблон класса с необходимыми определениями. Класс итератора может
использовать iterator в качестве базового класса для автоматической генерации
необходимых определений.
В шаблоне как то не получается автоматическая генерация необходимых определений - надо ж вручную все типы переопределять. Получается, лучше вообще не наследовать от std::iterator
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.12.2013, 14:49     Реализация примитивного STL совместимого контейнера #7
от итератора наследоваться все же полезно. Croessmah показал как лучше тайпдефить нужные типы.
по поводу того, почему это нужно тайпдефить:
возможно описание этого дела есть в главе 9.4 Наследование и шаблоны классов вот такой книги:
Дэвид Вандевурд, Николай М. Джосаттис Шаблоны C++: справочник разработчика = C++ Templates: The Complete Guide. — М.: «Вильямс», 2003. — С. 544. — ISBN 0-201-73484-2
ссылка с картинкой: http://www.williamspublishing.com/Bo...59-0513-3.html

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

В общем там всякие зависимые от аргумента шаблона имена и т.д. и т.п. Лучше найти и почитать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2013, 15:05     Реализация примитивного STL совместимого контейнера
Еще ссылки по теме:

C++ Конструкция цикла for, для удаления элементов во время перечисления из контейнера STL
C++ STL итератор на конец контейнера
C++ Обработка STL контейнера vector

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

Или воспользуйтесь поиском по форуму:
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
21.12.2013, 15:05     Реализация примитивного STL совместимого контейнера #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;
}
Yandex
Объявления
21.12.2013, 15:05     Реализация примитивного STL совместимого контейнера
Ответ Создать тему
Опции темы

Текущее время: 02:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru