🔒 Locked

C++ container class fun!

Started by Timkin Oct 30, 2005 at 9:18 PM 2 replies 600+ views

Original Post

Oct 30, 2005 at 9:18 PM

So one of my projects I'm working on has taken me to the point of requiring a template container class similar to a priority queue, but with the ability to enforce uniqueness of objects stored (so kind of like an inverse map). That is, objects stored might have non-unique keys so that the sort order is actually a set of possible orders, but when inserting an item, a check should first be made to see whether the item already exists or not. Certainly, I could just write a helper function (or friend function) to do this checking and insertion into an STL list, but I was hoping there was already something out there. I'd really prefer to offer the container as a complete class, so an adapter might be appropriate!? Obviously, one possibility is just to design my own template class from scratch. So, to summarise, I need a priority queue that also permits inspection of non-head items, at least internally for member functions. I'm guessing I'm going to have to design/write it myself though. Any thoughts or advice on how to do this efficiently/robustly would be welcome. Cheers, Timkin

MrEvil

Oct 30, 2005 at 10:14 PM

Not sure how capable this is, since unfortunately my head exploded half way through reading about it (it's early in the morning [dead]), but I've seen it produce some cool ontainers (bidirectional map, for one):
Boost.MultiIndex

And if it's not useful, at least it's interesting [wink]

Sneftel

Oct 30, 2005 at 10:20 PM

It sounds like you just want a set (usually implemented as a red-black tree). AFAICT there's no way to enforce uniqueness on insertion except linear search for unsorted or binary search for sorted, so you can't insert in better than O(log n).

Timkin

Oct 30, 2005 at 10:45 PM

EDIT: It looks like the Boost.MultiIndex might do what I want. Thanks for the link.

Quote:
Original post by Sneftel
It sounds like you just want a set

Nope... a set collects unique values and uses these as the keys upon which to order the set.

I require a container that can store unique items, but for which each item may have several keys. To get your head around this concept, consider a finite set of objects that you want to store, but which can be stored according to a key which might represent some function of a subset of the objects that includes the current object. So, different subsets that all include a particular object might presumably give different keys. So, in one example, that function might return a value which could be ordered against all other values, thus inducing a preference ordering on the possible subsets that could be formed from the set of objects (really a preference odering on the arguments to the function).

(and yes, this DOES have relevance to game development!) ;)

Cheers,

Timkin

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.