CODEWITHSUNDEEP
c++booststlassociative-array
rahman
rahman

Reputation: 4948

C++ associative container with two search criteria

I am looking for a container for storing my objects of a class, called Link, which has a member variable: "std::string linkID". the size of container can be as high as several milions, therefore fast look up is more preferred. 1-Later I need to look up the container using linkID 2-but, due to some reasons, the order in which the objects are added is also important.

I have gone through vector,list,set,map... and I am going to study muliset, multimap and boost multi index. But I guess,being new to C++, I still need some more experienced opinion to help me choose the best container based on the above two criteria.

Thank you vahid

Upvotes: 1

Views: 559

Answers (3)

Smittii
Smittii

Reputation: 187

For me this looks as a perfekt usecase for boost::multi_index_container

your type declaration should look similat to this (not tested)

typedef multi_index_container<
    Link,
    indexed_by<
        sequenced<>,
        ordered_unique< member< Link, std::string, &Link::linkID> >,
        ordered_unique< member< Link, std::string, &Link::linkID_2 > >
    >
> LinkList;
LinkList s;
s.push_back(Link(...));

It is in general the same as the solution posted by Frerich Raabe. But I think with less pitfalls and likely more optimized. Read the tutorial on the boost page to learn how to access the elements stored in s.

Your comment...

Actually, I am developing an already existing project where in, they have used std::vector for only STORING the elements(as you pointed out). so now can I use the 'storage' vector as is and just add the maps as you suggested?

This is not possible. Vector iterators stay not valid. They can become undefined when you add or remove elements to the vector.

Upvotes: 4

Frerich Raabe
Frerich Raabe

Reputation: 94319

If the properties by which you want to look up links don't change very often, you could choose a std::list<Link> as your primary container to hold the link objects. Then, for each criterion, you have one std::map which maps a value to an iterator pointing into the list. E.g.

typedef std::list<Link> LinkList;

LinkList links = ...;
std::map<std::string, LinkList::iterator> linkByName;
std::map<unsigned int, LinkList::iterator> linkByPopularity;

The nice thing about a std::list is that it has very strong iterator invalidation guarantees (basically, your iterator into a list only becomes invalid if you remove the element from the list).

In order to have these structures updated consistently, you could wrap this all into a 'LinkCollection' wrapper or so.

Upvotes: 1

aambrozkiewicz
aambrozkiewicz

Reputation: 552

This sounds perfect to use Boost Bimap.

Upvotes: 2

Related Questions