CODEWITHSUNDEEP
c++stldictionarysetcontainers
paperjam
paperjam

Reputation: 8508

Most appropriate associative STL container when key is part of object [C++]

I have a class like this:

struct Thing
{
    unsigned index;
    // more data members
};

I am using a std::map<Thing> to contain my Things. Calling code looks something like this:

Thing myThing(/*...*/);
std::map<Thing> things;
things[myThing.index] = myThing;
// ...
Thing &thing3 = things[3];

I was wondering if there was an approach that could use Thing::index directly without the need implicitly to copy it into pair::first.

I guess I would need to provide some sort of Thing comparison operator, but that's OK. std::set might work, but I would need a whole Thing object as key:

std::set<Thing> things;
Thing &thing3 = *things.find(Thing(3));

Other than refactoring Thing into a std::pair, can I do better with STL?

Upvotes: 5

Views: 291

Answers (4)

timday
timday

Reputation: 24892

I don't see why

inline bool operator<(const Thing& a,const Thing& b) {
  return (a.index<b.index);
}

std::set<Thing> things;  // Uses comparison operator above

Thing &thing3 = *things.find(Thing(3));

doesn't do exactly what you want. No duplication/copying of the index field, and key comparison as efficient as the map approach; what's not to like ?

Update in light of comments below:

If Thing is so heavyweight that you don't want to copy it, then you'd probably end up with code more like:

inline bool operator<(const shared_ptr<Thing>& a,const shared_ptr<Thing>& b) {
  return (a->index < b->index);
}

std::set<shared_ptr<Thing>> things;  // Uses comparison operator above

shared_ptr<Thing> key3(new Thing(3));   

Thing &thing3 = *things.find(key3);

although IMHO overriding pointer value comparison is fairly evil and it'd be better to go the more verbose route of an explicit "Compare" argument to the set template args.

One thing to bear in mind (from my own experience of big priority queues of heavyweight objects): there may be significant advantages to std::pair<trivial_key,shared_ptr<heavyweight_object>>-based containers over std::pair<trivial_key,heavyweight_object> due to the fact that traversals of the former touching only keys (e.g find) can be much more cache efficient compared with the latter which will also fetch a lot of mostly unneeded/irrelevant heavyweight_object bytes into cache (depends on the details and numbers of course, but in fact this effect could easily completely swamp the relatively minor cost of duplicating the key).

Upvotes: 2

lurscher
lurscher

Reputation: 26943

I Recall that boost::flyweight supports key extractors to avoid keeping extra storage for the key, when it is readily obtainable from the object.

I'm not suggesting to use flyweight in all cases where map or unordered_map are sufficient, I have a hard time believing those classes won't support a similar key extraction pattern, although i can't find any mention in the docs or google. In either case this might be helpful to you

Upvotes: 1

Basilevs
Basilevs

Reputation: 23916

Wrap map with private inheritance or composition, reexport accessors and implement insertion in terms of required functionality. I'd recommend to patametrize your new type on key getter - a functor that returns a key given an object of storage type.

Upvotes: 1

AlexTheo
AlexTheo

Reputation: 4164

What about using the memory address of your object as a key in your map?? 

std::map< void*, std::shared_ptr<MyObject> > myMap;
myMap.insert( std::pair<void*, std::shared_ptr<MyObject> >(object.get(), object) );

So you don't need to store the key in your object which I think is a bad idea because the key does not has any relation with the objects state.

Upvotes: 0

Related Questions