CODEWITHSUNDEEP
c++vector
Apache
Apache

Reputation: 1110

How to find first duplicate item in a vector - C++?

I have a vector with different values and some of them may appear twice. (Only twice.)
How can I find the FIRST duplicate item?

Like: [a][b][b][a]
Then I'd need 'b'.

(Sorry for the newbie question.)

Upvotes: 1

Views: 1924

Answers (3)

MSalters
MSalters

Reputation: 179779

If you don't want to use extra storage, there are roughly two solutions. The first is brute-force: For every element i, check if it equals the elements 0..i-1. This is O(N*N) (obvious worst case: last two elements are the first duplicates).

The second solution is to make the search faster, by keeping the range 0..i. sorted. You'll find the duplicates trivially during the sorting. A bubble sort is efficient because the range 0..i-1 was already sorted in the previous iteration. Still O(N*N) worst case, but O(N) if the range happened to be sorted before.

Upvotes: 0

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

If you're looking for adjacent duplicates, you can simply use std::adjacent_find.

If the duplicates aren't necessarily adjacent, then you could first std::sort the vector, and then use std::adjacent_find on the result. (See @aix's comment below)

Alternatively, you could push each element into a std::set, and look for collisions as you're doing it.

Upvotes: 7

Johann Gerell
Johann Gerell

Reputation: 25581

There are many answers to this question. To find the best one, it's necessary to know the context of your usage scenario. For instance, is it ok that there are duplicates in the first place? What are you going to do with the result of the duplicate search? Can we use a parallel structure to the vector at all times? And more...

So, one way, of many, is to iterate the items and insert them to a std::set<>. Look at the second parameter of the returned std::pair<> to get whether the value existed in the set or not, then you'll get the first duplicate and can bail out of the set-adding.

Upvotes: 3

Related Questions