1 //////////////////////////////////////////////////////////////////////////////// 2 // The Loki Library 3 // Copyright (c) 2001 by Andrei Alexandrescu 4 // This code accompanies the book: 5 // Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 6 // Patterns Applied". Copyright (c) 2001. Addison-Wesley. 7 // Permission to use, copy, modify, distribute and sell this software for any 8 // purpose is hereby granted without fee, provided that the above copyright 9 // notice appear in all copies and that both that copyright notice and this 10 // permission notice appear in supporting documentation. 11 // The author or Addison-Wesley Longman make no representations about the 12 // suitability of this software for any purpose. It is provided "as is" 13 // without express or implied warranty. 14 //////////////////////////////////////////////////////////////////////////////// 15 #ifndef LOKI_ASSOCVECTOR_INC_ 16 #define LOKI_ASSOCVECTOR_INC_ 17 18 // $Id: AssocVector.h 765 2006-10-18 13:55:32Z syntheticpp $ 19 20 21 #include <algorithm> 22 #include <functional> 23 #include <vector> 24 #include <utility> 25 26 namespace Loki 27 { 28 //////////////////////////////////////////////////////////////////////////////// 29 // class template AssocVectorCompare 30 // Used by AssocVector 31 //////////////////////////////////////////////////////////////////////////////// 32 33 namespace Private 34 { 35 template <class Value, class C> 36 class AssocVectorCompare : public C 37 { 38 typedef std::pair<typename C::first_argument_type, Value> 39 Data; 40 typedef typename C::first_argument_type first_argument_type; 41 42 public: AssocVectorCompare()43 AssocVectorCompare() 44 {} 45 AssocVectorCompare(const C & src)46 AssocVectorCompare(const C& src) : C(src) 47 {} 48 operator()49 bool operator()(const first_argument_type& lhs, 50 const first_argument_type& rhs) const 51 { return C::operator()(lhs, rhs); } 52 operator()53 bool operator()(const Data& lhs, const Data& rhs) const 54 { return operator()(lhs.first, rhs.first); } 55 operator()56 bool operator()(const Data& lhs, 57 const first_argument_type& rhs) const 58 { return operator()(lhs.first, rhs); } 59 operator()60 bool operator()(const first_argument_type& lhs, 61 const Data& rhs) const 62 { return operator()(lhs, rhs.first); } 63 }; 64 } 65 66 //////////////////////////////////////////////////////////////////////////////// 67 // class template AssocVector 68 // An associative vector built as a syntactic drop-in replacement for std::map 69 // BEWARE: AssocVector doesn't respect all map's guarantees, the most important 70 // being: 71 // * iterators are invalidated by insert and erase operations 72 // * the complexity of insert/erase is O(N) not O(log N) 73 // * value_type is std::pair<K, V> not std::pair<const K, V> 74 // * iterators are random 75 //////////////////////////////////////////////////////////////////////////////// 76 77 78 template 79 < 80 class K, 81 class V, 82 class C = std::less<K>, 83 class A = std::allocator< std::pair<K, V> > 84 > 85 class AssocVector 86 : private std::vector< std::pair<K, V>, A > 87 , private Private::AssocVectorCompare<V, C> 88 { 89 typedef std::vector<std::pair<K, V>, A> Base; 90 typedef Private::AssocVectorCompare<V, C> MyCompare; 91 92 public: 93 typedef K key_type; 94 typedef V mapped_type; 95 typedef typename Base::value_type value_type; 96 97 typedef C key_compare; 98 typedef A allocator_type; 99 typedef typename A::reference reference; 100 typedef typename A::const_reference const_reference; 101 typedef typename Base::iterator iterator; 102 typedef typename Base::const_iterator const_iterator; 103 typedef typename Base::size_type size_type; 104 typedef typename Base::difference_type difference_type; 105 typedef typename A::pointer pointer; 106 typedef typename A::const_pointer const_pointer; 107 typedef typename Base::reverse_iterator reverse_iterator; 108 typedef typename Base::const_reverse_iterator const_reverse_iterator; 109 110 class value_compare 111 : public std::binary_function<value_type, value_type, bool> 112 , private key_compare 113 { 114 friend class AssocVector; 115 116 protected: value_compare(key_compare pred)117 value_compare(key_compare pred) : key_compare(pred) 118 {} 119 120 public: operator()121 bool operator()(const value_type& lhs, const value_type& rhs) const 122 { return key_compare::operator()(lhs.first, rhs.first); } 123 }; 124 125 // 23.3.1.1 construct/copy/destroy 126 127 explicit AssocVector(const key_compare& comp = key_compare(), 128 const A& alloc = A()) Base(alloc)129 : Base(alloc), MyCompare(comp) 130 {} 131 132 template <class InputIterator> 133 AssocVector(InputIterator first, InputIterator last, 134 const key_compare& comp = key_compare(), 135 const A& alloc = A()) Base(first,last,alloc)136 : Base(first, last, alloc), MyCompare(comp) 137 { 138 MyCompare& me = *this; 139 std::sort(begin(), end(), me); 140 } 141 142 AssocVector& operator=(const AssocVector& rhs) 143 { 144 AssocVector(rhs).swap(*this); 145 return *this; 146 } 147 148 // iterators: 149 // The following are here because MWCW gets 'using' wrong begin()150 iterator begin() { return Base::begin(); } begin()151 const_iterator begin() const { return Base::begin(); } end()152 iterator end() { return Base::end(); } end()153 const_iterator end() const { return Base::end(); } rbegin()154 reverse_iterator rbegin() { return Base::rbegin(); } rbegin()155 const_reverse_iterator rbegin() const { return Base::rbegin(); } rend()156 reverse_iterator rend() { return Base::rend(); } rend()157 const_reverse_iterator rend() const { return Base::rend(); } 158 159 // capacity: empty()160 bool empty() const { return Base::empty(); } size()161 size_type size() const { return Base::size(); } max_size()162 size_type max_size() { return Base::max_size(); } 163 164 // 23.3.1.2 element access: 165 mapped_type& operator[](const key_type& key) 166 { return insert(value_type(key, mapped_type())).first->second; } 167 168 // modifiers: insert(const value_type & val)169 std::pair<iterator, bool> insert(const value_type& val) 170 { 171 bool found(true); 172 iterator i(lower_bound(val.first)); 173 174 if (i == end() || this->operator()(val.first, i->first)) 175 { 176 i = Base::insert(i, val); 177 found = false; 178 } 179 return std::make_pair(i, !found); 180 } 181 //Section [23.1.2], Table 69 182 //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4 insert(iterator pos,const value_type & val)183 iterator insert(iterator pos, const value_type& val) 184 { 185 if( (pos == begin() || this->operator()(*(pos-1),val)) && 186 (pos == end() || this->operator()(val, *pos)) ) 187 { 188 return Base::insert(pos, val); 189 } 190 return insert(val).first; 191 } 192 193 template <class InputIterator> insert(InputIterator first,InputIterator last)194 void insert(InputIterator first, InputIterator last) 195 { for (; first != last; ++first) insert(*first); } 196 erase(iterator pos)197 void erase(iterator pos) 198 { Base::erase(pos); } 199 erase(const key_type & k)200 size_type erase(const key_type& k) 201 { 202 iterator i(find(k)); 203 if (i == end()) return 0; 204 erase(i); 205 return 1; 206 } 207 erase(iterator first,iterator last)208 void erase(iterator first, iterator last) 209 { Base::erase(first, last); } 210 swap(AssocVector & other)211 void swap(AssocVector& other) 212 { 213 Base::swap(other); 214 MyCompare& me = *this; 215 MyCompare& rhs = other; 216 std::swap(me, rhs); 217 } 218 clear()219 void clear() 220 { Base::clear(); } 221 222 // observers: key_comp()223 key_compare key_comp() const 224 { return *this; } 225 value_comp()226 value_compare value_comp() const 227 { 228 const key_compare& comp = *this; 229 return value_compare(comp); 230 } 231 232 // 23.3.1.3 map operations: find(const key_type & k)233 iterator find(const key_type& k) 234 { 235 iterator i(lower_bound(k)); 236 if (i != end() && this->operator()(k, i->first)) 237 { 238 i = end(); 239 } 240 return i; 241 } 242 find(const key_type & k)243 const_iterator find(const key_type& k) const 244 { 245 const_iterator i(lower_bound(k)); 246 if (i != end() && this->operator()(k, i->first)) 247 { 248 i = end(); 249 } 250 return i; 251 } 252 count(const key_type & k)253 size_type count(const key_type& k) const 254 { return find(k) != end(); } 255 lower_bound(const key_type & k)256 iterator lower_bound(const key_type& k) 257 { 258 MyCompare& me = *this; 259 return std::lower_bound(begin(), end(), k, me); 260 } 261 lower_bound(const key_type & k)262 const_iterator lower_bound(const key_type& k) const 263 { 264 const MyCompare& me = *this; 265 return std::lower_bound(begin(), end(), k, me); 266 } 267 upper_bound(const key_type & k)268 iterator upper_bound(const key_type& k) 269 { 270 MyCompare& me = *this; 271 return std::upper_bound(begin(), end(), k, me); 272 } 273 upper_bound(const key_type & k)274 const_iterator upper_bound(const key_type& k) const 275 { 276 const MyCompare& me = *this; 277 return std::upper_bound(begin(), end(), k, me); 278 } 279 equal_range(const key_type & k)280 std::pair<iterator, iterator> equal_range(const key_type& k) 281 { 282 MyCompare& me = *this; 283 return std::equal_range(begin(), end(), k, me); 284 } 285 equal_range(const key_type & k)286 std::pair<const_iterator, const_iterator> equal_range( 287 const key_type& k) const 288 { 289 const MyCompare& me = *this; 290 return std::equal_range(begin(), end(), k, me); 291 } 292 293 template <class K1, class V1, class C1, class A1> 294 friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs, 295 const AssocVector<K1, V1, C1, A1>& rhs); 296 297 bool operator<(const AssocVector& rhs) const 298 { 299 const Base& me = *this; 300 const Base& yo = rhs; 301 return me < yo; 302 } 303 304 template <class K1, class V1, class C1, class A1> 305 friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs, 306 const AssocVector<K1, V1, C1, A1>& rhs); 307 308 template <class K1, class V1, class C1, class A1> 309 friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs, 310 const AssocVector<K1, V1, C1, A1>& rhs); 311 312 template <class K1, class V1, class C1, class A1> 313 friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs, 314 const AssocVector<K1, V1, C1, A1>& rhs); 315 316 template <class K1, class V1, class C1, class A1> 317 friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs, 318 const AssocVector<K1, V1, C1, A1>& rhs); 319 }; 320 321 template <class K, class V, class C, class A> 322 inline bool operator==(const AssocVector<K, V, C, A>& lhs, 323 const AssocVector<K, V, C, A>& rhs) 324 { 325 const std::vector<std::pair<K, V>, A>& me = lhs; 326 return me == rhs; 327 } 328 329 template <class K, class V, class C, class A> 330 inline bool operator!=(const AssocVector<K, V, C, A>& lhs, 331 const AssocVector<K, V, C, A>& rhs) 332 { return !(lhs == rhs); } 333 334 template <class K, class V, class C, class A> 335 inline bool operator>(const AssocVector<K, V, C, A>& lhs, 336 const AssocVector<K, V, C, A>& rhs) 337 { return rhs < lhs; } 338 339 template <class K, class V, class C, class A> 340 inline bool operator>=(const AssocVector<K, V, C, A>& lhs, 341 const AssocVector<K, V, C, A>& rhs) 342 { return !(lhs < rhs); } 343 344 template <class K, class V, class C, class A> 345 inline bool operator<=(const AssocVector<K, V, C, A>& lhs, 346 const AssocVector<K, V, C, A>& rhs) 347 { return !(rhs < lhs); } 348 349 350 // specialized algorithms: 351 template <class K, class V, class C, class A> swap(AssocVector<K,V,C,A> & lhs,AssocVector<K,V,C,A> & rhs)352 void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs) 353 { lhs.swap(rhs); } 354 355 } // namespace Loki 356 357 #endif // end file guardian 358 359