16 template<
typename Tkey,
typename Tvalue,
typename Tcompare>
27 template<
class Tmap_iter,
class Tlist_iter,
class Tkey,
class Tvalue,
class Tcompare>
30 friend class MultiMap<Tkey, Tvalue, Tcompare>;
59 template<
class Tnon_const>
71 this->list_valid = (this->list_iter != this->map_iter->second.begin());
80 template<
class Tnon_const>
84 this->list_valid =
false;
95 assert(!this->map_iter->second.empty());
96 return this->list_valid ?
97 this->list_iter.operator*() :
98 this->map_iter->second.begin().operator*();
107 assert(!this->map_iter->second.empty());
108 return this->list_valid ?
109 this->list_iter.operator->() :
110 this->map_iter->second.begin().operator->();
113 inline const Tmap_iter &GetMapIter()
const {
return this->
map_iter; }
114 inline const Tlist_iter &GetListIter()
const {
return this->
list_iter; }
115 inline bool ListValid()
const {
return this->
list_valid; }
117 const Tkey &GetKey()
const {
return this->map_iter->first; }
127 assert(!this->map_iter->second.empty());
128 if (this->list_valid) {
129 if (++this->list_iter == this->map_iter->second.end()) {
131 this->list_valid =
false;
134 this->list_iter = ++(this->map_iter->second.begin());
135 if (this->list_iter == this->map_iter->second.end()) {
138 this->list_valid =
true;
164 assert(!this->map_iter->second.empty());
165 if (!this->list_valid) {
167 this->list_iter = this->map_iter->second.end();
168 assert(!this->map_iter->second.empty());
171 this->list_valid = (--this->list_iter != this->map_iter->second.begin());
202 template<
class Tmap_iter1,
class Tlist_iter1,
class Tmap_iter2,
class Tlist_iter2,
class Tkey,
class Tvalue1,
class Tvalue2,
class Tcompare>
205 if (iter1.GetMapIter() != iter2.GetMapIter())
return false;
206 if (!iter1.ListValid())
return !iter2.ListValid();
207 return iter2.ListValid() ?
208 iter1.GetListIter() == iter2.GetListIter() :
false;
219 template<
class Tmap_iter1,
class Tlist_iter1,
class Tmap_iter2,
class Tlist_iter2,
class Tkey,
class Tvalue1,
class Tvalue2,
class Tcompare>
222 return !(iter1 == iter2);
233 template<
class Tmap_iter1,
class Tlist_iter1,
class Tmap_iter2,
class Tkey,
class Tvalue,
class Tcompare >
236 return !iter1.ListValid() && iter1.GetMapIter() == iter2;
245 template<
class Tmap_iter1,
class Tlist_iter1,
class Tmap_iter2,
class Tkey,
class Tvalue,
class Tcompare >
248 return iter1.ListValid() || iter1.GetMapIter() != iter2;
257 template<
class Tmap_iter1,
class Tlist_iter1,
class Tmap_iter2,
class Tkey,
class Tvalue,
class Tcompare >
260 return !iter1.ListValid() && iter1.GetMapIter() == iter2;
269 template<
class Tmap_iter1,
class Tlist_iter1,
class Tmap_iter2,
class Tkey,
class Tvalue,
class Tcompare >
272 return iter1.ListValid() || iter1.GetMapIter() != iter2;
283 template<
typename Tkey,
typename Tvalue,
typename Tcompare = std::less<Tkey> >
284 class MultiMap :
public std::map<Tkey, std::list<Tvalue>, Tcompare > {
286 typedef typename std::list<Tvalue> List;
287 typedef typename List::iterator ListIterator;
288 typedef typename List::const_iterator ConstListIterator;
290 typedef typename std::map<Tkey, List, Tcompare > Map;
291 typedef typename Map::iterator MapIterator;
292 typedef typename Map::const_iterator ConstMapIterator;
305 assert(!list.empty());
315 list.erase(list.begin());
316 if (list.empty()) this->Map::erase(it.
map_iter++);
326 void Insert(
const Tkey &key,
const Tvalue &val)
328 List &list = (*this)[key];
330 assert(!list.empty());
340 for (ConstMapIterator it = this->Map::begin(); it != this->Map::end(); ++it) {
341 ret += it->second.size();
352 return this->Map::size();
362 MapIterator begin(this->lower_bound(key));
363 if (begin != this->Map::end() && begin->first == key) {
364 MapIterator end = begin;
365 return std::make_pair(begin, ++end);
367 return std::make_pair(begin, begin);
375 std::pair<const_iterator, const_iterator>
equal_range(
const Tkey &key)
const
377 ConstMapIterator begin(this->lower_bound(key));
378 if (begin != this->Map::end() && begin->first == key) {
379 ConstMapIterator end = begin;
380 return std::make_pair(begin, ++end);
382 return std::make_pair(begin, begin);