CODEWITHSUNDEEP
c++stl
McLovin
McLovin

Reputation: 3417

Prefer unordered_set over vector

Is it safe to say that if I don't want duplicates in my container, and I don't care about element position as I only want to iterate through the container, then I should use an unordered_set instead of vector?

Upvotes: 10

Views: 15538

Answers (5)

Hari
Hari

Reputation: 1813

This article by Matt Austern is related to this topic and it is worth reading:

Why you shouldn't use set (and what you should use instead) by Matt Austern

This thread is trying to identify conditions under which unordered_set is preferable over vectors. Similarly, in the above article, the author clearly identifies four conditions, which all need to be satisfied in order to prefer set over a custom but simpler data structure called sorted_vector (last section: What is set good for?). Like that it will be interesting to identify a set of conditions for preferring unordered_set over vector.

also, the last paragraph of the article summarizes a useful rule to keep in mind:

Every component in the standard C++ library is there because it's useful for some purpose, but sometimes that purpose is narrowly defined and rare. As a general rule you should always use the simplest data structure that meets your needs. The more complicated a data structure, the more likely that it's not as widely useful as it might seem.

Upvotes: 1

Slava
Slava

Reputation: 44258

Is it safe to say that if I don't want duplicates in my container, and I don't care about element position as I only want to iterate through the container, then I should use an unordered_set instead of vector?

No, it is not. It depends on many factors. For example if you seldom add new elements but iterate over container quite often it would be preferable to use std::vector and maintain uniqueness manually. There also could be other factors affecting your decision. But normally yes you may prefer std::unordered_set as it simplifies your program.

Upvotes: 14

SergeyA
SergeyA

Reputation: 62583

Of course yes. If you do not want duplicates, you have to use a key-aware container, and since unordered_* totally win over their tree-based counterparts, this is pretty much your only choice.

Upvotes: -2

Erik Alapää
Erik Alapää

Reputation: 2703

I generally prefer vector or map. (or in your case, std::set).

Hash tables can be faster than maps/sets (red-black trees), but red-black trees have guaranteed performance 100% of the time. And logarithmic performance is REALLY fast! A hash table kan kill performance when it starts rehashing.

std::vector is the workhorse of the STL and should be your default choice. Vector is very straightforward, and is very cache-friendly

Upvotes: 4

YSC
YSC

Reputation: 40080

Not entirely. unordered_sets are not required to be contiguous containers; in the case where you'd frequently want to read all numerous values contained in the set, you may prefer std::vector on time-critic application.

std::unordered_set:

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

But in the general case, I'd say Yes.

Upvotes: 5

Related Questions