LCOV - code coverage report
Current view: top level - include/crpropa - AssocVector.h (source / functions) Hit Total Coverage
Test: coverage.info.cleaned Lines: 21 21 100.0 %
Date: 2024-04-29 14:43:01 Functions: 5 5 100.0 %

          Line data    Source code
       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             : //
       8             : // Permission is hereby granted, free of charge, to any person obtaining a copy
       9             : // of this software and associated documentation files (the "Software"), to deal
      10             : // in the Software without restriction, including without limitation the rights
      11             : // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      12             : // copies of the Software, and to permit persons to whom the Software is
      13             : // furnished to do so, subject to the following conditions:
      14             : //
      15             : // The above copyright notice and this permission notice shall be included in
      16             : // all copies or substantial portions of the Software.
      17             : //
      18             : // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      19             : // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      20             : // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      21             : // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      22             : // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      23             : // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
      24             : // SOFTWARE.
      25             : ////////////////////////////////////////////////////////////////////////////////
      26             : #ifndef LOKI_ASSOCVECTOR_INC_
      27             : #define LOKI_ASSOCVECTOR_INC_
      28             : 
      29             : // $Id$
      30             : 
      31             : 
      32             : #include <algorithm>
      33             : #include <functional>
      34             : #include <vector>
      35             : #include <utility>
      36             : #include <iterator>
      37             : #include <map>
      38             : 
      39             : 
      40             : namespace Loki
      41             : {
      42             : ////////////////////////////////////////////////////////////////////////////////
      43             : // class template AssocVectorCompare
      44             : // Used by AssocVector
      45             : ////////////////////////////////////////////////////////////////////////////////
      46             : 
      47             :     namespace Private
      48             :     {
      49             :         template <class Value, class C>
      50             :         class AssocVectorCompare : public C
      51             :         {
      52             :             typedef std::pair<typename C::first_argument_type, Value>
      53             :                 Data;
      54             :             typedef typename C::first_argument_type first_argument_type;
      55             : 
      56             :         public:
      57             :             AssocVectorCompare()
      58             :             {}
      59             : 
      60             :             AssocVectorCompare(const C& src) : C(src)
      61             :             {}
      62             : 
      63             :             bool operator()(const first_argument_type& lhs,
      64             :                 const first_argument_type& rhs) const
      65             :             { return C::operator()(lhs, rhs); }
      66             : 
      67             :             bool operator()(const Data& lhs, const Data& rhs) const
      68             :             { return operator()(lhs.first, rhs.first); }
      69             : 
      70             :             bool operator()(const Data& lhs,
      71             :                 const first_argument_type& rhs) const
      72          57 :             { return operator()(lhs.first, rhs); }
      73             : 
      74             :             bool operator()(const first_argument_type& lhs,
      75             :                 const Data& rhs) const
      76             :             { return operator()(lhs, rhs.first); }
      77             :         };
      78             :     }
      79             : 
      80             : ////////////////////////////////////////////////////////////////////////////////
      81             : // class template AssocVector
      82             : // An associative vector built as a syntactic drop-in replacement for std::map
      83             : // BEWARE: AssocVector doesn't respect all map's guarantees, the most important
      84             : //     being:
      85             : // * iterators are invalidated by insert and erase operations
      86             : // * the complexity of insert/erase is O(N) not O(log N)
      87             : // * value_type is std::pair<K, V> not std::pair<const K, V>
      88             : // * iterators are random
      89             : ////////////////////////////////////////////////////////////////////////////////
      90             : 
      91             : 
      92             :     template
      93             :     <
      94             :         class K,
      95             :         class V,
      96             :         class C = std::less<K>,
      97             :         class A = std::allocator< std::pair<K, V> >
      98             :     >
      99          30 :     class AssocVector
     100             :         : private std::vector< std::pair<K, V>, A >
     101             :         , private Private::AssocVectorCompare<V, C>
     102             :     {
     103             :         typedef std::vector<std::pair<K, V>, A> Base;
     104             :         typedef Private::AssocVectorCompare<V, C> MyCompare;
     105             : 
     106             :     public:
     107             :         typedef K key_type;
     108             :         typedef V mapped_type;
     109             :         typedef typename Base::value_type value_type;
     110             : 
     111             :         typedef C key_compare;
     112             :         typedef A allocator_type;
     113             :         typedef typename A::reference reference;
     114             :         typedef typename A::const_reference const_reference;
     115             :         typedef typename Base::iterator iterator;
     116             :         typedef typename Base::const_iterator const_iterator;
     117             :         typedef typename Base::size_type size_type;
     118             :         typedef typename Base::difference_type difference_type;
     119             :         typedef typename A::pointer pointer;
     120             :         typedef typename A::const_pointer const_pointer;
     121             :         typedef typename Base::reverse_iterator reverse_iterator;
     122             :         typedef typename Base::const_reverse_iterator const_reverse_iterator;
     123             : 
     124             :         class value_compare
     125             :             : public std::binary_function<value_type, value_type, bool>
     126             :             , private key_compare
     127             :         {
     128             :             friend class AssocVector;
     129             : 
     130             :         protected:
     131             :             value_compare(key_compare pred) : key_compare(pred)
     132             :             {}
     133             : 
     134             :         public:
     135             :             bool operator()(const value_type& lhs, const value_type& rhs) const
     136             :             { return key_compare::operator()(lhs.first, rhs.first); }
     137             :         };
     138             : 
     139             :         // 23.3.1.1 construct/copy/destroy
     140             : 
     141             :         explicit AssocVector(const key_compare& comp = key_compare(),
     142             :             const A& alloc = A())
     143             :         : Base(alloc), MyCompare(comp)
     144             :         {}
     145             : 
     146             :         template <class InputIterator>
     147             :         AssocVector(InputIterator first, InputIterator last,
     148             :             const key_compare& comp = key_compare(),
     149             :             const A& alloc = A())
     150             :         : Base( alloc ), MyCompare( comp )
     151             :         {
     152             :             typedef ::std::vector< ::std::pair< K, V >, A > BaseType;
     153             :             typedef ::std::map< K, V, C, A > TempMap;
     154             :             typedef ::std::back_insert_iterator< Base > MyInserter;
     155             :             MyCompare & me = *this;
     156             :             const A tempAlloc;
     157             :             // Make a temporary map similar to this type to prevent any duplicate elements.
     158             :             TempMap temp( first, last, me, tempAlloc );
     159             :             Base::reserve( temp.size() );
     160             :             BaseType & target = static_cast< BaseType & >( *this );
     161             :             MyInserter myInserter = ::std::back_inserter( target );
     162             :             ::std::copy( temp.begin(), temp.end(), myInserter );
     163             :         }
     164             : 
     165          30 :         AssocVector& operator=(const AssocVector& rhs)
     166             :         {
     167          30 :             AssocVector(rhs).swap(*this);
     168          30 :             return *this;
     169             :         }
     170             : 
     171             :         // iterators:
     172             :         // The following are here because MWCW gets 'using' wrong
     173             :         iterator begin() { return Base::begin(); }
     174             :         const_iterator begin() const { return Base::begin(); }
     175             :         iterator end() { return Base::end(); }
     176             :         const_iterator end() const { return Base::end(); }
     177             :         reverse_iterator rbegin() { return Base::rbegin(); }
     178             :         const_reverse_iterator rbegin() const { return Base::rbegin(); }
     179             :         reverse_iterator rend() { return Base::rend(); }
     180             :         const_reverse_iterator rend() const { return Base::rend(); }
     181             : 
     182             :         // capacity:
     183             :         bool empty() const { return Base::empty(); }
     184             :         size_type size() const { return Base::size(); }
     185             :         size_type max_size() { return Base::max_size(); }
     186             : 
     187             :         // 23.3.1.2 element access:
     188        1143 :         mapped_type& operator[](const key_type& key)
     189        1143 :         { return insert(value_type(key, mapped_type())).first->second; }
     190             : 
     191             :         // modifiers:
     192        1143 :         std::pair<iterator, bool> insert(const value_type& val)
     193             :         {
     194             :             bool found(true);
     195        1143 :             iterator i(lower_bound(val.first));
     196             : 
     197          13 :             if (i == end() || this->operator()(val.first, i->first))
     198             :             {
     199        1134 :                 i = Base::insert(i, val);
     200             :                 found = false;
     201             :             }
     202        1143 :             return std::make_pair(i, !found);
     203             :         }
     204             :         //Section [23.1.2], Table 69
     205             :         //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
     206             :         iterator insert(iterator pos, const value_type& val)
     207             :         {
     208             :             if( (pos == begin() || this->operator()(*(pos-1),val)) &&
     209             :                 (pos == end()    || this->operator()(val, *pos)) )
     210             :             {
     211             :                 return Base::insert(pos, val);
     212             :             }
     213             :             return insert(val).first;
     214             :         }
     215             : 
     216             :         template <class InputIterator>
     217             :         void insert(InputIterator first, InputIterator last)
     218             :         { for (; first != last; ++first) insert(*first); }
     219             : 
     220             :         void erase(iterator pos)
     221           5 :         { Base::erase(pos); }
     222             : 
     223             :         size_type erase(const key_type& k)
     224             :         {
     225             :             iterator i(find(k));
     226             :             if (i == end()) return 0;
     227             :             erase(i);
     228             :             return 1;
     229             :         }
     230             : 
     231             :         void erase(iterator first, iterator last)
     232             :         { Base::erase(first, last); }
     233             : 
     234             :         void swap(AssocVector& other)
     235             :         {
     236             :             Base::swap(other);
     237             :             MyCompare& me = *this;
     238             :             MyCompare& rhs = other;
     239             :             std::swap(me, rhs);
     240             :         }
     241             : 
     242             :         void clear()
     243             :         { Base::clear(); }
     244             : 
     245             :         // observers:
     246             :         key_compare key_comp() const
     247             :         { return *this; }
     248             : 
     249             :         value_compare value_comp() const
     250             :         {
     251             :             const key_compare& comp = *this;
     252             :             return value_compare(comp);
     253             :         }
     254             : 
     255             :         // 23.3.1.3 map operations:
     256           5 :         iterator find(const key_type& k)
     257             :         {
     258             :             iterator i(lower_bound(k));
     259           5 :             if (i != end() && this->operator()(k, i->first))
     260             :             {
     261             :                 i = end();
     262             :             }
     263           5 :             return i;
     264             :         }
     265             : 
     266          41 :         const_iterator find(const key_type& k) const
     267             :         {
     268             :             const_iterator i(lower_bound(k));
     269          33 :             if (i != end() && this->operator()(k, i->first))
     270             :             {
     271             :                 i = end();
     272             :             }
     273          41 :             return i;
     274             :         }
     275             : 
     276             :         size_type count(const key_type& k) const
     277             :         { return find(k) != end(); }
     278             : 
     279             :         iterator lower_bound(const key_type& k)
     280             :         {
     281             :             MyCompare& me = *this;
     282        1148 :             return std::lower_bound(begin(), end(), k, me);
     283             :         }
     284             : 
     285             :         const_iterator lower_bound(const key_type& k) const
     286             :         {
     287             :             const MyCompare& me = *this;
     288          41 :             return std::lower_bound(begin(), end(), k, me);
     289             :         }
     290             : 
     291             :         iterator upper_bound(const key_type& k)
     292             :         {
     293             :             MyCompare& me = *this;
     294             :             return std::upper_bound(begin(), end(), k, me);
     295             :         }
     296             : 
     297             :         const_iterator upper_bound(const key_type& k) const
     298             :         {
     299             :             const MyCompare& me = *this;
     300             :             return std::upper_bound(begin(), end(), k, me);
     301             :         }
     302             : 
     303             :         std::pair<iterator, iterator> equal_range(const key_type& k)
     304             :         {
     305             :             MyCompare& me = *this;
     306             :             return std::equal_range(begin(), end(), k, me);
     307             :         }
     308             : 
     309             :         std::pair<const_iterator, const_iterator> equal_range(
     310             :             const key_type& k) const
     311             :         {
     312             :             const MyCompare& me = *this;
     313             :             return std::equal_range(begin(), end(), k, me);
     314             :         }
     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             :         bool operator<(const AssocVector& rhs) const
     321             :         {
     322             :             const Base& me = *this;
     323             :             const Base& yo = rhs;
     324             :             return me < yo;
     325             :         }
     326             : 
     327             :         template <class K1, class V1, class C1, class A1>
     328             :         friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
     329             :                                const AssocVector<K1, V1, C1, A1>& rhs);
     330             : 
     331             :         template <class K1, class V1, class C1, class A1>
     332             :         friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
     333             :                               const AssocVector<K1, V1, C1, A1>& rhs);
     334             : 
     335             :         template <class K1, class V1, class C1, class A1>
     336             :         friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
     337             :                                const AssocVector<K1, V1, C1, A1>& rhs);
     338             : 
     339             :         template <class K1, class V1, class C1, class A1>
     340             :         friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
     341             :                                const AssocVector<K1, V1, C1, A1>& rhs);
     342             :     };
     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             :     {
     348             :       const std::vector<std::pair<K, V>, A>& me = lhs;
     349             :       return me == rhs;
     350             :     }
     351             : 
     352             :     template <class K, class V, class C, class A>
     353             :     inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
     354             :                            const AssocVector<K, V, C, A>& rhs)
     355             :     { return !(lhs == rhs); }
     356             : 
     357             :     template <class K, class V, class C, class A>
     358             :     inline bool operator>(const AssocVector<K, V, C, A>& lhs,
     359             :                           const AssocVector<K, V, C, A>& rhs)
     360             :     { return rhs < lhs; }
     361             : 
     362             :     template <class K, class V, class C, class A>
     363             :     inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
     364             :                            const AssocVector<K, V, C, A>& rhs)
     365             :     { return !(lhs < rhs); }
     366             : 
     367             :     template <class K, class V, class C, class A>
     368             :     inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
     369             :                            const AssocVector<K, V, C, A>& rhs)
     370             :     { return !(rhs < lhs); }
     371             : 
     372             : 
     373             :     // specialized algorithms:
     374             :     template <class K, class V, class C, class A>
     375             :     void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
     376             :     { lhs.swap(rhs); }
     377             : 
     378             : } // namespace Loki
     379             : 
     380             : #endif // end file guardian
     381             : 

Generated by: LCOV version 1.14