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