AssocVector.h

00001 
00002 // The Loki Library
00003 // Copyright (c) 2001 by Andrei Alexandrescu
00004 // This code accompanies the book:
00005 // Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
00006 //     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
00007 // Permission to use, copy, modify, distribute and sell this software for any 
00008 //     purpose is hereby granted without fee, provided that the above copyright 
00009 //     notice appear in all copies and that both that copyright notice and this 
00010 //     permission notice appear in supporting documentation.
00011 // The author or Addison-Wesley Longman make no representations about the 
00012 //     suitability of this software for any purpose. It is provided "as is" 
00013 //     without express or implied warranty.
00015 #ifndef LOKI_ASSOCVECTOR_INC_
00016 #define LOKI_ASSOCVECTOR_INC_
00017 
00018 // $Id: AssocVector.h 765 2006-10-18 13:55:32Z syntheticpp $
00019 
00020 
00021 #include <algorithm>
00022 #include <functional>
00023 #include <vector>
00024 #include <utility>
00025 
00026 namespace Loki
00027 {
00029 // class template AssocVectorCompare
00030 // Used by AssocVector
00032 
00033     namespace Private
00034     {
00035         template <class Value, class C>
00036         class AssocVectorCompare : public C
00037         {
00038             typedef std::pair<typename C::first_argument_type, Value>
00039                 Data;
00040             typedef typename C::first_argument_type first_argument_type;
00041 
00042         public:
00043             AssocVectorCompare()
00044             {}
00045             
00046             AssocVectorCompare(const C& src) : C(src)
00047             {}
00048             
00049             bool operator()(const first_argument_type& lhs, 
00050                 const first_argument_type& rhs) const
00051             { return C::operator()(lhs, rhs); }
00052             
00053             bool operator()(const Data& lhs, const Data& rhs) const
00054             { return operator()(lhs.first, rhs.first); }
00055             
00056             bool operator()(const Data& lhs, 
00057                 const first_argument_type& rhs) const
00058             { return operator()(lhs.first, rhs); }
00059             
00060             bool operator()(const first_argument_type& lhs,
00061                 const Data& rhs) const
00062             { return operator()(lhs, rhs.first); }
00063         };
00064     }
00065 
00067 // class template AssocVector
00068 // An associative vector built as a syntactic drop-in replacement for std::map
00069 // BEWARE: AssocVector doesn't respect all map's guarantees, the most important
00070 //     being:
00071 // * iterators are invalidated by insert and erase operations
00072 // * the complexity of insert/erase is O(N) not O(log N)
00073 // * value_type is std::pair<K, V> not std::pair<const K, V>
00074 // * iterators are random
00076 
00077 
00078     template
00079     <
00080         class K,
00081         class V,
00082         class C = std::less<K>,
00083         class A = std::allocator< std::pair<K, V> >
00084     >
00085     class AssocVector 
00086         : private std::vector< std::pair<K, V>, A >
00087         , private Private::AssocVectorCompare<V, C>
00088     {
00089         typedef std::vector<std::pair<K, V>, A> Base;
00090         typedef Private::AssocVectorCompare<V, C> MyCompare;
00091 
00092     public:
00093         typedef K key_type;
00094         typedef V mapped_type;
00095         typedef typename Base::value_type value_type;
00096 
00097         typedef C key_compare;
00098         typedef A allocator_type;
00099         typedef typename A::reference reference;
00100         typedef typename A::const_reference const_reference;
00101         typedef typename Base::iterator iterator;
00102         typedef typename Base::const_iterator const_iterator;
00103         typedef typename Base::size_type size_type;
00104         typedef typename Base::difference_type difference_type;
00105         typedef typename A::pointer pointer;
00106         typedef typename A::const_pointer const_pointer;
00107         typedef typename Base::reverse_iterator reverse_iterator;
00108         typedef typename Base::const_reverse_iterator const_reverse_iterator;
00109 
00110         class value_compare
00111             : public std::binary_function<value_type, value_type, bool>
00112             , private key_compare
00113         {
00114             friend class AssocVector;
00115         
00116         protected:
00117             value_compare(key_compare pred) : key_compare(pred)
00118             {}
00119 
00120         public:
00121             bool operator()(const value_type& lhs, const value_type& rhs) const
00122             { return key_compare::operator()(lhs.first, rhs.first); }
00123         };
00124         
00125         // 23.3.1.1 construct/copy/destroy
00126 
00127         explicit AssocVector(const key_compare& comp = key_compare(), 
00128             const A& alloc = A())
00129         : Base(alloc), MyCompare(comp)
00130         {}
00131         
00132         template <class InputIterator>
00133         AssocVector(InputIterator first, InputIterator last, 
00134             const key_compare& comp = key_compare(), 
00135             const A& alloc = A())
00136         : Base(first, last, alloc), MyCompare(comp)
00137         {
00138             MyCompare& me = *this;
00139             std::sort(begin(), end(), me);
00140         }
00141         
00142         AssocVector& operator=(const AssocVector& rhs)
00143         { 
00144             AssocVector(rhs).swap(*this); 
00145             return *this;
00146         }
00147 
00148         // iterators:
00149         // The following are here because MWCW gets 'using' wrong
00150         iterator begin() { return Base::begin(); }
00151         const_iterator begin() const { return Base::begin(); }
00152         iterator end() { return Base::end(); }
00153         const_iterator end() const { return Base::end(); }
00154         reverse_iterator rbegin() { return Base::rbegin(); }
00155         const_reverse_iterator rbegin() const { return Base::rbegin(); }
00156         reverse_iterator rend() { return Base::rend(); }
00157         const_reverse_iterator rend() const { return Base::rend(); }
00158         
00159         // capacity:
00160         bool empty() const { return Base::empty(); }
00161         size_type size() const { return Base::size(); }
00162         size_type max_size() { return Base::max_size(); }
00163 
00164         // 23.3.1.2 element access:
00165         mapped_type& operator[](const key_type& key)
00166         { return insert(value_type(key, mapped_type())).first->second; }
00167 
00168         // modifiers:
00169         std::pair<iterator, bool> insert(const value_type& val)
00170         {
00171             bool found(true);
00172             iterator i(lower_bound(val.first));
00173 
00174             if (i == end() || this->operator()(val.first, i->first))
00175             {
00176                 i = Base::insert(i, val);
00177                 found = false;
00178             }
00179             return std::make_pair(i, !found);
00180         }
00181         //Section [23.1.2], Table 69
00182         //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
00183         iterator insert(iterator pos, const value_type& val)
00184         {
00185             if( (pos == begin() || this->operator()(*(pos-1),val)) && 
00186                 (pos == end()    || this->operator()(val, *pos)) )
00187             {
00188                 return Base::insert(pos, val);
00189             }
00190             return insert(val).first;
00191         }
00192        
00193         template <class InputIterator>
00194         void insert(InputIterator first, InputIterator last)
00195         { for (; first != last; ++first) insert(*first); }
00196         
00197         void erase(iterator pos)
00198         { Base::erase(pos); }
00199 
00200         size_type erase(const key_type& k)
00201         {
00202             iterator i(find(k));
00203             if (i == end()) return 0;
00204             erase(i);
00205             return 1;
00206         }
00207 
00208         void erase(iterator first, iterator last)
00209         { Base::erase(first, last); }
00210 
00211         void swap(AssocVector& other)
00212         {
00213             Base::swap(other);
00214             MyCompare& me = *this;
00215             MyCompare& rhs = other;
00216             std::swap(me, rhs);
00217         }
00218         
00219         void clear()
00220         { Base::clear(); }
00221 
00222         // observers:
00223         key_compare key_comp() const
00224         { return *this; }
00225 
00226         value_compare value_comp() const
00227         {
00228             const key_compare& comp = *this;
00229             return value_compare(comp);
00230         }
00231 
00232         // 23.3.1.3 map operations:
00233         iterator find(const key_type& k)
00234         {
00235             iterator i(lower_bound(k));
00236             if (i != end() && this->operator()(k, i->first))
00237             {
00238                 i = end();
00239             }
00240             return i;
00241         }
00242 
00243         const_iterator find(const key_type& k) const
00244         {       
00245             const_iterator i(lower_bound(k));
00246             if (i != end() && this->operator()(k, i->first))
00247             {
00248                 i = end();
00249             }
00250             return i;
00251         }
00252 
00253         size_type count(const key_type& k) const
00254         { return find(k) != end(); }
00255 
00256         iterator lower_bound(const key_type& k)
00257         {
00258             MyCompare& me = *this;
00259             return std::lower_bound(begin(), end(), k, me);
00260         }
00261 
00262         const_iterator lower_bound(const key_type& k) const
00263         {
00264             const MyCompare& me = *this;
00265             return std::lower_bound(begin(), end(), k, me);
00266         }
00267 
00268         iterator upper_bound(const key_type& k)
00269         {
00270             MyCompare& me = *this;
00271             return std::upper_bound(begin(), end(), k, me);
00272         }
00273 
00274         const_iterator upper_bound(const key_type& k) const
00275         {
00276             const MyCompare& me = *this;
00277             return std::upper_bound(begin(), end(), k, me);
00278         }
00279 
00280         std::pair<iterator, iterator> equal_range(const key_type& k)
00281         {
00282             MyCompare& me = *this;
00283             return std::equal_range(begin(), end(), k, me);
00284         }
00285 
00286         std::pair<const_iterator, const_iterator> equal_range(
00287             const key_type& k) const
00288         {
00289             const MyCompare& me = *this;
00290             return std::equal_range(begin(), end(), k, me);
00291         }
00292 
00293         template <class K1, class V1, class C1, class A1>
00294         friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
00295                         const AssocVector<K1, V1, C1, A1>& rhs);
00296 
00297         bool operator<(const AssocVector& rhs) const
00298         {
00299             const Base& me = *this;
00300             const Base& yo = rhs;
00301             return me < yo;
00302         }
00303 
00304         template <class K1, class V1, class C1, class A1>
00305         friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
00306                                const AssocVector<K1, V1, C1, A1>& rhs);
00307 
00308         template <class K1, class V1, class C1, class A1>
00309         friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
00310                               const AssocVector<K1, V1, C1, A1>& rhs);
00311 
00312         template <class K1, class V1, class C1, class A1>
00313         friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
00314                                const AssocVector<K1, V1, C1, A1>& rhs);
00315 
00316         template <class K1, class V1, class C1, class A1>
00317         friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
00318                                const AssocVector<K1, V1, C1, A1>& rhs);
00319     };
00320 
00321     template <class K, class V, class C, class A>
00322     inline bool operator==(const AssocVector<K, V, C, A>& lhs,
00323                            const AssocVector<K, V, C, A>& rhs)
00324     {
00325       const std::vector<std::pair<K, V>, A>& me = lhs;
00326       return me == rhs;
00327     }
00328 
00329     template <class K, class V, class C, class A>
00330     inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
00331                            const AssocVector<K, V, C, A>& rhs)
00332     { return !(lhs == rhs); }
00333 
00334     template <class K, class V, class C, class A>
00335     inline bool operator>(const AssocVector<K, V, C, A>& lhs,
00336                           const AssocVector<K, V, C, A>& rhs)
00337     { return rhs < lhs; }
00338 
00339     template <class K, class V, class C, class A>
00340     inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
00341                            const AssocVector<K, V, C, A>& rhs)
00342     { return !(lhs < rhs); }
00343 
00344     template <class K, class V, class C, class A>
00345     inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
00346                            const AssocVector<K, V, C, A>& rhs)
00347     { return !(rhs < lhs); }
00348 
00349 
00350     // specialized algorithms:
00351     template <class K, class V, class C, class A>
00352     void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
00353     { lhs.swap(rhs); }
00354     
00355 } // namespace Loki
00356 
00357 #endif // end file guardian
00358 

Generated on Sun Feb 25 16:52:20 2007 for Loki by  doxygen 1.5.1-p1