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 "uassert.h" 13#include "ufunction.h" 14#include "uvector.h" 15 16namespace ustl { 17 18/// \class multimap umultimap.h ustl.h 19/// \ingroup AssociativeContainers 20/// 21/// \brief A sorted associative container that may container multiple entries for each key. 22/// 23template <typename K, typename V> 24class multimap : public vector<pair<K,V> > { 25public: 26 typedef K key_type; 27 typedef V data_type; 28 typedef const K& const_key_ref; 29 typedef const V& const_data_ref; 30 typedef const multimap<K,V>& rcself_t; 31 typedef vector<pair<K,V> > base_class; 32 typedef typename base_class::value_type value_type; 33 typedef typename base_class::size_type size_type; 34 typedef typename base_class::pointer pointer; 35 typedef typename base_class::const_pointer const_pointer; 36 typedef typename base_class::reference reference; 37 typedef typename base_class::const_reference const_reference; 38 typedef typename base_class::const_iterator const_iterator; 39 typedef typename base_class::iterator iterator; 40 typedef typename base_class::reverse_iterator reverse_iterator; 41 typedef typename base_class::const_reverse_iterator const_reverse_iterator; 42 typedef pair<const_iterator,const_iterator> const_range_t; 43 typedef pair<iterator,iterator> range_t; 44public: 45 inline multimap (void) : vector<pair<K,V> > () {} 46 explicit inline multimap (size_type n) : vector<pair<K,V> > (n) {} 47 inline multimap (rcself_t v) : vector<pair<K,V> > (v) {} 48 inline multimap (const_iterator i1, const_iterator i2) : vector<pair<K,V> > () { insert (i1, i2); } 49 inline rcself_t operator= (rcself_t v) { base_class::operator= (v); return (*this); } 50 inline size_type size (void) const { return (base_class::size()); } 51 inline iterator begin (void) { return (base_class::begin()); } 52 inline const_iterator begin (void) const { return (base_class::begin()); } 53 inline iterator end (void) { return (base_class::end()); } 54 inline const_iterator end (void) const { return (base_class::end()); } 55 inline void assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); } 56 inline size_type count (const_key_ref k) const { return (upper_bound(k) - lower_bound(k)); } 57 inline void push_back (const_reference v) { insert (v); } 58 inline const_range_t equal_range (const_key_ref k) const { return (make_pair (lower_bound(k), upper_bound(k))); } 59 inline range_t equal_range (const_key_ref k) { return (make_pair (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(k)))); } 60 const_iterator lower_bound (const_key_ref k) const; 61 const_iterator upper_bound (const_key_ref k) const; 62 inline iterator insert (const_reference v); 63 void insert (const_iterator i1, const_iterator i2); 64 inline void erase (const_key_ref k) { erase (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(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}; 69 70/// Returns an iterator to the first element with key value \p k. 71template <typename K, typename V> 72typename multimap<K,V>::const_iterator multimap<K,V>::lower_bound (const_key_ref k) const 73{ 74 const_iterator first (begin()), last (end()); 75 while (first != last) { 76 const_iterator mid = advance (first, distance (first,last) / 2); 77 if (mid->first < k) 78 first = advance (mid, 1); 79 else 80 last = mid; 81 } 82 return (first); 83} 84 85/// Returns an iterator to the first element with key value \p k. 86template <typename K, typename V> 87typename multimap<K,V>::const_iterator multimap<K,V>::upper_bound (const_key_ref k) const 88{ 89 const_iterator first (begin()), last (end()); 90 while (first != last) { 91 const_iterator mid = advance (first, distance (first,last) / 2); 92 if (k < mid->first) 93 last = mid; 94 else 95 first = advance (mid, 1); 96 } 97 return (last); 98} 99 100/// Inserts the pair into the container. 101template <typename K, typename V> 102inline typename multimap<K,V>::iterator multimap<K,V>::insert (const_reference v) 103{ 104 iterator ip = const_cast<iterator> (upper_bound (v.first)); 105 return (base_class::insert (ip, v)); 106} 107 108/// Inserts elements from range [i1,i2) into the container. 109template <typename K, typename V> 110void multimap<K,V>::insert (const_iterator i1, const_iterator i2) 111{ 112 assert (i1 <= i2); 113 reserve (size() + distance (i1, i2)); 114 for (; i1 != i2; ++i1) 115 insert (*i1); 116} 117 118} // namespace ustl 119 120#endif 121 122