CODEWITHSUNDEEP
c++data-structures
andriej
andriej

Reputation: 2266

storing items in a map under multiple keys

I have a std::map with key_type and mapped_type. Every instance of mapped_type is inserted into the map as 3 copies - under 3 different key values. This allows me to retrieve the value based on any of the 3 keys.

But the drawback is that when I want to delete the item, I need to look for 3 keys instead of just one, in order to get rid of all 3 copies.

Is it possible to compose the 3 keys into one class and be able to compare such object with 1 key, while maintaing a strict weak ordering? In such scenario, how would the operator< look like for key_type?

EDIT: The 3 keys are of the same type e.g. a single record is accessible with 3 different integer values (and those key values are not used by any other record). So from what I understand Boost.MultiIndex is not a solution for this problem.

Upvotes: 0

Views: 392

Answers (2)

ecatmur
ecatmur

Reputation: 157334

I'd suggest using two data structures encapsulated into a single object:

  • std::list<Node> list;
  • std::map<Key, std::list<Node>::iterator> map;

where Node contains:

  • Value value;
  • and 3 instances std::map<Key, std::list<Node>::iterator>::iterator i1, i2, i3;

You can then insert and remove values with appropriate bookkeeping to ensure that the structures remain consistent.

Upvotes: 1

ecatmur
ecatmur

Reputation: 157334

Use Boost.MultiIndex. See http://www.boost.org/doc/libs/1_49_0/libs/multi_index/doc/tutorial/basics.html#multiple_sort

Upvotes: 2

Related Questions