std::set allows you to have one index variable. std::map and std::multimap allow you to have a "table" that is indexed by one variable and has non-index variable. What I'm looking for is a n-ary table with multiple indexes. Ie, a collection of data for which fast lookup by multiple parameters is possible. Ideally I'd like the syntax to be STL-esque. Failing being able to find it, I'll have to write it. ^_^

Though I've not yet used it, the abstract for Boost.MultiIndex sounds like it might be what you are looking for.

Quote:Original post by jpetrie
Though I've not yet used it, the abstract for Boost.MultiIndex sounds like it might be what you are looking for.

Ayep, it does!

Sadly it requires compile-time decisions about what to Index, but that is understandable.

Would not simply creating an additional map be another way to create another index? It seems to me there is no difference between a thing being held in a "table" with multiple "indexed" / sortable columns, than that thing being in mutliple completely unrelated lists. For example often our game objects are "owned" in some sort of container, but might also be in lists based on player, area, state, game groupings, etc. The transient states / relations the object finds itself in while running are almost the same as any fundamental core attribute of the object itself.

If something is in many different containers, then they all have to be managed when the item is modified.

As an example, a map from int id to string name. Sometimes you want to be able to remove elements from this map by name.

Searching the map linearly is not acceptable. So you now have to maintain a map from name to id. And whenever you modify one of the two maps, you have to modify the other -- this really is begging to be encapsulated into one container.

With a "table" or a boost::multi_index, you can have your map that goes both ways. Inserting elements into the table updates both indexes. If you have an element and delete it, it is removed from all of the indexes.

Plus (as mentioned in the boost::multi_index) you get nice features like O(1) object deletion, 20% to 100% faster performance for inserts than the naive multiple container approach, it takes up less memory, and the interface is tight.

"I want to find all the items held by Chuck".

item_table.index<by_owner>().equal_range("Chuck");

"I want to find the sword held in Bob's left hand".

item_table.index<by_owner_location>().equal_range(  inventory_location("Bob", slot::left_hand ));

"I want to find all of the swords with object ID 1337".

item_table.ndex<by_id>().equal_range(1337);

"I want to find all items enchanted with blessing of the chicken."

item_table.index<by_enchant>().equal_range(  *(enchant_table.index<by_name>().find("Blessing of the Chicken")));

I wanted this because I had a pile of data I wanted sorted upteen ways, and didn't want to bother maintaining upteen containers. So I'm happy. =)