1

I need to store unique objects in a container. The object provides a operator== and operator!= (operator< nor operator>).

I can't use std::set, as it requires a operator<. I can't use std::unordered_set as it requires a hash function and I have none. Let's say I can't write one considering my object type (or I'm lazy).

Am I really forced to use a std::vector and make sure myself that items does not get duplicated in the container (using std::find which uses operator==)?

Is there really no container that could be used to store unique items only using the operator==?

Improve this question
19
  • 2
    std::unordered_set does not require operator< Commented Aug 23, 2016 at 14:04
  • 1
    As above. The only thing is to provide an hash function for the unique object. Commented Aug 23, 2016 at 14:05
  • 1
    stackoverflow.com/questions/28767234/… --- DUPLICATE QUESTION Commented Aug 23, 2016 at 14:06
  • 1
    @CherkesgillerTural: Actually, no, as it doesn't mention operator< at all. Commented Aug 23, 2016 at 14:07
  • 2
    Then you're stuck with O(N) singularity check. Commented Aug 23, 2016 at 14:11

3 Answers 3

Reset to default
4

There's indeed no standard container, and that's because it would be inefficient. O(N), to be precise - exactly the brute force search you imagine.

Both std::set<T> and std::unordered_set<T> avoid a brute-force search by taking advantage of a non-trivial property of T. Lacking either property, any of the existing N members of a container could be equal to a potential new value V, and you must therefore compare all N members using operator== repeatedly.

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

Do you mean that the standard will not develop, let's call it, a "unique_vector" container only because it won't be efficient. It's true STL provides effective code but it also provides code to make developers life easier...no?
@jpo38: Yes, that's indeed the case. Same reason as why std::list doesn't have an O(N) operator[ ]; it could be implemented but wouldn't be fast.
It wouldn't provide a unique_vector because std::unordered_set is already provided which is more efficient. If you can write an operator== it's a safe assumption that you can write a hash function in most cases.
@Kevin: That's not a safe assumption, actually. Try writing a hash function that hashes std::vector<std::string>, for instance. Keep in mind that strings can contain any char including \0 and a vector can contain empty strings. Equality is trivial, in comparison.
@MSalters: what's the problem there?
|
2

"Let's say I can't write a hash function considering my object type (or I'm lazy)."

Well, you're lazy, but I'll write one for you anyway : template<typename T> size_t degenerate_hash(T) { return 0; }.

Of course, this means you get O(N) performance because every value collides with every other value, but that was the best possible outcome anyway.

Improve this answer

1 Comment

That's definitely a nice solution! Thanks for answering.
1

Use a std::vector and before you std::vector::push_back or std::vector::insert use first std::find to check whether the element already exists in the vector.

Or at the end of all insertions use std::unique in combination with std::vector::erase to remove duplicates.

Improve this answer

3 Comments

That's what I'm actually doing right now. Was just surprised the STL did not provide a container doing this autmatically...I'll have to keep this solution then! Thanks.
@jpo38 I don't see any reason why STL should support a data structure like this, since there's std::set and std::unordered_set for it. IMHO it's not a big deal to provide a operator< for your stuff .
std::unique will only work if the equivalent elements are consecutive, right?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.