git.cworth.org Git - vogl/blob - src/extlib/loki/include/loki/AssocVector.h

   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:
  43         AssocVectorCompare()
  44         {}
  45
  46         AssocVectorCompare(const C &src) : C(src)
  47         {}
  48
  49         bool operator()(const first_argument_type &lhs,
  50                         const first_argument_type &rhs) const
  51         {
  52                 return C::operator()(lhs, rhs);
  53         }
  54
  55         bool operator()(const Data &lhs, const Data &rhs) const
  56         {
  57                 return operator()(lhs.first, rhs.first);
  58         }
  59
  60         bool operator()(const Data &lhs,
  61                         const first_argument_type &rhs) const
  62         {
  63                 return operator()(lhs.first, rhs);
  64         }
  65
  66         bool operator()(const first_argument_type &lhs,
  67                         const Data &rhs) const
  68         {
  69                 return operator()(lhs, rhs.first);
  70         }
  71 };
  72 }
  73
  74 ////////////////////////////////////////////////////////////////////////////////
  75 // class template AssocVector
  76 // An associative vector built as a syntactic drop-in replacement for std::map
  77 // BEWARE: AssocVector doesn't respect all map's guarantees, the most important
  78 //     being:
  79 // * iterators are invalidated by insert and erase operations
  80 // * the complexity of insert/erase is O(N) not O(log N)
  81 // * value_type is std::pair<K, V> not std::pair<const K, V>
  82 // * iterators are random
  83 ////////////////////////////////////////////////////////////////////////////////
  84
  85
  86 template
  87 <
  88 class K,
  89       class V,
  90       class C = std::less<K>,
  91       class A = std::allocator< std::pair<K, V> >
  92       >
  93 class AssocVector
  94         : private std::vector< std::pair<K, V>, A >
  95         , private Private::AssocVectorCompare<V, C>
  96 {
  97         typedef std::vector<std::pair<K, V>, A> Base;
  98         typedef Private::AssocVectorCompare<V, C> MyCompare;
  99
 100 public:
 101         typedef K key_type;
 102         typedef V mapped_type;
 103         typedef typename Base::value_type value_type;
 104
 105         typedef C key_compare;
 106         typedef A allocator_type;
 107         typedef typename A::reference reference;
 108         typedef typename A::const_reference const_reference;
 109         typedef typename Base::iterator iterator;
 110         typedef typename Base::const_iterator const_iterator;
 111         typedef typename Base::size_type size_type;
 112         typedef typename Base::difference_type difference_type;
 113         typedef typename A::pointer pointer;
 114         typedef typename A::const_pointer const_pointer;
 115         typedef typename Base::reverse_iterator reverse_iterator;
 116         typedef typename Base::const_reverse_iterator const_reverse_iterator;
 117
 118         class value_compare
 119                 : public std::binary_function<value_type, value_type, bool>
 120                 , private key_compare
 121         {
 122                 friend class AssocVector;
 123
 124         protected:
 125                 value_compare(key_compare pred) : key_compare(pred)
 126                 {}
 127
 128         public:
 129                 bool operator()(const value_type &lhs, const value_type &rhs) const
 130                 {
 131                         return key_compare::operator()(lhs.first, rhs.first);
 132                 }
 133         };
 134
 135         // 23.3.1.1 construct/copy/destroy
 136
 137         explicit AssocVector(const key_compare &comp = key_compare(),
 138                              const A &alloc = A())
 139                 : Base(alloc), MyCompare(comp)
 140         {}
 141
 142         template <class InputIterator>
 143         AssocVector(InputIterator first, InputIterator last,
 144                     const key_compare &comp = key_compare(),
 145                     const A &alloc = A())
 146                 : Base(first, last, alloc), MyCompare(comp)
 147         {
 148                 MyCompare &me = *this;
 149                 std::sort(begin(), end(), me);
 150         }
 151
 152         AssocVector &operator=(const AssocVector &rhs)
 153         {
 154                 AssocVector(rhs).swap(*this);
 155                 return *this;
 156         }
 157
 158         // iterators:
 159         // The following are here because MWCW gets 'using' wrong
 160         iterator begin()
 161         {
 162                 return Base::begin();
 163         }
 164         const_iterator begin() const
 165         {
 166                 return Base::begin();
 167         }
 168         iterator end()
 169         {
 170                 return Base::end();
 171         }
 172         const_iterator end() const
 173         {
 174                 return Base::end();
 175         }
 176         reverse_iterator rbegin()
 177         {
 178                 return Base::rbegin();
 179         }
 180         const_reverse_iterator rbegin() const
 181         {
 182                 return Base::rbegin();
 183         }
 184         reverse_iterator rend()
 185         {
 186                 return Base::rend();
 187         }
 188         const_reverse_iterator rend() const
 189         {
 190                 return Base::rend();
 191         }
 192
 193         // capacity:
 194         bool empty() const
 195         {
 196                 return Base::empty();
 197         }
 198         size_type size() const
 199         {
 200                 return Base::size();
 201         }
 202         size_type max_size()
 203         {
 204                 return Base::max_size();
 205         }
 206
 207         // 23.3.1.2 element access:
 208         mapped_type &operator[](const key_type &key)
 209         {
 210                 return insert(value_type(key, mapped_type())).first->second;
 211         }
 212
 213         // modifiers:
 214         std::pair<iterator, bool> insert(const value_type &val)
 215         {
 216                 bool found(true);
 217                 iterator i(lower_bound(val.first));
 218
 219                 if (i == end() || this->operator()(val.first, i->first))
 220                 {
 221                         i = Base::insert(i, val);
 222                         found = false;
 223                 }
 224                 return std::make_pair(i, !found);
 225         }
 226         //Section [23.1.2], Table 69
 227         //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
 228         iterator insert(iterator pos, const value_type &val)
 229         {
 230                 if( (pos == begin() || this->operator()(*(pos-1),val)) &&
 231                         (pos == end()    || this->operator()(val, *pos)) )
 232                 {
 233                         return Base::insert(pos, val);
 234                 }
 235                 return insert(val).first;
 236         }
 237
 238         template <class InputIterator>
 239         void insert(InputIterator first, InputIterator last)
 240         {
 241                 for (; first != last; ++first) insert(*first);
 242         }
 243
 244         void erase(iterator pos)
 245         {
 246                 Base::erase(pos);
 247         }
 248
 249         size_type erase(const key_type &k)
 250         {
 251                 iterator i(find(k));
 252                 if (i == end()) return 0;
 253                 erase(i);
 254                 return 1;
 255         }
 256
 257         void erase(iterator first, iterator last)
 258         {
 259                 Base::erase(first, last);
 260         }
 261
 262         void swap(AssocVector &other)
 263         {
 264                 Base::swap(other);
 265                 MyCompare &me = *this;
 266                 MyCompare &rhs = other;
 267                 std::swap(me, rhs);
 268         }
 269
 270         void clear()
 271         {
 272                 Base::clear();
 273         }
 274
 275         // observers:
 276         key_compare key_comp() const
 277         {
 278                 return *this;
 279         }
 280
 281         value_compare value_comp() const
 282         {
 283                 const key_compare &comp = *this;
 284                 return value_compare(comp);
 285         }
 286
 287         // 23.3.1.3 map operations:
 288         iterator find(const key_type &k)
 289         {
 290                 iterator i(lower_bound(k));
 291                 if (i != end() && this->operator()(k, i->first))
 292                 {
 293                         i = end();
 294                 }
 295                 return i;
 296         }
 297
 298         const_iterator find(const key_type &k) const
 299         {
 300                 const_iterator i(lower_bound(k));
 301                 if (i != end() && this->operator()(k, i->first))
 302                 {
 303                         i = end();
 304                 }
 305                 return i;
 306         }
 307
 308         size_type count(const key_type &k) const
 309         {
 310                 return find(k) != end();
 311         }
 312
 313         iterator lower_bound(const key_type &k)
 314         {
 315                 MyCompare &me = *this;
 316                 return std::lower_bound(begin(), end(), k, me);
 317         }
 318
 319         const_iterator lower_bound(const key_type &k) const
 320         {
 321                 const MyCompare &me = *this;
 322                 return std::lower_bound(begin(), end(), k, me);
 323         }
 324
 325         iterator upper_bound(const key_type &k)
 326         {
 327                 MyCompare &me = *this;
 328                 return std::upper_bound(begin(), end(), k, me);
 329         }
 330
 331         const_iterator upper_bound(const key_type &k) const
 332         {
 333                 const MyCompare &me = *this;
 334                 return std::upper_bound(begin(), end(), k, me);
 335         }
 336
 337         std::pair<iterator, iterator> equal_range(const key_type &k)
 338         {
 339                 MyCompare &me = *this;
 340                 return std::equal_range(begin(), end(), k, me);
 341         }
 342
 343         std::pair<const_iterator, const_iterator> equal_range(
 344             const key_type &k) const
 345         {
 346                 const MyCompare &me = *this;
 347                 return std::equal_range(begin(), end(), k, me);
 348         }
 349
 350         template <class K1, class V1, class C1, class A1>
 351         friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
 352                                const AssocVector<K1, V1, C1, A1>& rhs);
 353
 354         bool operator<(const AssocVector &rhs) const
 355         {
 356                 const Base &me = *this;
 357                 const Base &yo = rhs;
 358                 return me < yo;
 359         }
 360
 361         template <class K1, class V1, class C1, class A1>
 362         friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
 363                                const AssocVector<K1, V1, C1, A1>& rhs);
 364
 365         template <class K1, class V1, class C1, class A1>
 366         friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
 367                               const AssocVector<K1, V1, C1, A1>& rhs);
 368
 369         template <class K1, class V1, class C1, class A1>
 370         friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
 371                                const AssocVector<K1, V1, C1, A1>& rhs);
 372
 373         template <class K1, class V1, class C1, class A1>
 374         friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
 375                                const AssocVector<K1, V1, C1, A1>& rhs);
 376 };
 377
 378 template <class K, class V, class C, class A>
 379 inline bool operator==(const AssocVector<K, V, C, A>& lhs,
 380                        const AssocVector<K, V, C, A>& rhs)
 381 {
 382         const std::vector<std::pair<K, V>, A>& me = lhs;
 383         return me == rhs;
 384 }
 385
 386 template <class K, class V, class C, class A>
 387 inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
 388                        const AssocVector<K, V, C, A>& rhs)
 389 {
 390         return !(lhs == rhs);
 391 }
 392
 393 template <class K, class V, class C, class A>
 394 inline bool operator>(const AssocVector<K, V, C, A>& lhs,
 395                       const AssocVector<K, V, C, A>& rhs)
 396 {
 397         return rhs < lhs;
 398 }
 399
 400 template <class K, class V, class C, class A>
 401 inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
 402                        const AssocVector<K, V, C, A>& rhs)
 403 {
 404         return !(lhs < rhs);
 405 }
 406
 407 template <class K, class V, class C, class A>
 408 inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
 409                        const AssocVector<K, V, C, A>& rhs)
 410 {
 411         return !(rhs < lhs);
 412 }
 413
 414
 415 // specialized algorithms:
 416 template <class K, class V, class C, class A>
 417 void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
 418 {
 419         lhs.swap(rhs);
 420 }
 421
 422 } // namespace Loki
 423
 424 #endif // end file guardian
 425