00001 #ifndef ML_CONTAINER_ASSOCIATIVE_VECTOR_HPP
00002 #define ML_CONTAINER_ASSOCIATIVE_VECTOR_HPP
00003
00004 #include <functional>
00005 #include <algorithm>
00006 #include <vector>
00007
00008 namespace ml_container
00009 {
00023 template < typename K, typename T, typename Compare = std::less<K> >
00024 class KeyCompare
00025 {
00026 public:
00027 KeyCompare(): cmp() { };
00028
00029 bool operator()(const std::pair<K, T>& lhs, const std::pair<K, T>& rhs) const
00030 { return do_compare(lhs.first, rhs.first); }
00031
00032 bool operator()(const std::pair<K, T>& lhs, const K& k) const
00033 { return do_compare(lhs.first, k); }
00034
00035 bool operator()(const K& k, const std::pair<K, T>& rhs) const
00036 { return do_compare(k, rhs.first); }
00037
00038 private:
00039 bool do_compare(const K& k1, const K& k2) const
00040 { return cmp(k1, k2); }
00041
00042 Compare cmp;
00043 };
00044
00045
00046 template < typename K, typename T, typename Compare = std::less<K>, typename Alloc = std::allocator< std::pair<K, T> > >
00047 class associative_vector
00048 {
00049
00050 typedef typename std::vector< std::pair<K, T>, Alloc > container_type;
00051
00052 public:
00053
00054 typedef typename container_type::value_type value_type;
00055 typedef typename container_type::value_type::first_type key_type;
00056 typedef typename container_type::value_type::second_type mapped_type;
00057 typedef KeyCompare<key_type, mapped_type, Compare> key_compare;
00058 typedef key_compare value_compare;
00059 typedef mapped_type* pointer;
00060 typedef mapped_type& reference;
00061 typedef const mapped_type& const_reference;
00062 typedef typename container_type::size_type size_type;
00063 typedef typename container_type::difference_type difference_type;
00064 typedef typename container_type::iterator iterator;
00065 typedef typename container_type::const_iterator const_iterator;
00066 typedef typename container_type::reverse_iterator reverse_iterator;
00067 typedef typename container_type::const_reverse_iterator const_reverse_iterator;
00068
00069 private:
00070 container_type container;
00071 key_compare cmp;
00072
00073 public:
00074 iterator begin()
00075 { return container.begin(); }
00076
00077 iterator end()
00078 { return container.end(); }
00079
00080 const_iterator begin() const
00081 { return container.begin(); }
00082
00083 const_iterator end() const
00084 { return container.end(); }
00085
00086 reverse_iterator rbegin()
00087 { return container.rbegin(); }
00088
00089 reverse_iterator rend()
00090 { return container.rend(); }
00091
00092 const_reverse_iterator rbegin() const
00093 { return container.rbegin(); }
00094
00095 const_reverse_iterator rend() const
00096 { return container.rend(); }
00097
00098 size_type size() const
00099 { return container.size(); }
00100
00101 size_type max_size() const
00102 { return container.max_size(); }
00103
00104 bool empty() const
00105 { return container.empty(); }
00106
00107 key_compare key_comp() const
00108 { return cmp; }
00109
00110 value_compare value_comp() const
00111 { return key_comp(); }
00112
00113 associative_vector():
00114 container(), cmp()
00115 { }
00116
00117 template <class InputIterator>
00118 associative_vector(InputIterator first, InputIterator last):
00119 container(first, last), cmp()
00120 { std::sort(begin(), end(), cmp); }
00121
00122 associative_vector(const associative_vector& v):
00123 container(v.container), cmp(v.cmp)
00124 { }
00125
00126 associative_vector& operator=(const associative_vector& v)
00127 {
00128 if (this == &v) return *this;
00129 container = v.container;
00130 cmp = v.cmp;
00131 return *this;
00132 }
00133
00134 void swap(associative_vector& v)
00135 { container.swap(v); }
00136
00137 std::pair<iterator, bool>
00138 insert(const value_type& x)
00139 {
00140 iterator i(lower_bound(x.first));
00141 return (i == end() || cmp(x, *i)) ?
00142 std::make_pair(container.insert(i, x), true) :
00143 std::make_pair(i, false);
00144 }
00145
00146 iterator insert(iterator pos, const value_type& x)
00147 {
00148 if ( (pos == begin() || cmp(*(--pos), x)) &&
00149 (pos == end() || cmp(x, *pos)) )
00150 { return container.insert(pos, x); }
00151 return insert(x).first;
00152 }
00153
00154 template< class InputIterator >
00155 void insert(InputIterator first, InputIterator last)
00156 {
00157 const size_type initial_size = size();
00158 container.insert(container.end(), first, last);
00159 std::sort(container.begin() + initial_size, container.end(), cmp);
00160 std::inplace_merge(container.begin(), container.begin() + initial_size, container.end(), cmp);
00161 }
00162
00163 void erase(iterator pos)
00164 { container.erase(pos); }
00165
00166 size_type erase(const key_type& k)
00167 {
00168 iterator i(find(k));
00169 if (i == end()) return 0;
00170 erase(i);
00171 return 1;
00172 }
00173
00174 void erase(iterator first, iterator last)
00175 { container.erase(first, last); }
00176
00177 void clear()
00178 { container.clear(); }
00179
00180 iterator find(const key_type& k)
00181 {
00182 iterator i(lower_bound(k));
00183 return (i == end() || cmp(k, *i)) ? end() : i;
00184 }
00185
00186 const_iterator find(const key_type& k) const
00187 {
00188 const_iterator i(lower_bound(k));
00189 return (i == end() || cmp(k, *i)) ? end() : i;
00190 }
00191
00192 size_type count(const key_type& k) const
00193 { return find(k) != end(); }
00194
00195 iterator lower_bound(const key_type& k)
00196 { return std::lower_bound(begin(), end(), k, cmp); }
00197
00198 const_iterator lower_bound(const key_type& k) const
00199 { return std::lower_bound(begin(), end(), k, cmp); }
00200
00201 iterator upper_bound(const key_type& k)
00202 { return std::upper_bound(begin(), end(), k, cmp); }
00203
00204 const_iterator upper_bound(const key_type& k) const
00205 { return std::upper_bound(begin(), end(), k, cmp); }
00206
00207 std::pair<iterator, iterator> equal_range(const key_type& k)
00208 { return std::equal_range(begin(), end(), k, cmp); }
00209
00210 std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
00211 { return std::equal_range(begin(), end(), k, cmp); }
00212
00213 reference operator[](const key_type& k)
00214 { return (insert(value_type(k, T())).first)->second; }
00215
00216 template< typename K1, typename T1, typename C1, typename A1 >
00217 friend bool operator==(const associative_vector<K1, T1, C1, A1>&, const associative_vector<K1, T1, C1, A1>&);
00218
00219 template< typename K1, typename T1, typename C1, typename A1 >
00220 friend bool operator!=(const associative_vector<K1, T1, C1, A1>&, const associative_vector<K1, T1, C1, A1>&);
00221
00222 template< typename K1, typename T1, typename C1, typename A1 >
00223 friend bool operator<(const associative_vector<K1, T1, C1, A1>&, const associative_vector<K1, T1, C1, A1>&);
00224
00225 template< typename K1, typename T1, typename C1, typename A1 >
00226 friend bool operator>(const associative_vector<K1, T1, C1, A1>&, const associative_vector<K1, T1, C1, A1>&);
00227
00228 template< typename K1, typename T1, typename C1, typename A1 >
00229 friend bool operator<=(const associative_vector<K1, T1, C1, A1>&, const associative_vector<K1, T1, C1, A1>&);
00230
00231 template< typename K1, typename T1, typename C1, typename A1 >
00232 friend bool operator>=(const associative_vector<K1, T1, C1, A1>&, const associative_vector<K1, T1, C1, A1>&);
00233 };
00234
00235 template< typename K, typename T, typename C, typename A >
00236 inline bool operator==(const associative_vector<K, T, C, A>& lhs, const associative_vector<K, T, C, A>& rhs)
00237 { return lhs.container == rhs.container; }
00238
00239 template< typename K, typename T, typename C, typename A >
00240 inline bool operator!=(const associative_vector<K, T, C, A>& lhs, const associative_vector<K, T, C, A>& rhs)
00241 { return lhs.container != rhs.container; }
00242
00243 template< typename K, typename T, typename C, typename A >
00244 inline bool operator<(const associative_vector<K, T, C, A>& lhs, const associative_vector<K, T, C, A>& rhs)
00245 { return lhs.container < rhs.container; }
00246
00247 template< typename K, typename T, typename C, typename A >
00248 inline bool operator>(const associative_vector<K, T, C, A>& lhs, const associative_vector<K, T, C, A>& rhs)
00249 { return lhs.container < rhs.container; }
00250
00251 template< typename K, typename T, typename C, typename A >
00252 inline bool operator<=(const associative_vector<K, T, C, A>& lhs, const associative_vector<K, T, C, A>& rhs)
00253 { return lhs.container <= rhs.container; }
00254
00255 template< typename K, typename T, typename C, typename A >
00256 inline bool operator>=(const associative_vector<K, T, C, A>& lhs, const associative_vector<K, T, C, A>& rhs)
00257 { return lhs.container <= rhs.container; }
00258
00259 }
00260
00261 #endif
00262
1.5.7