Algorithm for checking if an element is in a vector that is not O(n)

I need to be quick about this, As I don't have much time today.
But the Standard Library mentioned that the contains() function is O(n).

Is there a better way to do this? (at least not linear time)

If the vector is sorted, you can use binary_search, which takes O(log 𝓃) time. Otherwise, O(𝓃) is the best you can theoretically achieve.


Have you considered alternative collections? A HashSet can do it in O(1).


Also check your dataset sizes (typical and worst-case). I'd rather have a simple and efficient O(n) with a smallish n than an O(1) with a big constant cost.

As always, benchmark.


I can't remember the exact talk, but several years ago there was a talk at CppCon showing the relative performance of different data structures. The big thing I took away was that linearly scanning std::vector (Vec) was faster than std::map (BTreeMap) up to a surprisingly large number of elements despite worse algoritmic complexity because modern CPUs really like scanning through memory sequentially.


Exactly ! I know people that abuse the O(x)-ness of their algorithms without realizing that in real life cache-trashiness is often more important than how many loops you imbricate. Basically once you've pulled a cache line what you do inside it is O(zero), and smart programmers take advantage of that.


This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.