CODEWITHSUNDEEP
c++algorithmfor-loopvectorduplicates
rrc
rrc

Reputation: 335

Check std::vector has duplicates

I want to check if a vector of integers has any duplicates or not, and have to return true if it does. So I try to do something like this:

vector<int> uGuess = {1,2,3,3,4,5}
vector<int> a = uGuess;
sort(a.begin(), a.end());
bool d = unique(a.begin(), a.end());

And this will not work since unqiue cannot be assigned as a bool value. How should I proceed towards this? If I were to write a for loop to perform the same action, how should I do that?

Upvotes: 28

Views: 69531

Answers (9)

Monsalma
Monsalma

Reputation: 21

For unsorted vectors of int, a simple nested loop should do.
The original vector is not modified and the complexity is O(n2):

bool duplicateFound = false;
std::vector<int>::iterator duplicate;

for (auto i = vecOfInt.begin(); !duplicateFound && i != vecOfInt.end(); i++)
{
    for (auto j = vecOfInt.begin(); !duplicateFound && j < i; j++)
    {
        if (*i == *j)
        {
            duplicateFound = true;
            duplicate = i;
        }
    }
}

or:

bool duplicateFound = false;
std::vector<int>::iterator duplicate;

for (auto i = vecOfInt.begin(); !duplicateFound && i != vecOfInt.end(); i++)
{
    if (i != vecOfInt.begin())
    {   
        auto prevI = i - 1;

        if ((duplicate = std::find(vecOfInt.begin(), prevI, *i)) != prevI)
        {
            duplicateFound = true;
        }
    }
}

Upvotes: 1

Sir2B
Sir2B

Reputation: 1079

If you have a more complex vector and want to know which value is duplicated, you can do something like this:

#include <vector>
#include <unordered_set>
#include <string>

template <typename InputContainer_t, typename GetCompareValueLambda_t>
bool HasDuplicates(const InputContainer_t& container, GetCompareValueLambda_t compare)
{
    using CompareValue_t = decltype(compare(*container.begin()));
    std::unordered_set<CompareValue_t> setUniqueValues;
    bool hasDuplicates = false;

    for (const auto & element : container)
    {
        CompareValue_t compareValue = compare(element);

        auto [_, successful] = setUniqueValues.insert(compareValue);

        if (!successful)
        {
            printf("Value '%s' is not unique.\n", std::to_string(compareValue).c_str());
            hasDuplicates = true;
        }
    }
    return hasDuplicates;
}

int main()
{
    std::vector<int> a {1,2,2};
    HasDuplicates(a, [](auto x){ return x; });
    
    std::vector<S> b {{1, 0},{2, 1}, {2, 0}};
    HasDuplicates(b, [](auto x){ return x.idx; });

    return 0;
}

see also: https://onlinegdb.com/bvOzbptnR

Upvotes: 0

Goswin von Brederlow
Goswin von Brederlow

Reputation: 12362

If your vector is small, say < 32 objects, or if copying and sorting the objects is expensive or impossible due to lack of move or copy constructor/assignment then a straight O(n^2) compare everything against everything else algorithm is the way to go.

Here is my solution:

template <typename Iterator>
bool has_duplicates( Iterator first, Iterator end ) {
    for (auto i = first; i != end; ++i) {
        for (auto j = first; i != j; ++j) {
            if (*i == *j) return true;
        }
    }
    return false;
}

template <typename Container>
bool has_duplicates(const Container &v) {
    for (const auto & i : v) {
        for (const auto & j : v) {
            if (&i == &j) break;
            if (i == j) return true;
        }
    }
    return false;
}

Upvotes: 3

mksteve
mksteve

Reputation: 13085

Looking at google for std::unique I found this page std::unique. I looked at what it did:

Eliminates all except the first element from every consecutive group of equivalent elements from the range [first, last)

So it looks like it does what you want - removes the duplicates.

I then looked at what it returns...

... returns a past-the-end iterator for the new logical end of the range

So the result from std::unique is a sequence which is not necessary the same as the whole vector.

If nothing was removed, the return value would be the end of the vector.

So you want:

vector<int>::iterator it = std::unique(a.begin(), a.end());
bool wasUnique = (it == a.end());

Or for C++11:

auto it = std::unique(a.begin(), a.end());
bool wasUnique = (it == a.end());

Finally for the unique function to work, the vector needs to be sorted, so the complete code would be:

sort(a.begin(), a.end());
auto it = std::unique(a.begin(), a.end());
bool wasUnique = (it == a.end());

Upvotes: 15

Jan Holecek
Jan Holecek

Reputation: 2251

The algorithm you're looking for is std::adjacent_find.

// The container must be sorted!
const std::vector<int> sortedVector = {1,2,3,3,4,5};
const bool hasDuplicates = std::adjacent_find(sortedVector.begin(), sortedVector.end()) != sortedVector.end();

Unlike std::unique, std::adjacent_find doesn't modify the container.

As a bonus, std::adjacent_find returns an iterator to the first element in the duplicate "pair":

const auto duplicate = std::adjacent_find(sortedVector.begin(), sortedVector.end());

if (duplicate != sortedVector.end())
    std::cout << "Duplicate element = " << *duplicate << "\n";

Upvotes: 35

gsamaras
gsamaras

Reputation: 73444

Sort the vector if it's not already sorted, and then use std::unique(), like this:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 3, 4, 5};
    sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    std::cout << ((it == v.end()) ? "Unique\n" : "Duplicate(s)\n");
    return 0;
}

Output:

Duplicate(s)

Upvotes: 2

Giang
Giang

Reputation: 2739

You should using set

set<int> s(a.begin(), a.end());
return s.size() != a.size();

Upvotes: 25

boriaz50
boriaz50

Reputation: 856

If someone is forced to write own algorithm:

bool hasDuplicates(const std::vector<int>& arr) {
    for (std::size_t i = 0; i < arr.size(); ++i) {
        for (std::size_t j = i + 1; j < arr.size(); ++j) {
            if (arr[i] == arr[j])
                return true;
        }
    }
    return false;
}

But in real code you should use things that already exist, and in the standard library.

Upvotes: 2

D&#250;thomhas
D&#250;thomhas

Reputation: 10123

So far all these solutions either modify the container or have O(n²) complexity. You can put a std::map to much better use:

#include <algorithm>
#include <iterator>
#include <map>

template <typename Iterator>
bool has_duplicates( Iterator first, Iterator last )
{
  std::map <typename std::iterator_traits <Iterator> ::value_type, std::size_t> histogram;

  while (first != last)
    if (++histogram[ *first++ ] > 1) 
      return true;

  return false;
}

#include <iostream>
#include <vector>

int main()
{
  using std::begin;
  using std::end;

  int a[] = { 2, 3, 5, 7, 11 };
  int b[] = { 2, 3, 5, 5, 7 };

  std::vector <int> c( begin(a), end(a) );
  std::vector <int> d( begin(b), end(b) );

  std::cout << std::boolalpha;
  std::cout << "a has duplicates false : " << has_duplicates( begin(a), end(a) ) << "\n";
  std::cout << "b has duplicates true  : " << has_duplicates( begin(b), end(b) ) << "\n";
  std::cout << "c has duplicates false : " << has_duplicates( begin(c), end(c) ) << "\n";
  std::cout << "d has duplicates true  : " << has_duplicates( begin(d), end(d) ) << "\n";
}

Upvotes: 2

Related Questions