CODEWITHSUNDEEP
c++collectionsstl
Jonathan Wood
Jonathan Wood

Reputation: 67355

Best STL container for fast lookups

I need to store a list of integers, and very quickly determine if an integer is already in the list. No duplicates will be stored.

I won't be inserting or deleting any values, but I will be appending values (which might be implemented as inserting).

What is the best STL container class for this? I found std::multimap on Google, but I that seems to require a key/value pair, which I don't have.

I'm fairly new to STL. Can I get some recommendations?

Upvotes: 3

Views: 2182

Answers (2)

jfMR
jfMR

Reputation: 24788

std::unordered_set<int> is a good choice for keeping track of duplicates of ints, since both insertion and lookup can be achieved in constant time on average.

Insertion

Inserting a new int into the collection can be achieved with the insert() member function:

std::unordered_set<int> s;
s.insert(7);

Lookup

Checking whether a given int is present in the collection can be done with the find() member function:

bool is_present(const std::unordered_set<int>& s, int value) {
   return s.find(value) != s.end();
}

Upvotes: 1

eerorika
eerorika

Reputation: 238471

Instead of a map, you can use a set when the value and the key aren't separate.

Instead of a multiset/-map, you can use the non-multi version which doesn't store duplicates.

Instead of a set, you have the std::unordered_set as an alternative. It may be faster for your use case.

There are other, less generic, data structures that can be used to represent sets of integers, and some of those may be more efficient depending on the use case. But those other data structures aren't necessarily provided for you by the standard library.

But I'm not clear which have the fastest lookup.

Unordered set has better asymptotic complexity for lookups than the ordered one. Whether it is faster for your use case, you can find out by measuring.

not likely to exceed a thousand or so

In that case, asymptotic complexity is not necessarily relevant.

Especially for small-ish sets like this, a sorted vector can be quite efficient. Given that you "won't be inserting or deleting any values", the vector shouldn't have significant downsides either. The standard library doesn't provide a set container implemented internally using a sorted vector, but it does provide a vector container as well as all necessary algorithms.

I don't know how the containers compute hashes.

You can provide a hash function for the unordered container. By default it uses std::hash. std::hash uses an implementation defined hash function.

Upvotes: 5

Related Questions