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.
00014 ////////////////////////////////////////////////////////////////////////////////
00015 
00016 #ifndef ASSOCVECTOR_INC_
00017 #define ASSOCVECTOR_INC_
00018 
00019 #include <algorithm>
00020 #include <functional>
00021 #include <vector>
00022 #include <utility>
00023 
00024 namespace Loki
00025 {
00026 ////////////////////////////////////////////////////////////////////////////////
00027 // class template AssocVectorCompare
00028 // Used by AssocVector
00029 ////////////////////////////////////////////////////////////////////////////////
00030 
00031     namespace Private
00032     {
00033         template <class Value, class C>
00034         class AssocVectorCompare : public C
00035         {
00036             typedef std::pair<typename C::first_argument_type, Value>
00037                 Data;
00038             typedef typename C::first_argument_type first_argument_type;
00039 
00040         public:
00041             AssocVectorCompare()
00042             {}
00043             
00044             AssocVectorCompare(const C& src) : C(src)
00045             {}
00046             
00047             bool operator()(const first_argument_type& lhs, 
00048                 const first_argument_type& rhs) const
00049             { return C::operator()(lhs, rhs); }
00050             
00051             bool operator()(const Data& lhs, const Data& rhs) const
00052             { return operator()(lhs.first, rhs.first); }
00053             
00054             bool operator()(const Data& lhs, 
00055                 const first_argument_type& rhs) const
00056             { return operator()(lhs.first, rhs); }
00057             
00058             bool operator()(const first_argument_type& lhs,
00059                 const Data& rhs) const
00060             { return operator()(lhs, rhs.first); }
00061         };
00062     }
00063 
00064 ////////////////////////////////////////////////////////////////////////////////
00065 // class template AssocVector
00066 // An associative vector built as a syntactic drop-in replacement for std::map
00067 // BEWARE: AssocVector doesn't respect all map's guarantees, the most important
00068 //     being:
00069 // * iterators are invalidated by insert and erase operations
00070 // * the complexity of insert/erase is O(N) not O(log N)
00071 // * value_type is std::pair<K, V> not std::pair<const K, V>
00072 // * iterators are random
00073 ////////////////////////////////////////////////////////////////////////////////
00074 
00075     template
00076     <
00077         class K,
00078         class V,
00079         class C = std::less<K>,
00080         class A = std::allocator< std::pair<K, V> >
00081     >
00082     class AssocVector 
00083         : private std::vector< std::pair<K, V>, A >
00084         , private Private::AssocVectorCompare<V, C>
00085     {
00086         typedef std::vector<std::pair<K, V>, A> Base;
00087         typedef Private::AssocVectorCompare<V, C> MyCompare;
00088 
00089     public:
00090         typedef K key_type;
00091         typedef V mapped_type;
00092         typedef typename Base::value_type value_type;
00093 
00094         typedef C key_compare;
00095         typedef A allocator_type;
00096         typedef typename A::reference reference;
00097         typedef typename A::const_reference const_reference;
00098         typedef typename Base::iterator iterator;
00099         typedef typename Base::const_iterator const_iterator;
00100         typedef typename Base::size_type size_type;
00101         typedef typename Base::difference_type difference_type;
00102         typedef typename A::pointer pointer;
00103         typedef typename A::const_pointer const_pointer;
00104         typedef typename Base::reverse_iterator reverse_iterator;
00105         typedef typename Base::const_reverse_iterator const_reverse_iterator;
00106 
00107         class value_compare
00108             : public std::binary_function<value_type, value_type, bool>
00109             , private key_compare
00110         {
00111             friend class AssocVector;
00112         
00113         protected:
00114             value_compare(key_compare pred) : key_compare(pred)
00115             {}
00116 
00117         public:
00118             bool operator()(const value_type& lhs, const value_type& rhs) const
00119             { return key_compare::operator()(lhs.first, rhs.first); }
00120         };
00121         
00122         // 23.3.1.1 construct/copy/destroy
00123 
00124         explicit AssocVector(const key_compare& comp = key_compare(), 
00125             const A& alloc = A())
00126         : Base(alloc), MyCompare(comp)
00127         {}
00128         
00129         template <class InputIterator>
00130         AssocVector(InputIterator first, InputIterator last, 
00131             const key_compare& comp = key_compare(), 
00132             const A& alloc = A())
00133         : Base(first, last, alloc), MyCompare(comp)
00134         {
00135             MyCompare& me = *this;
00136             std::sort(begin(), end(), me);
00137         }
00138         
00139         AssocVector& operator=(const AssocVector& rhs)
00140         { 
00141             AssocVector(rhs).swap(*this); 
00142             return *this;
00143         }
00144 
00145         // iterators:
00146         // The following are here because MWCW gets 'using' wrong
00147         iterator begin() { return Base::begin(); }
00148         const_iterator begin() const { return Base::begin(); }
00149         iterator end() { return Base::end(); }
00150         const_iterator end() const { return Base::end(); }
00151         reverse_iterator rbegin() { return Base::rbegin(); }
00152         const_reverse_iterator rbegin() const { return Base::rbegin(); }
00153         reverse_iterator rend() { return Base::rend(); }
00154         const_reverse_iterator rend() const { return Base::rend(); }
00155         
00156         // capacity:
00157         bool empty() const { return Base::empty(); }
00158         size_type size() const { return Base::size(); }
00159         size_type max_size() { return Base::max_size(); }
00160 
00161         // 23.3.1.2 element access:
00162         mapped_type& operator[](const key_type& key)
00163         { return insert(value_type(key, mapped_type())).first->second; }
00164 
00165         // modifiers:
00166         std::pair<iterator, bool> insert(const value_type& val)
00167         {
00168             bool found(true);
00169             iterator i(lower_bound(val.first));
00170 
00171             if (i == end() || this->operator()(val.first, i->first))
00172             {
00173                 i = Base::insert(i, val);
00174                 found = false;
00175             }
00176             return std::make_pair(i, !found);
00177         }
00178 
00179         iterator insert(iterator pos, const value_type& val)
00180         {
00181             if (pos != end() && this->operator()(*pos, val) &&
00182                 (pos == end() - 1 ||
00183                     !this->operator()(val, pos[1]) &&
00184                         this->operator()(pos[1], val)))
00185             {
00186                 return Base::insert(pos, val);
00187             }
00188             return insert(val).first;
00189         }
00190        
00191         template <class InputIterator>
00192         void insert(InputIterator first, InputIterator last)
00193         { for (; first != last; ++first) insert(*first); }
00194         
00195         void erase(iterator pos)
00196         { Base::erase(pos); }
00197 
00198         size_type erase(const key_type& k)
00199         {
00200             iterator i(find(k));
00201             if (i == end()) return 0;
00202             erase(i);
00203             return 1;
00204         }
00205 
00206         void erase(iterator first, iterator last)
00207         { Base::erase(first, last); }
00208 
00209         void swap(AssocVector& other)
00210         {
00211             using std::swap;
00212             Base::swap(other);
00213             MyCompare& me = *this;
00214             MyCompare& rhs = other;
00215             swap(me, rhs);
00216         }
00217         
00218         void clear()
00219         { Base::clear(); }
00220 
00221         // observers:
00222         key_compare key_comp() const
00223         { return *this; }
00224 
00225         value_compare value_comp() const
00226         {
00227             const key_compare& comp = *this;
00228             return value_compare(comp);
00229         }
00230 
00231         // 23.3.1.3 map operations:
00232         iterator find(const key_type& k)
00233         {
00234             iterator i(lower_bound(k));
00235             if (i != end() && this->operator()(k, i->first))
00236             {
00237                 i = end();
00238             }
00239             return i;
00240         }
00241 
00242         const_iterator find(const key_type& k) const
00243         {       
00244             const_iterator i(lower_bound(k));
00245             if (i != end() && this->operator()(k, i->first))
00246             {
00247                 i = end();
00248             }
00249             return i;
00250         }
00251 
00252         size_type count(const key_type& k) const
00253         { return find(k) != end(); }
00254 
00255         iterator lower_bound(const key_type& k)
00256         {
00257             MyCompare& me = *this;
00258             return std::lower_bound(begin(), end(), k, me);
00259         }
00260 
00261         const_iterator lower_bound(const key_type& k) const
00262         {
00263             const MyCompare& me = *this;
00264             return std::lower_bound(begin(), end(), k, me);
00265         }
00266 
00267         iterator upper_bound(const key_type& k)
00268         {
00269             MyCompare& me = *this;
00270             return std::upper_bound(begin(), end(), k, me);
00271         }
00272 
00273         const_iterator upper_bound(const key_type& k) const
00274         {
00275             const MyCompare& me = *this;
00276             return std::upper_bound(begin(), end(), k, me);
00277         }
00278 
00279         std::pair<iterator, iterator> equal_range(const key_type& k)
00280         {
00281             MyCompare& me = *this;
00282             return std::equal_range(begin(), end(), k, me);
00283         }
00284 
00285         std::pair<const_iterator, const_iterator> equal_range(
00286             const key_type& k) const
00287         {
00288             const MyCompare& me = *this;
00289             return std::equal_range(begin(), end(), k, me);
00290         }
00291         
00292         friend bool operator==(const AssocVector& lhs, const AssocVector& rhs)
00293         {
00294             const Base& me = lhs;
00295             return me == rhs;
00296         } 
00297 
00298         bool operator<(const AssocVector& rhs) const
00299         {
00300             const Base& me = *this;
00301             const Base& yo = rhs;
00302             return me < yo;
00303         } 
00304 
00305         friend bool operator!=(const AssocVector& lhs, const AssocVector& rhs)
00306         { return !(lhs == rhs); } 
00307 
00308         friend bool operator>(const AssocVector& lhs, const AssocVector& rhs)
00309         { return rhs < lhs; }
00310 
00311         friend bool operator>=(const AssocVector& lhs, const AssocVector& rhs)
00312         { return !(lhs < rhs); } 
00313 
00314         friend bool operator<=(const AssocVector& lhs, const AssocVector& rhs)
00315         { return !(rhs < lhs); }
00316     };
00317 
00318     // specialized algorithms:
00319     template <class K, class V, class C, class A>
00320     void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
00321     { lhs.swap(rhs); }
00322     
00323 } // namespace Loki
00324 
00325 ////////////////////////////////////////////////////////////////////////////////
00326 // Change log:
00327 // May 20,     2001: change operator= - credit due to Cristoph Koegl
00328 // June 11,    2001: remove paren in equal_range - credit due to Cristoph Koegl
00329 // June 20,    2001: ported by Nick Thurn to gcc 2.95.3. Kudos, Nick!!!
00330 // January 22, 2002: fixed operator= - credit due to Tom Hyer
00331 // June 25,    2002: fixed template insert() - credit due to Robert Minsk
00332 // June 27,    2002: fixed member swap() - credit due to David Brookman
00333 // February 2, 2003: fixed dependent names - credit due to Rani Sharoni
00334 ////////////////////////////////////////////////////////////////////////////////
00335 
00336 #endif // ASSOCVECTOR_INC_

Generated on Mon Dec 18 07:29:46 2006 for E-CELL C++ libraries (libecs and libemc) 3.1.105 by  doxygen 1.5.1