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)

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.

2 Likes

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

8 Likes

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.

8 Likes

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.

6 Likes

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.

6 Likes

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.