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 "uassert.h" 13#include "ufunction.h" 14#include "uvector.h" 15 16namespace ustl { 17 18/// \class map umap.h ustl.h 19/// \ingroup AssociativeContainers 20/// 21/// \brief A sorted associative container of pair<K,V> 22/// 23template <typename K, typename V> 24class map : 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 map<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 map (void) : vector<pair<K,V> > () {} 46 explicit inline map (size_type n) : vector<pair<K,V> > (n) {} 47 inline map (rcself_t v) : vector<pair<K,V> > (v) {} 48 inline map (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 const_data_ref operator[] (const_key_ref i) const; 51 data_type& operator[] (const_key_ref i); 52 inline size_type size (void) const { return (base_class::size()); } 53 inline iterator begin (void) { return (base_class::begin()); } 54 inline const_iterator begin (void) const { return (base_class::begin()); } 55 inline iterator end (void) { return (base_class::end()); } 56 inline const_iterator end (void) const { return (base_class::end()); } 57 inline void assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); } 58 inline void push_back (const_reference v) { insert (v); } 59 inline const_iterator find (const_key_ref k) const; 60 inline iterator find (const_key_ref k) { return (const_cast<iterator> (const_cast<rcself_t>(*this).find (k))); } 61 inline const_iterator find_data (const_data_ref v, const_iterator first = NULL, const_iterator last = NULL) const; 62 inline iterator find_data (const_data_ref v, iterator first = NULL, iterator last = NULL); 63 iterator insert (const_reference v); 64 void insert (const_iterator i1, const_iterator i2); 65 inline void erase (const_key_ref k); 66 inline iterator erase (iterator ep) { return (base_class::erase (ep)); } 67 inline iterator erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); } 68 inline void clear (void) { base_class::clear(); } 69private: 70 const_iterator lower_bound (const_key_ref k) const; 71 inline iterator lower_bound (const_key_ref k) { return (const_cast<iterator>(const_cast<rcself_t>(*this).lower_bound (k))); } 72}; 73 74template <typename K, typename V> 75typename map<K,V>::const_iterator map<K,V>::lower_bound (const_key_ref k) const 76{ 77 const_iterator first (begin()), last (end()); 78 while (first != last) { 79 const_iterator mid = advance (first, distance (first,last) / 2); 80 if (mid->first < k) 81 first = advance (mid, 1); 82 else 83 last = mid; 84 } 85 return (first); 86} 87 88/// Returns the pair<K,V> where K = \p k. 89template <typename K, typename V> 90inline typename map<K,V>::const_iterator map<K,V>::find (const_key_ref k) const 91{ 92 const_iterator i = lower_bound (k); 93 return ((i < end() && k < i->first) ? end() : i); 94} 95 96/// Returns the pair<K,V> where V = \p v, occuring in range [first,last). 97template <typename K, typename V> 98inline typename map<K,V>::const_iterator map<K,V>::find_data (const_data_ref v, const_iterator first, const_iterator last) const 99{ 100 if (!first) first = begin(); 101 if (!last) last = end(); 102 for (; first != last && first->second != v; ++first); 103 return (first); 104} 105 106/// Returns the pair<K,V> where V = \p v, occuring in range [first,last). 107template <typename K, typename V> 108inline typename map<K,V>::iterator map<K,V>::find_data (const_data_ref v, iterator first, iterator last) 109{ 110 return (const_cast<iterator> (find_data (v, const_cast<const_iterator>(first), const_cast<const_iterator>(last)))); 111} 112 113/// Returns data associated with key \p k. 114template <typename K, typename V> 115inline const typename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k) const 116{ 117 assert (find(k) != end() && "operator[] const can not insert non-existent keys"); 118 return (find(k)->second); 119} 120 121/// Returns data associated with key \p k. 122template <typename K, typename V> 123typename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k) 124{ 125 iterator ip = lower_bound (k); 126 if (ip == end() || k < ip->first) 127 ip = base_class::insert (ip, make_pair (k, V())); 128 return (ip->second); 129} 130 131/// Inserts the pair into the container. 132template <typename K, typename V> 133typename map<K,V>::iterator map<K,V>::insert (const_reference v) 134{ 135 iterator ip = lower_bound (v.first); 136 if (ip == end() || v.first < ip->first) 137 ip = base_class::insert (ip, v); 138 else 139 *ip = v; 140 return (ip); 141} 142 143/// Inserts elements from range [i1,i2) into the container. 144template <typename K, typename V> 145void map<K,V>::insert (const_iterator i1, const_iterator i2) 146{ 147 assert (i1 <= i2); 148 reserve (size() + distance (i1, i2)); 149 for (; i1 != i2; ++i1) 150 insert (*i1); 151} 152 153/// Erases the element with key value \p k. 154template <typename K, typename V> 155inline void map<K,V>::erase (const_key_ref k) 156{ 157 iterator ip = find (k); 158 if (ip != end()) 159 erase (ip); 160} 161 162} // namespace ustl 163 164#endif 165 166