254 lines · c
1#ifndef CONTAINERS_H2#define CONTAINERS_H3 4namespace std {5 6template <typename T>7class iterator {8public:9 iterator() {}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 40private:41 T *ptr;42};43 44template <class Iterator>45class const_iterator {46public:47 const_iterator() {}48 const_iterator(const Iterator &iter) : iter(iter) {}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 70private:71 Iterator iter;72};73 74template <class Iterator>75class forward_iterable {76public:77 forward_iterable() {}78 typedef Iterator iterator;79 typedef const_iterator<Iterator> const_iterator;80 81 iterator begin() { return _begin; }82 iterator end() { return _end; }83 84 const_iterator begin() const { return _begin; }85 const_iterator end() const { return _end; }86 87 const_iterator cbegin() const { return _begin; }88 const_iterator cend() const { return _end; }89 90private:91 iterator _begin, _end;92};93 94template <class Iterator>95class reverse_iterator {96public:97 reverse_iterator() {}98 reverse_iterator(const Iterator &iter) : iter(iter) {}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 113private:114 Iterator iter;115};116 117template <class Iterator>118class backward_iterable {119public:120 backward_iterable() {}121 122 typedef reverse_iterator<Iterator> reverse_iterator;123 typedef const_iterator<reverse_iterator> const_reverse_iterator;124 125 reverse_iterator rbegin() { return _rbegin; }126 reverse_iterator rend() { return _rend; }127 128 const_reverse_iterator rbegin() const { return _rbegin; }129 const_reverse_iterator rend() const { return _rend; }130 131 const_reverse_iterator crbegin() const { return _rbegin; }132 const_reverse_iterator crend() const { return _rend; }133 134private:135 reverse_iterator _rbegin, _rend;136};137 138template <class Iterator>139class bidirectional_iterable : public forward_iterable<Iterator>,140 public backward_iterable<Iterator> {};141 142template <typename A, typename B>143struct pair {144 pair(A f, B s) : first(f), second(s) {}145 A first;146 B second;147};148 149class string {150public:151 string() {}152 string(const char *) {}153};154 155template <typename T, int n>156class array : public backward_iterable<iterator<T>> {157public:158 array() {}159 160 typedef T *iterator;161 typedef const T *const_iterator;162 163 iterator begin() { return &v[0]; }164 iterator end() { return &v[n - 1]; }165 166 const_iterator begin() const { return &v[0]; }167 const_iterator end() const { return &v[n - 1]; }168 169 const_iterator cbegin() const { return &v[0]; }170 const_iterator cend() const { return &v[n - 1]; }171 172private:173 T v[n];174};175 176template <typename T>177class deque : public bidirectional_iterable<iterator<T>> {178public:179 deque() {}180};181 182template <typename T>183class list : public bidirectional_iterable<iterator<T>> {184public:185 list() {}186};187 188template <typename T>189class forward_list : public forward_iterable<iterator<T>> {190public:191 forward_list() {}192};193 194template <typename T>195class vector : public bidirectional_iterable<iterator<T>> {196public:197 vector() {}198};199 200template <typename T>201class set : public bidirectional_iterable<iterator<T>> {202public:203 set() {}204};205 206template <typename T>207class multiset : public bidirectional_iterable<iterator<T>> {208public:209 multiset() {}210};211 212template <typename key, typename value>213class map : public bidirectional_iterable<iterator<pair<key, value>>> {214public:215 map() {}216 217 iterator<pair<key, value>> find(const key &);218 const_iterator<iterator<pair<key, value>>> find(const key &) const;219};220 221template <typename key, typename value>222class multimap : public bidirectional_iterable<iterator<pair<key, value>>> {223public:224 multimap() {}225};226 227template <typename T>228class unordered_set : public forward_iterable<iterator<T>> {229public:230 unordered_set() {}231};232 233template <typename T>234class unordered_multiset : public forward_iterable<iterator<T>> {235public:236 unordered_multiset() {}237};238 239template <typename key, typename value>240class unordered_map : public forward_iterable<iterator<pair<key, value>>> {241public:242 unordered_map() {}243};244 245template <typename key, typename value>246class unordered_multimap : public forward_iterable<iterator<pair<key, value>>> {247public:248 unordered_multimap() {}249};250 251} // namespace std252 253#endif // CONTAINERS_H254