1 #ifndef CONTAINERS_H
2 #define CONTAINERS_H
3 
4 namespace std {
5 
6 template <typename T>
7 class iterator {
8 public:
iterator()9   iterator() {}
iterator(const iterator<T> & iter)10   iterator(const iterator<T> &iter) : ptr(iter.ptr) {}
11 
12   typedef T value_type;
13   typedef T *pointer;
14   typedef T &reference;
15 
16   reference operator*() const { return *ptr; }
17   pointer operator->() const { return ptr; }
18   iterator &operator++() {
19     ++ptr;
20     return *this;
21   }
22   iterator &operator--() {
23     --ptr;
24     return *this;
25   }
26   iterator operator++(int) {
27     iterator res(*this);
28     ++ptr;
29     return res;
30   }
31   iterator operator--(int) {
32     iterator res(*this);
33     --ptr;
34     return res;
35   }
36   bool operator!=(const iterator<T> &iter) const {
37     return ptr != iter.operator->();
38   }
39 
40 private:
41   T *ptr;
42 };
43 
44 template <class Iterator>
45 class const_iterator {
46 public:
const_iterator()47   const_iterator() {}
const_iterator(const Iterator & iter)48   const_iterator(const Iterator &iter) : iter(iter) {}
const_iterator(const const_iterator<Iterator> & citer)49   const_iterator(const const_iterator<Iterator> &citer) : iter(citer.iter) {}
50 
51   typedef const typename Iterator::value_type value_type;
52   typedef const typename Iterator::pointer pointer;
53   typedef const typename Iterator::reference reference;
54 
55   reference operator*() const { return *iter; }
56   pointer operator->() const { return iter.operator->(); }
57 
58   const_iterator &operator++() { return ++iter; }
59   const_iterator &operator--() { return --iter; }
60   const_iterator operator++(int) { return iter--; }
61   const_iterator operator--(int) { return iter--; }
62 
63   bool operator!=(const Iterator &it) const {
64     return iter->operator->() != it.operator->();
65   }
66   bool operator!=(const const_iterator<Iterator> &it) const {
67     return iter.operator->() != it.operator->();
68   }
69 
70 private:
71   Iterator iter;
72 };
73 
74 template <class Iterator>
75 class forward_iterable {
76 public:
forward_iterable()77   forward_iterable() {}
78   typedef Iterator iterator;
79   typedef const_iterator<Iterator> const_iterator;
80 
begin()81   iterator begin() { return _begin; }
end()82   iterator end() { return _end; }
83 
begin()84   const_iterator begin() const { return _begin; }
end()85   const_iterator end() const { return _end; }
86 
cbegin()87   const_iterator cbegin() const { return _begin; }
cend()88   const_iterator cend() const { return _end; }
89 
90 private:
91   iterator _begin, _end;
92 };
93 
94 template <class Iterator>
95 class reverse_iterator {
96 public:
reverse_iterator()97   reverse_iterator() {}
reverse_iterator(const Iterator & iter)98   reverse_iterator(const Iterator &iter) : iter(iter) {}
reverse_iterator(const reverse_iterator<Iterator> & rit)99   reverse_iterator(const reverse_iterator<Iterator> &rit) : iter(rit.iter) {}
100 
101   typedef typename Iterator::value_type value_type;
102   typedef typename Iterator::pointer pointer;
103   typedef typename Iterator::reference reference;
104 
105   reference operator*() { return *iter; }
106   pointer operator->() { return iter.operator->(); }
107 
108   reverse_iterator &operator++() { return --iter; }
109   reverse_iterator &operator--() { return ++iter; }
110   reverse_iterator operator++(int) { return iter--; }
111   reverse_iterator operator--(int) { return iter++; }
112 
113 private:
114   Iterator iter;
115 };
116 
117 template <class Iterator>
118 class backward_iterable {
119 public:
backward_iterable()120   backward_iterable() {}
121 
122   typedef reverse_iterator<Iterator> reverse_iterator;
123   typedef const_iterator<reverse_iterator> const_reverse_iterator;
124 
rbegin()125   reverse_iterator rbegin() { return _rbegin; }
rend()126   reverse_iterator rend() { return _rend; }
127 
rbegin()128   const_reverse_iterator rbegin() const { return _rbegin; }
rend()129   const_reverse_iterator rend() const { return _rend; }
130 
crbegin()131   const_reverse_iterator crbegin() const { return _rbegin; }
crend()132   const_reverse_iterator crend() const { return _rend; }
133 
134 private:
135   reverse_iterator _rbegin, _rend;
136 };
137 
138 template <class Iterator>
139 class bidirectional_iterable : public forward_iterable<Iterator>,
140                                public backward_iterable<Iterator> {};
141 
142 template <typename A, typename B>
143 struct pair {
pairpair144   pair(A f, B s) : first(f), second(s) {}
145   A first;
146   B second;
147 };
148 
149 class string {
150 public:
string()151   string() {}
string(const char *)152   string(const char *) {}
153 };
154 
155 template <typename T, int n>
156 class array : public backward_iterable<iterator<T>> {
157 public:
array()158   array() {}
159 
160   typedef T *iterator;
161   typedef const T *const_iterator;
162 
begin()163   iterator begin() { return &v[0]; }
end()164   iterator end() { return &v[n - 1]; }
165 
begin()166   const_iterator begin() const { return &v[0]; }
end()167   const_iterator end() const { return &v[n - 1]; }
168 
cbegin()169   const_iterator cbegin() const { return &v[0]; }
cend()170   const_iterator cend() const { return &v[n - 1]; }
171 
172 private:
173   T v[n];
174 };
175 
176 template <typename T>
177 class deque : public bidirectional_iterable<iterator<T>> {
178 public:
deque()179   deque() {}
180 };
181 
182 template <typename T>
183 class list : public bidirectional_iterable<iterator<T>> {
184 public:
list()185   list() {}
186 };
187 
188 template <typename T>
189 class forward_list : public forward_iterable<iterator<T>> {
190 public:
forward_list()191   forward_list() {}
192 };
193 
194 template <typename T>
195 class vector : public bidirectional_iterable<iterator<T>> {
196 public:
vector()197   vector() {}
198 };
199 
200 template <typename T>
201 class set : public bidirectional_iterable<iterator<T>> {
202 public:
set()203   set() {}
204 };
205 
206 template <typename T>
207 class multiset : public bidirectional_iterable<iterator<T>> {
208 public:
multiset()209   multiset() {}
210 };
211 
212 template <typename key, typename value>
213 class map : public bidirectional_iterable<iterator<pair<key, value>>> {
214 public:
map()215   map() {}
216 
find(const key &)217   iterator<pair<key, value>> find(const key &) {}
find(const key &)218   const_iterator<iterator<pair<key, value>>> find(const key &) const {}
219 };
220 
221 template <typename key, typename value>
222 class multimap : public bidirectional_iterable<iterator<pair<key, value>>> {
223 public:
multimap()224   multimap() {}
225 };
226 
227 template <typename T>
228 class unordered_set : public forward_iterable<iterator<T>> {
229 public:
unordered_set()230   unordered_set() {}
231 };
232 
233 template <typename T>
234 class unordered_multiset : public forward_iterable<iterator<T>> {
235 public:
unordered_multiset()236   unordered_multiset() {}
237 };
238 
239 template <typename key, typename value>
240 class unordered_map : public forward_iterable<iterator<pair<key, value>>> {
241 public:
unordered_map()242   unordered_map() {}
243 };
244 
245 template <typename key, typename value>
246 class unordered_multimap : public forward_iterable<iterator<pair<key, value>>> {
247 public:
unordered_multimap()248   unordered_multimap() {}
249 };
250 
251 } // namespace std
252 
253 #endif // CONTAINERS_H
254