umultimap.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 // umultimap.h
   7 //
   8
   9 #ifndef UMULTIMAP_H_45743F516E02A87A3FCEA5024052A6F5
  10 #define UMULTIMAP_H_45743F516E02A87A3FCEA5024052A6F5
  11
  12 #include "uvector.h"
  13 #include "ufunction.h"
  14
  15 namespace ustl {
  16
  17 /// \class multimap umultimap.h ustl.h
  18 /// \ingroup AssociativeContainers
  19 ///
  20 /// \brief A sorted associative container that may container multiple entries for each key.
  21 ///
  22 template <typename K, typename V>
  23 class multimap : 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 multimap<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                      multimap (void)         : vector<pair<K,V> > () {}
  45     explicit inline             multimap (size_type n)  : vector<pair<K,V> > (n) {}
  46     inline                      multimap (rcself_t v)   : vector<pair<K,V> > (v) {}
  47     inline                      multimap (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 size_type            size (void) const       { return (base_class::size()); }
  50     inline iterator             begin (void)            { return (base_class::begin()); }
  51     inline const_iterator       begin (void) const      { return (base_class::begin()); }
  52     inline iterator             end (void)              { return (base_class::end()); }
  53     inline const_iterator       end (void) const        { return (base_class::end()); }
  54     inline void                 assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); }
  55     inline size_type            count (const_key_ref k) const           { return (upper_bound(k) - lower_bound(k)); }
  56     inline void                 push_back (const_reference v)           { insert (v); }
  57     inline const_range_t        equal_range (const_key_ref k) const     { return (make_pair (lower_bound(k), upper_bound(k))); }
  58     inline range_t              equal_range (const_key_ref k)           { return (make_pair (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(k)))); }
  59     const_iterator              lower_bound (const_key_ref k) const;
  60     const_iterator              upper_bound (const_key_ref k) const;
  61     inline iterator             insert (const_reference v);
  62     void                        insert (const_iterator i1, const_iterator i2);
  63     inline void                 erase (const_key_ref k)                 { erase (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(k))); }
  64     inline iterator             erase (iterator ep)                     { return (base_class::erase (ep)); }
  65     inline iterator             erase (iterator ep1, iterator ep2)      { return (base_class::erase (ep1, ep2)); }
  66     inline void                 clear (void)                            { base_class::clear(); }
  67 };
  68
  69 /// Returns an iterator to the first element with key value \p k.
  70 template <typename K, typename V>
  71 typename multimap<K,V>::const_iterator multimap<K,V>::lower_bound (const_key_ref k) const
  72 {
  73     const_iterator first (begin()), last (end());
  74     while (first != last) {
  75         const_iterator mid = advance (first, distance (first,last) / 2);
  76         if (mid->first < k)
  77             first = advance (mid, 1);
  78         else
  79             last = mid;
  80     }
  81     return (first);
  82 }
  83
  84 /// Returns an iterator to the first element with key value \p k.
  85 template <typename K, typename V>
  86 typename multimap<K,V>::const_iterator multimap<K,V>::upper_bound (const_key_ref k) const
  87 {
  88     const_iterator first (begin()), last (end());
  89     while (first != last) {
  90         const_iterator mid = advance (first, distance (first,last) / 2);
  91         if (k < mid->first)
  92             last = mid;
  93         else
  94             first = advance (mid, 1);
  95     }
  96     return (last);
  97 }
  98
  99 /// Inserts the pair into the container.
 100 template <typename K, typename V>
 101 inline typename multimap<K,V>::iterator multimap<K,V>::insert (const_reference v)
 102 {
 103     iterator ip = const_cast<iterator> (upper_bound (v.first));
 104     return (base_class::insert (ip, v));
 105 }
 106
 107 /// Inserts elements from range [i1,i2) into the container.
 108 template <typename K, typename V>
 109 void multimap<K,V>::insert (const_iterator i1, const_iterator i2)
 110 {
 111     assert (i1 <= i2);
 112     reserve (size() + distance (i1, i2));
 113     for (; i1 != i2; ++i1)
 114         insert (*i1);
 115 }
 116
 117 } // namespace ustl
 118
 119 #endif
 120