Re: ordered unordered_map
On Feb 3, 9:27 pm, Ralf Goertz <r_goe...@usenet.arcornews.de> wrote:
tonydee wrote:
On Feb 2, 10:30 pm, Ralf Goertz <r_goe...@usenet.arcornews.de> wrote:
Pete Becker wrote:
If you're willing to reorganize the container, how about going a sma=
ll
step further and replacing it at that point with an ordered containe=
r?
It seems I will have to do that then, thanks.
It's a good, simple solution in most cases. If the objects are large
and keys small and your RAM limited, and/or that final step is
performance critical too, consider
- keeping the data in an ordered map, but adding an unordered (hash)
map indexing from key to ordered-map iterator
- keep the data in a vector, and having unordered and ordered maps
from key to index
- looking at boost's multi-indexed container library, which can manage
the synchronisation of data and indices for you
These are worth trying, especially since I still need to find() in the
map. The reason why I want an ordered iterator is that I'd like to
compare all elements with each other and erase duplicate (type Foo)
values keeping the one with the lower (type unsigned) key (it is more
complicated than that but you get the point). So I use two nested loops:
typedef unordered_map<unsigned, Foo> Map;
typedef unordered_set<unsigned> Set;
Map m;
Map::iterator i1,i2;
Set s;
Set::iterator i3;
void find_elements_in_m_that_need_to_be_compared(unsigned to_this_element=
,Set&);
bool foo_equal(const Foo &,const Foo&);
for (i1=m.begin();i1!=m.end();++i1) {
find_elements_in_m_that_need_to_be_compared(i1->first,s);
for (i3=s.begin();i3!=s.end();++i3) {
i2=m.find(*i3);
if (foo_equal(i1->second,i2->second)) {
m.erase(i2); // (*)
}
}
}
Since m is not ordered, I cannot be sure that i1->first is less than
i2->first. Therefore I might erase the object with the lower key at (*).
OTOH unordered_map has an erase(iterator, iterator) member function.
This function seems to be of little use since the key 42 might be in the
range [8,15).
I'm not sure how often you need to "clean up" these duplicates, but if
Foo has (or can easily be given) a operator<, you may find it better
to have an (ordered) map (something like "std::map<Foo*, unsigned,
Compare_Via_Ptr<Foo*> >" with template <typename T> struct
Compare_Via_Ptr { bool operator()(const Foo* lhs, const Foo* rhs)
const { return *lhs < *rhs; } }; )...
That way you can do a quick lookup to see if an "incoming" Foo is
already stored, preventing the storage of duplicates.
Cheers,
Tony