0

I need a data structure that manages integer IDs for T objects (typically std::string). It should support getting the ID for some object and, vice versa, get the object for some ID:

// if object not seen before: copies and stores object and returns
// new ID, otherwise just returns its ID
int Add(const T& obj);

// if obj not found: returns some specified `NotFound` ID,
// otherwise just returns its ID
int GetId(const T& obj);

// if id not contained: throws exception, 
// otherwise returns associated object
const T& GetObj(int id)

It should also own all those T objects, so internally it allocates new objects, stores them and deletes them in the destructor.

Any comments? How would you implement that?

I am using these two containers inside; every object pointer is stored in both:

// quickly retrieve the ID
std::map<const T*, int, CompareByValue> Obj2IdMap;
// quickly retrieve the object, given an ID
std::vector<const T*> Id2ObjMap;

Are there any other data structures that might help? Or is this whole object ID manager already available in some library?

Frank
  • 64,140
  • 93
  • 237
  • 324
  • For first question it seems you compulsorily need RAII. For the second question hash_map could be another option !! – DumbCoder Sep 29 '10 at 15:43

1 Answers1

1

It should also own all those T objects, so internally it allocates new objects, stores them and deletes them in the destructor.

Any comments? How would you implement that?

I would use boost shared_ptr to manage the objects.

Are there any other data structures that might help? Or is this whole object ID manager already available in some library?

Check this Stack Overflow thread: Using STL containers for multiple keys. I think thats a good alternative solution for your problem although, to be honest, I have used your very same approach in lots of projects too.

Community
  • 1
  • 1
Ruben Penalva
  • 11
  • 2
  • They recommend Boost.MultiIndex. That makes sense (although it looks slightly intimidating ...). – Frank Sep 29 '10 at 22:47