"inverse" associative container?

Question

does there exist a kind of "inverse" associative container in the stl or in general? For instance I'd like to have a container where the same element is shared by a set of keys.

Let's say my key is an int, then I would have for instance:

container.at(3) -> some object A
container.at(4) -> same object A
container.at(1) -> other object B

This container would have (ideally) the same complexity as std::map for the different operations. Is such a thing possible?

I was thinking about using at first a std::map<int, T*> where several indexes point to the same object, but then when removing an item from the map, the running time is in O(n) because you'd have to check the other items to see if you need to delete the T object

Is there already this kind of container "natively" in the stl or in boost?

edit : some example of utilisation:

container<int, myClass> myContainer;
myClass obj(...); //new object
myContainer.insert(3, obj); //insert object for specific key
myContainer.insert(2, obj); //insert same object for specific key, since both objects would compare equal we would actually not "insert" a new object but have it shared by both keys
myContainer.duplicate_object(2,5); //key 5 also has the same object as key 2 (and 3)
myContainer.getAllKeys(2); //would return 2,3 and 5 since they all reference the same object as key 2
myContainer.removeKey(3);
myContainer.removeKey(2);
myContainer.removeKey(5); //would destroy the object here, not before

I don't understand the question. Your title uses the word "reverse" and your question uses the word "inverse". Either way, your example still doesn't clarify what you mean. Can you give an example of how you would use such a container? Assume that reverse_container or inverse_container exists and write a main() method that illustrates how it works. — Code-Apprentice, Sep 19 '12 at 00:28
Also, some kind of counter would allow you to still remove in O(1) time. You increment the counter every time an object is added and decrement every time it is removed. When the count reaches zero, then you can delete it. (Of course, this may mean extending or wrapping std::map.) — Code-Apprentice, Sep 19 '12 at 00:30
@ Code-Guru : about having a counter : you'd still have to store somewhere a container saying that this pointer is used by n keys, for all the pointers in the map. So I don't see how it could be O(1) when you have to decrement the counter for a given pointer — lezebulon, Sep 19 '12 at 00:41

jogojapan · Accepted Answer · 2012-09-19T00:59:45.593

You could use a

std::map<int,std::shared_ptr<myclass>>

In C++11 that is part of the Standard. Otherwise use the shared pointers provided by the Boost library.

The idea of a shared pointer is that it internally keeps a reference count, i.e. it keeps track of how many times a copy of the pointer was made. When you delete an entry of the map, the destructor of the shared pointer object will ensure the counter is decremented. Once it reaches zero, the object will be deleted.

(Edit:) To make the answer more complete, a few usage examples:

#include <map>
#include <memory>

struct myclass
{

};


int main()
{
  std::map<int,std::shared_ptr<myclass>> mymap;

  /* std::make_shared() calls the constructor and creates a shared_ptr: */
  std::shared_ptr<myclass> object1 { std::make_shared<myclass>() };
  std::shared_ptr<myclass> object2 { std::make_shared<myclass>() };
  std::shared_ptr<myclass> object3 { std::make_shared<myclass>() };

  mymap[1] = object1;
  mymap[2] = object2;
  mymap[3] = object3;
  mymap[4] = object2;
  mymap[5] = object1;

  mymap.erase(2); // erases the (2,object2) entry
                  // therefore, decreases the counter
                  // for object2
                  // but (4,object2) is still intact

  return 0;
}

Incidentally, boost [ptr_map](http://www.boost.org/doc/libs/1_51_0/libs/ptr_container/doc/ptr_map.html) etc. are recommended over containers of shared_ptrs. — Realz Slaw, Sep 19 '12 at 01:04
@RealzSlaw Interesting; I have no experience with `ptr_map`, but if there is some justification for the recommendation, it may justify posting a separate answer. Thanks for the comment in any case. — jogojapan, Sep 19 '12 at 01:11
The difference between your answer is ony performance. AFAIK, it is equivalent functionality-wise. — Realz Slaw, Sep 19 '12 at 01:17

score 0 · Answer 2 · answered Sep 19 '12 at 14:21

0

You might want to look at Boost.MultiIndex; the description says:

The Boost Multi-index Containers Library provides a class template named multi_index_container which enables the construction of containers maintaining one or more indices with different sorting and access semantics.

answered Sep 19 '12 at 14:21

Marshall Clow

15,972
2
29
45

1

The title makes it sound like this is what he wants, but the example he gives makes it sound as if he just wants to have lightweight objects as values. – Realz Slaw Sep 19 '12 at 16:38

score -1 · Answer 3 · answered Sep 19 '12 at 00:47

So what you want is both fast insertion and lookup like in a std::map, but also the ability to quickly remove entries by value.

There is no standard container which does that. But when you want to write one yourself, you could do this by maintaining two internal data structures:

a std::map which maps keys to values
a second std::multimap which maps values to the sets of the keys pointing to them

when you want to delete keys by value, you could look it up in the second map.

"inverse" associative container?

3 Answers3