26 #ifndef LIMBO_CONTAINERS_FASTMULTISET_H
27 #define LIMBO_CONTAINERS_FASTMULTISET_H
33 #include <boost/typeof.hpp>
50 template <
typename KeyType,
51 typename Compare1 = less<KeyType>,
52 typename Compare2 = less<KeyType> >
61 typedef Compare1 key_compare1;
62 typedef Compare2 key_compare2;
63 typedef multiset<key_type, key_compare1> base_type;
64 typedef map<key_type, typename base_type::iterator, key_compare2> map_type;
65 typedef typename map_type::value_type map_value_type;
67 typedef typename base_type::reference reference;
68 typedef typename base_type::const_reference const_reference;
69 typedef typename base_type::pointer pointer;
70 typedef typename base_type::const_pointer const_pointer;
71 typedef typename base_type::iterator iterator;
72 typedef typename base_type::const_iterator const_iterator;
73 typedef typename base_type::reverse_iterator reverse_iterator;
74 typedef typename base_type::const_reverse_iterator const_reverse_iterator;
75 typedef typename base_type::difference_type difference_type;
76 typedef typename base_type::size_type size_type;
83 key_compare2
const& comp2 = key_compare2())
84 : base_type(comp1),
m_map(comp2) {}
94 for (iterator it = this->begin();
95 it != this->end(); ++it)
96 m_map.insert(std::make_pair(*it, it));
102 virtual iterator
insert(key_type
const& val)
105 BOOST_AUTO(found,
m_map.find(val));
106 assert(found ==
m_map.end());
107 iterator it = this->base_type::insert(val);
115 virtual iterator
insert(iterator position, key_type
const& val)
118 BOOST_AUTO(found,
m_map.find(val));
119 assert(found ==
m_map.end());
120 iterator it = this->base_type::insert(position, val);
127 template <
typename InputIterator>
void insert(InputIterator first, InputIterator last);
132 virtual size_type
erase(key_type
const& val)
134 BOOST_AUTO(found,
m_map.find(val));
135 if (found ==
m_map.end())
return 0;
136 this->base_type::erase(found->second);
142 void erase(iterator position);
145 void erase(iterator first, iterator last);
150 virtual iterator
update(key_type
const& val)
152 BOOST_AUTO(found,
m_map.find(val));
154 if (found ==
m_map.end())
return this->end();
156 this->base_type::erase(found->second);
157 iterator it = this->base_type::insert(val);
160 return found->second;
166 virtual size_type
count(key_type
const& val)
const
168 return m_map.count(val);
173 virtual iterator
find(key_type
const& val)
const
175 BOOST_AUTO(found,
m_map.find(val));
176 if (found ==
m_map.end())
179 return found->second;
186 os <<
"/////////// FastMultiSet ////////////\n";
188 for (const_iterator it = this->begin();
189 it != this->end(); ++it)
192 for (BOOST_AUTO(it,
m_map.begin());
193 it !=
m_map.end(); ++it)
194 os << it->first <<
" --> " << *(it->second) << endl;
FastMultiSet(key_compare1 const &comp1=key_compare1(), key_compare2 const &comp2=key_compare2())
constructor
virtual size_type erase(key_type const &val)
erase value
FastMultiSet(FastMultiSet const &rhs)
copy constructor
void print(std::ostream &os) const
print object
virtual iterator find(key_type const &val) const
use m_map.find rather than std::multiset::find to have faster access
virtual iterator update(key_type const &val)
update value, the value is changed which means its position is not correct in the container ...
virtual size_type count(key_type const &val) const
use m_map.count rather than multiset::count to have faster access
friend std::ostream & operator<<(std::ostream &os, FastMultiSet const &rhs)
print object
map_type m_map
internal map
virtual iterator insert(key_type const &val)
insert value
virtual iterator insert(iterator position, key_type const &val)
insert value with hint of position
KeyType key_type
for set concept, value_type is also key_type
KeyType value_type
for set concept, key_type is also value_type