std::set

What kind of insertion scheme do you want to use? You can probably get away with using an std::set but just adjusting the traits so it doesn't do any sorting for you while still inserting elements how you want.

First of all, what would you want insert to do? insert at the end if it isn't present (like push_back) but do nothing if it is?

Also, really high insertion efficiency won't be possible without sorting because worst case behavior will be linear.

Sounds like std::tr1::unordered_set or hash_set suits your needs.

Quote:

Original post by chaosgame what would be the best way to implement an array based class that is similar to std::set in the sense that its members are all uneque. Unlike std::set it can not be sorted. Im guessing that I should use std::iterator. Should I just create a class derived from std::vector and overload the insert() functions?

In that case, just use std::set or std::tr1::unordered_set.
Surely just because you don't need the set to be ordered by any of the data members, doesn't mean that it has to be somehow randomly unordered.
The fact that a set is ordered isn't because that's what is always wanted, but because the container needs to be able to perform an O(logn) search, in your case for the possible duplicate. Imposing some kind of arbitrary ordering, (no matter how little use it seems) is required to be able to search in logn time, for a set. If you simply don't care about the order then just provide and dummy comparison operator that just happens to order them in some probably non-useful (but consistent) way. e.g. You could for example order items by casting the item's pointer values to a size_t and comparing them, or something like that if you are storing pointers to items.

Perhaps you do mean to have the items sorted, but by something unusual like the order in which they were inserted, as would be the case in a vector.

Your suggestion of "overload[ing] the insert() functions" is a bit puzzliing, because you said that you didn't want the data ordered, so why would there be any need to use anything other than push_back (which is fastest for a vector), after first checking for duplicates?
I think you need to explain in more detail what you are really trying to achieve.

It sounds to me like your only requirements are that the container does not allow duplicates, and you perhaps don't want to have to search through the whole lot every time.

I would like an encapsulated array class that only allows for the insertion of uneque data. The class can be ordered, I found a way around that. I need this class as a member variable of a larger node based data structure.
I dont want to use std::set because I would like to make it as efficiant as possible and Im not sure if I should have a smaller data structure as part of each node because wouldnt it eat much more memmory?

Quote:

Original post by chaosgame I would like an encapsulated array class that only allows for the insertion of uneque data. The class can be ordered, I found a way around that. I need this class as a member variable of a larger node based data structure.

You mean unique? you can do all this just using std::vector/deque with std::lower_bound then make a wrapper that gives an std::set like interface if you like.

Quote:

Original post by chaosgame I dont want to use std::set because I would like to make it as efficiant as possible and Im not sure if I should have a smaller data structure as part of each node because wouldnt it eat much more memmory?

How do you know? have you profiled yet? did you try using a custom allocator type like boost::fast_pool_allocator with it yet?

In some cases an always sorted vector/deque can be better than using std::set in other cases it's not and std::set is the better choice, it all depends on what operations you are doing the most (among other things).