how can I find repeated elements in a vector

Question

I have a vector of int which can include maximum 4 elements and minimum 2, for example :

std::vector<int> vectorDATA(X); // x means unknown here

What I want to do is to erase the elements that are repeated for example :

vectorDATA{1,2,2}     to vectorDATA{1,2}
vectorDATA{1,2,3}     to nothing changes
vectorDATA{2,2,2}     to vectorDATA{2}
vectorDATA{3,2,1,3}   to vectorDATA{3,2,1}
vectorDATA{1,2,1,2}   to vector{1,2}

and so on

here a code simple :

cv::HoughLines(canny,lineQ,1,CV_PI/180,200);
        std::cout << " line Size "<<lineQ.size()<< std::endl;
        std::vector<int> linesData(lineQ.size());
        std::vector<int> ::iterator  it;
        if(lineQ.size() <=4 && lineQ.size() !=0 ){
            if(lineQ.size()==1){
                break;
            }else {
            for ( int i = 0; i<lineQ.size();i++){
                linesData[i] = lineQ[i][1]; // my comparison parameter is the lineQ[i][1]
            }

// based on the answer I got I'm trying this but I really don't how to continue ?

std::sort(lineQ.begin(),lineQ.end(),[](const cv::Vec2f &a,const cv::Vec2f &b)
            {
                return ????
            }

I tried use a for and do while loop, but I didn't get it, and the function std::adjacent_find this has a condition that the elements should be consecutive.
Maybe it's easy but I just don't get it ! thanks for any help !

maximum 4, minimum 4. That's not really a wide choice of sizes :) — jrok, Dec 17 '13 at 13:32

Yakk - Adam Nevraumont · Accepted Answer · 2013-12-17T15:12:29.020

3

The easy way is sort then unique-erase, but this changes order.

The c++11 order preserving way is to create an unordered_set<int> s; and do:

unordered_set<int> s;
vec.erase(
  std::remove_if( vec.begin(),vec.end(), // remove from vector
    [&](int x)->bool{
      return !std::get<1>(s.insert(x)); // true iff the item was already in the set
    }
  ),
  vec.end() // erase from the end of kept elements to the end of the `vec`
);

which is the remove-erase idiom using the unordered_set to detect duplicates.

edited Dec 17 '13 at 15:12

answered Dec 17 '13 at 13:33

Yakk - Adam Nevraumont

262,606
27
330
524

You can shorten this by simply inserting and checking the return value, as the insert will tell you whether the element already existed or not. – Svalorzen Dec 17 '13 at 13:44
@Svalorzen shorter version used. – Yakk - Adam Nevraumont Dec 17 '13 at 15:10

score 1 · Answer 2 · answered Dec 17 '13 at 13:28

I didn't see a sort-less source code in the already mentioned answers, so here it goes. Hash table for checking duplicates, shifting unique elements towards the front of the vector, note that src is always >= dst and dst is the number of copied, i.e. unique elements at the end.

#include <unordered_set>
#include <vector>
#include <iostream>

void
uniq (std::vector<int> &a) {
    std::unordered_set<int> s;
    size_t dst = 0;
    for (size_t src = 0; src < a.size(); ++src) {
        if (s.count (a[src]) == 0) {
            s.insert (a[src]);
            a[dst++] = a[src];
        }
    }
    a.resize (dst);
}

int
main () {
    std::vector<int> a = { 3, 2, 1, 3, 2, 1, 2, 3, 4, 5 ,2, 3, 1, 1 };
    uniq (a);
    for (auto v : a)
        std::cout<< v << " ";
    std::cout << std::endl;
}

score 1 · Answer 3 · answered Dec 17 '13 at 13:37

If you want to realy remove repeated elements, you may try something like this:

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

using namespace std;

int main () {
    int data[] = {1,2,3,2,1};
    vector<int> vectorDATA = (&data[0], &data[0] + 5);
    sort(vectorDATA.begin(),vectorDATA.end());

    for(int i = 0; i < vectorDATA.size()-1; ++i)
    {
        if(vectorDATA[i] == vectorDATA[i+1])
            vectorDATA.erase(vectorDATA.begin()+i+1);
    }

    for(int i = 0; i < vectorDATA.size();++i)
    {
        cout << vectorDATA[i] << " ";
    }
    cout << endl;

  return 0;
}

Lack of of this method is then elements lost his order.

@engine You forgot the sort that's being made before the remove. — Ian Medeiros, Dec 17 '13 at 14:17

how can I find repeated elements in a vector

3 Answers3