Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
DiffEreD
1442 / 779 / 257
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
1

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

20.12.2013, 00:07. Просмотров 1653. Ответов 7
Метки нет (Все метки)

Как то застрял на этом. Как правильно объявить все 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2013, 00:07
Ответы с готовыми решениями:

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

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

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

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

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

7
DU
1487 / 1133 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
20.12.2013, 01:12 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;
}
1
Croessmah
++Ͻ
14740 / 8422 / 1597
Регистрация: 27.09.2012
Сообщений: 20,714
Записей в блоге: 2
Завершенные тесты: 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
DiffEreD
1442 / 779 / 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
MrGluck
Модератор
Эксперт CЭксперт С++
8099 / 4951 / 1435
Регистрация: 29.11.2010
Сообщений: 13,435
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
DiffEreD
1442 / 779 / 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
1487 / 1133 / 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.com/Books/5-8459-0513-3.html

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

В общем там всякие зависимые от аргумента шаблона имена и т.д. и т.п. Лучше найти и почитать.
0
Nick Alte
Эксперт С++
1647 / 1019 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2013, 15:05

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

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

Структура, с использованием контейнера библиотеки STL
Помогите, пожалуйста,с задачкой. Следующие задания реализовать в виде класса,...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru