umap.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // umap.h
   7 //
   8
   9 #ifndef UMAP_H_45643F516E02A87A3DCEA5024052A6F5
  10 #define UMAP_H_45643F516E02A87A3DCEA5024052A6F5
  11
  12 #include "uvector.h"
  13 #include "ufunction.h"
  14
  15 namespace ustl {
  16
  17 /// \class map umap.h ustl.h
  18 /// \ingroup AssociativeContainers
  19 ///
  20 /// \brief A sorted associative container of pair<K,V>
  21 ///
  22 template <typename K, typename V>
  23 class map : public vector<pair<K,V> > {
  24 public:
  25     typedef K                                           key_type;
  26     typedef V                                           data_type;
  27     typedef const K&                                    const_key_ref;
  28     typedef const V&                                    const_data_ref;
  29     typedef const map<K,V>&                             rcself_t;
  30     typedef vector<pair<K,V> >                          base_class;
  31     typedef typename base_class::value_type             value_type;
  32     typedef typename base_class::size_type              size_type;
  33     typedef typename base_class::pointer                pointer;
  34     typedef typename base_class::const_pointer          const_pointer;
  35     typedef typename base_class::reference              reference;
  36     typedef typename base_class::const_reference        const_reference;
  37     typedef typename base_class::const_iterator         const_iterator;
  38     typedef typename base_class::iterator               iterator;
  39     typedef typename base_class::reverse_iterator       reverse_iterator;
  40     typedef typename base_class::const_reverse_iterator const_reverse_iterator;
  41     typedef pair<const_iterator,const_iterator>         const_range_t;
  42     typedef pair<iterator,iterator>                     range_t;
  43 public:
  44     inline                      map (void)                      : vector<pair<K,V> > () {}
  45     explicit inline             map (size_type n)               : vector<pair<K,V> > (n) {}
  46     inline                      map (rcself_t v)                : vector<pair<K,V> > (v) {}
  47     inline                      map (const_iterator i1, const_iterator i2) : vector<pair<K,V> >() { insert (i1, i2); }
  48     inline rcself_t             operator= (rcself_t v)          { base_class::operator= (v); return (*this); }
  49     inline const_data_ref       operator[] (const_key_ref i) const;
  50     data_type&                  operator[] (const_key_ref i);
  51     inline size_type            size (void) const               { return (base_class::size()); }
  52     inline iterator             begin (void)                    { return (base_class::begin()); }
  53     inline const_iterator       begin (void) const              { return (base_class::begin()); }
  54     inline iterator             end (void)                      { return (base_class::end()); }
  55     inline const_iterator       end (void) const                { return (base_class::end()); }
  56     inline void                 assign (const_iterator i1, const_iterator i2)   { clear(); insert (i1, i2); }
  57     inline void                 push_back (const_reference v)                   { insert (v); }
  58     inline const_iterator       find (const_key_ref k) const;
  59     inline iterator             find (const_key_ref k)  { return (const_cast<iterator> (const_cast<rcself_t>(*this).find (k))); }
  60     inline const_iterator       find_data (const_data_ref v, const_iterator first = NULL, const_iterator last = NULL) const;
  61     inline iterator             find_data (const_data_ref v, iterator first = NULL, iterator last = NULL);
  62     iterator                    insert (const_reference v);
  63     void                        insert (const_iterator i1, const_iterator i2);
  64     inline void                 erase (const_key_ref k);
  65     inline iterator             erase (iterator ep)     { return (base_class::erase (ep)); }
  66     inline iterator             erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); }
  67     inline void                 clear (void)            { base_class::clear(); }
  68 private:
  69     const_iterator              lower_bound (const_key_ref k) const;
  70     inline iterator             lower_bound (const_key_ref k) { return (const_cast<iterator>(const_cast<rcself_t>(*this).lower_bound (k))); }
  71 };
  72
  73 template <typename K, typename V>
  74 typename map<K,V>::const_iterator map<K,V>::lower_bound (const_key_ref k) const
  75 {
  76     const_iterator first (begin()), last (end());
  77     while (first != last) {
  78         const_iterator mid = advance (first, distance (first,last) / 2);
  79         if (mid->first < k)
  80             first = advance (mid, 1);
  81         else
  82             last = mid;
  83     }
  84     return (first);
  85 }
  86
  87 /// Returns the pair<K,V> where K = \p k.
  88 template <typename K, typename V>
  89 inline typename map<K,V>::const_iterator map<K,V>::find (const_key_ref k) const
  90 {
  91     const_iterator i = lower_bound (k);
  92     return ((i < end() && k < i->first) ? end() : i);
  93 }
  94
  95 /// Returns the pair<K,V> where V = \p v, occuring in range [first,last).
  96 template <typename K, typename V>
  97 inline typename map<K,V>::const_iterator map<K,V>::find_data (const_data_ref v, const_iterator first, const_iterator last) const
  98 {
  99     if (!first) first = begin();
 100     if (!last) last = end();
 101     for (; first != last && first->second != v; ++first);
 102     return (first);
 103 }
 104
 105 /// Returns the pair<K,V> where V = \p v, occuring in range [first,last).
 106 template <typename K, typename V>
 107 inline typename map<K,V>::iterator map<K,V>::find_data (const_data_ref v, iterator first, iterator last)
 108 {
 109     return (const_cast<iterator> (find_data (v, const_cast<const_iterator>(first), const_cast<const_iterator>(last))));
 110 }
 111
 112 /// Returns data associated with key \p k.
 113 template <typename K, typename V>
 114 inline const typename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k) const
 115 {
 116     assert (find(k) != end() && "operator[] const can not insert non-existent keys");
 117     return (find(k)->second);
 118 }
 119
 120 /// Returns data associated with key \p k.
 121 template <typename K, typename V>
 122 typename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k)
 123 {
 124     iterator ip = lower_bound (k);
 125     if (ip == end() || k < ip->first)
 126         ip = base_class::insert (ip, make_pair (k, V()));
 127     return (ip->second);
 128 }
 129
 130 /// Inserts the pair into the container.
 131 template <typename K, typename V>
 132 typename map<K,V>::iterator map<K,V>::insert (const_reference v)
 133 {
 134     iterator ip = lower_bound (v.first);
 135     if (ip == end() || v.first < ip->first)
 136         ip = base_class::insert (ip, v);
 137     else
 138         *ip = v;
 139     return (ip);
 140 }
 141
 142 /// Inserts elements from range [i1,i2) into the container.
 143 template <typename K, typename V>
 144 void map<K,V>::insert (const_iterator i1, const_iterator i2)
 145 {
 146     assert (i1 <= i2);
 147     reserve (size() + distance (i1, i2));
 148     for (; i1 != i2; ++i1)
 149         insert (*i1);
 150 }
 151
 152 /// Erases the element with key value \p k.
 153 template <typename K, typename V>
 154 inline void map<K,V>::erase (const_key_ref k)
 155 {
 156     iterator ip = find (k);
 157     if (ip != end())
 158         erase (ip);
 159 }
 160
 161 } // namespace ustl
 162
 163 #endif
 164