CODEWITHSUNDEEP
c++algorithmsortingsplitunique
Bogdan
Bogdan

Reputation: 914

Split vector to unique and duplicates c++

My goal is to split a vector into two parts: with unique values and with duplicates.

For example I have sorted vector myVec=(1,1,3,4,4,7,7,8,9,9) which should be split into myVecDuplicates=(1,7,4,9) and myVecUnique=(1,4,7,9,3,8). So myVecDuplicates contains all values that have duplicates while myVecUnique contains all values but in a single embodiment.

The order does not matter. My idea was to use unique as it splits a vector into two parts. But I have a problem running my code. 

vector<int> myVec(8)={1,1,3,4,4,7,8,9};
vector<int>::iterator firstDuplicate=unique(myVec.begin(),myVec.end());
vector<int> myVecDuplicate=myVec(firstDuplicate,myVec.end());\\here error accures that says ' no match for call to '(std::vector<int>) (std::vector<int>::iterator&, std::vector<int>::iterator)'
vector<int> myVecUnique=myVec(myVec.begin()+firstDuplicate-1,myVec.end());

After running this code I get an error that says (2nd line) 'no match for call to '(std::vector) (std::vector::iterator&, std::vector::iterator)'

Please help me to understand the source of error or maybe suggest some more elegant and fast way to solve my problem (without hash tables)!

Upvotes: 1

Views: 488

Answers (4)

Saurav Sahu
Saurav Sahu

Reputation: 13934

Ahh..Too many edits in your question for anyone's liking. Just keep it simple by using map.

In C++, map comes really handy in storing the unique + sorted + respective_count values.

map<int, int> m;
for(auto &t : myVec){
    m[t]++;
}
vector<int> myVecDuplicate, myVecUnique;
for(map<int, int>::iterator it = m.begin(); it != m.end(); it++){
    if(it->second > 1) myVecDuplicate.push_back(it->first);
    myVecUnique.push_back(it->first);
}

Edit:

maybe suggest some more elegant and fast way to solve my problem (without hash tables)!

  1. Sort the vector
  2. Traverse through the sorted vector,

and do

  if (current_value == previous_value){
    if(previous_value != previous_previous_value)
     myVecDuplicate.push_back(current_value);
  }
  else{
      myVecUnique.push_back(current_value);
  }

To start, initialize previous_value = current_value - 1 and previous_previous_value as current_value - 2.

Upvotes: 1

Slava
Slava

Reputation: 44268

std::vector has a constructor that accepts 2 iterators for range [first,second[ You cannot call constructor for existing object - it is already created, so your code 

myVec(firstDuplicate,myVec.end());

actually tries to use myVec as a functor, but std::vector does not have operator() hence the error.

you have 2 ways, pass 2 iterators to constructor directly:

vector<int> myVecDuplicate(firstDuplicate,myVec.end());

or use copy initialization with temporary vector:

vector<int> myVecDuplicate = vector<int>(firstDuplicate,myVec.end());

Same for the second vector:

 vector<int> myVecUnique(myVec.begin(),firstDuplicate);

as pointed by Logman std::unique does not seem to guarantee value of duplicates, so working solution can use std::set instead (and you would not have to presort source vector):

std::set<int> iset;
vector<int> myVecUnique, myVecDuplicate;
for( auto val : myVec )
    ( iset.insert( val ).second ? myVecUnique : myVecDuplicate ).push_back( val );

Upvotes: 1

Logman
Logman

Reputation: 4189

O(n) complexity solution:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> myVec = {1,1,3,4,4,7,7,8,9,9};
    std::vector<int> myVecDuplicatec;
    std::vector<int> myVecUnique;

    for(int &x : myVec)
    {
        if(myVecUnique.size() == 0 || myVecUnique.back() != x)
            myVecUnique.push_back(x);
        else
            myVecDuplicatec.push_back(x);
    }

    std::cout << "V = ";
    for(int &x : myVec)
    {
        std::cout << x << ",";
    }
    std::cout << std::endl << "U = ";
    for(int &x : myVecUnique)
    {
        std::cout << x << ",";
    }
    std::cout << std::endl << "D = ";
    for(int &x : myVecDuplicatec)
    {
        std::cout << x << ",";
    }

}

cpp.sh/4i45x

Upvotes: 1

SingerOfTheFall
SingerOfTheFall

Reputation: 29966

While this may be frowned upon (for not using standard algorithms and such), I would write some simple solution like this:

vector<int> myVec = {1,1,3,4,4,7,8,9};
unordered_set<int> duplicates;
unordered_set<int> unique;

for(int & v : myVec)
{
    if(unique.count(v) > 0)
        duplicates.insert(v);
    else
        unique.insert(v);
}

Upvotes: 1

Related Questions