CODEWITHSUNDEEP
c++set
Darlyn
Darlyn

Reputation: 4938

Detecting duplicates with set

I am working with data that shouldn't pop up twice. If it does, it should detect it and invoke a function handling that.

Currently, I am pushing some data to a vector and before insertion, it should check if the data is already contained in that vector. At the moment, this is not very effective, e.g

for (int i = 0; i < myVector.size() ; i++) 
{
  if ( myVector[i] == data ) 
  {
             // invoke function
             return false;
  }
}

I know set is a special kind of vector which allows only unique data.

Is there another way to detect duplicate data being added (or at least attempting to add it) to the set?

Upvotes: 13

Views: 42155

Answers (4)

Rakete1111
Rakete1111

Reputation: 48938

std::set returns std::pair<iterator, bool>, where the bool is false when the insertion failed (by adding duplicate values for example).

Example:

std::set<int> set{ 1, 2, 3 };
auto result = set.insert(1);
if (!result.second)
    std::cout << "Failed to insert element!" << std::endl;

Upvotes: 8

Serge Ballesta
Serge Ballesta

Reputation: 148880

A std::set or std::unordered_set is another container from standard c++ library but is not a vector... They obey different rules:

  • a vector is more or less a growable array: no control on duplicates, but respect insertion order
  • a set requires an order on the data it contains and allows to browse its data according to that order. It automatically reject duplicates at insertion time
  • an unordered_set also reject duplicates at insertion time, but the browse order is kind of random (not exactly, it is even perfectly deterministic but depends on the hash function being used)

For a vector, a simple way to see if it already contains a value is (ref):

std::find(vector.begin(), vector.end(), item) != vector.end()

For a set of unordered_set, the insert method returns a pair iterator pointing to the element - boolean indicating where it was added or not for being already there

if (! my_set.insert(data).second) {
    // invoke function
    return false;
}

Upvotes: 6

Jean-Baptiste Yun&#232;s
Jean-Baptiste Yun&#232;s

Reputation: 36391

You can use an std::unordered_set. There is a method insert which, depending on library version returns you information about the insertion (either a pair with a bool that is true if insertion was effective and false if already in), or an iterator, etc. Find the documentation of your lib.

Upvotes: 1

Mark B
Mark B

Reputation: 96243

First let's just be clear that a set is not a special kind of vector. It's a kind of container, orthogonal to vector, that happens to prevent duplicates.

You can detect duplicates by checking the return value from insert:

if(my_set.insert("value").second == false) { do_something_for_duplicate(); }

Upvotes: 31

Related Questions