CODEWITHSUNDEEP
c++containers
user656925
user656925

Reputation:

Are elements searchable in a multimap? Is it needed?

If I have Key->Elements

A->B,C,D,E

Are B,C,D,E searchable , i.e. are they inserted into a red and black tree.

I think the answer is no. I think I would need a 

multimap<string,map>

to make the value part searchable efficiently (i.e. part of a red and black tree)

A->B,C,D
B->C,D
C->D
D->E

If I use a map of sets, this would best describe this structure. Each Key of the map points to a set. Each set is basically a list of Elements. Because I'd like efficient searching and inserting I'm using std::map and std::set instead of std::list and std::list.

Upvotes: 2

Views: 166

Answers (3)

juanchopanza
juanchopanza

Reputation: 227390

If you want the value part to be a sequence with efficient look-up time, you can use

multimap<string, set>

if the elements of the value-sequence are unique, or

multimap<string, multiset>

if not. This would give you logarithmic lookup time, and logarithmic insertion (this can be better or worse depending on the type of insertion, look at std::set and std::multiset documentation). The sets behave much like the std::maps, except that the value of each element is its key.

Upvotes: 1

Tony Delroy
Tony Delroy

Reputation: 106086

I think I would need a multimap<string,map> to make the value part searchable efficiently (i.e. part of a red and black tree)

You think right.

But if they keys and values are in oder then do I need an associative container at all. Wouldn't it be better to use a vector?

If they're in order, and you don't plan on adding or removing elements quickly, then yes - a binary search (provided in <algorithm>) in a vector can be expected to outperform a map lookup.

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490108

No -- neither map nor multimap will do that. You'd want something like a Boost bimap for this.

Upvotes: 2

Related Questions