Remove duplicates from unsorted vector of arrays of doubles

Question

So in my code I got a vector of multidimensional arrays. In this vector I store the coordinates of points of a contour. Before I can restore the contour, based on the points, I have to erase the duplicates to reduce the data. So I found that I can use std::unique, if the vector is sorted. But sorting isn't needed, so I want to erase the duplicates from the unsorted vector. So I have to use std::set to remove the duplicates

std::vector<std::array<double, 3>> matrix;
rows = 2*lss.size();
matrix.resize(rows);

int j=0;

for(size_t i = 0;i<lss.size();i++) {
    int k = j+1;

    matrix[j][0]=lss[i].v[0].x;
    matrix[j][1]=lss[i].v[0].y;
    matrix[j][2]=lss[i].v[0].z;
    matrix[k][0]=lss[i].v[1].x;
    matrix[k][1]=lss[i].v[1].y;
    matrix[k][2]=lss[i].v[1].z;

    j=j+2;
}

std::set<double> set(matrix.begin(), matrix.end());

matrix.erase(std::remove_if(matrix.begin(), matrix.end(), [&set] (double item) {return !set.erase(item); }), matrix.end());

But for the line std::set<double> set(matrix.begin(), matrix.end()); I get this error message: 'std::pair<_Ty1,_Ty2> std::set<_Kty>::insert(double &&) : cannot convert parameter 1 from std::array<_Ty,_Size> to 'double &&'.

For the following line I also receive an error message: 'bool export::<lambda_c894aac2078f37151750793b2c6d0417>::operator ()(double) const' : cannot convert parameter 1 from 'std::array<_Ty,_Size>' to 'double'

`std::set set()` would expect doubles while you are passing std::array to it. — Gaurav Sehgal, May 24 '16 at 07:41
If you want to avoid duplicates, why do you store your points in a vector in the first place? Is it to meet a particular requirement? — Rerito, May 24 '16 at 07:41
Pushing to a set and erasing the tail has almost the same complexity as sorting first then finding unique values. — Eissa N., May 24 '16 at 07:46
@GauravSehgal : Thanks for the tip I changed the line to `std::set> set()`. And also the second line had to be changed to `... [&set] (array item) ...` — user3794592, May 24 '16 at 07:48
@Rerito: I store the unsorted points in the vector. To restore the contour my code than search for the nearest neigbor for each point to sort the vector. — user3794592, May 24 '16 at 07:50
@EissaN.: So it would take as much time to sort the vector and erase from the sorted vector, than to erase from the unsorted vector? — user3794592, May 24 '16 at 07:51
@user3794592 Correct! Also, to use `std::set` you need to define `<` for its elements. But, I guess you don't have a well-defined `<` operation. You only care whether 2 elements are equal or not. So, you need `std::unordered_set` and you need to define `==` for the elements. — Eissa N., May 24 '16 at 07:53
@user3794592 Even after this `matrix.erase()` will remove duplicate `std::array` as a whole and not individual double elements.I think this is not what you desire. — Gaurav Sehgal, May 24 '16 at 07:57
@GauravSehgal: I want to remove duplicate `std:array` as a whole. — user3794592, May 24 '16 at 08:06
@GauravSehgal: By removing the whole array, I reduce the size of the vector and my following sorting function (finding the nearest point to the first element and so on) has to deal with fewer elements. Or is my thinking here wrong? **Edit:** Or how do I remove arrays form my vector, in wich the x y and z coordinates are duplicates — user3794592, May 24 '16 at 08:14
If all your values are say `1.2`, then what output do you want?`[[1.2,1.2,1.2]]`? — Gaurav Sehgal, May 24 '16 at 08:18
@GauravSehgal: My vector `matrix` contains in the rows the arrays. So if i call `matrix[i]` I get the `i` element (array) of the vector. By `matrix[i][0]` I get the x coordinate of the i array in the vector. So I want to remove the whole array if `matrix[i][0]` and `matrix[i][1]` and `matrix[i][2]` are the same as a previous element. So if the first array is `[[5, 5, 5]]` and a following array is also `[[5,5,5]]` i want to remove the second array from my vector. — user3794592, May 24 '16 at 08:24
@GauravSehgal: Sorry but I can't find a difference between your code and mine. You pass two times the same input to the vector. Than you remove the duplicate. That's exactly what I want to do. — user3794592, May 24 '16 at 08:39
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/112767/discussion-between-gaurav-sehgal-and-user3794592). — Gaurav Sehgal, May 24 '16 at 09:52

score 1 · Answer 1 · edited May 23 '17 at 10:28

If you require your container holds unique items only and you do not care about these being sorted then you can always just use std::unordered_set to hold your coordinates.

Simple example:

#include <iostream>
#include <unordered_set>    

struct Point
{
    double x, y, z;

    bool operator==(const Point& other) const
    {
        return (x == other.x) && (y == other.y) && (z == other.z);
    }
};

Hash function taken from this answer:

struct Hash 
{
    size_t operator() (const Point &point) const 
    {
        return ((std::hash<double>()(point.x)
            ^ (std::hash<double>()(point.y) << 1)) >> 1)
            ^ (std::hash<double>()(point.z) << 1);
    }
};

int main()
{
    std::unordered_set<Point, Hash> uset;
    uset.insert({ 100, 100, 200 });
    uset.insert({ 100, 100, 200 });
    uset.insert({ 100, 100, 200 });

    std::cout << uset.size() << '\n'; // prints 1

    return 0;
}

score 0 · Answer 2 · answered May 24 '16 at 07:53

0

You should change the line

std::set<double> set(matrix.begin(), matrix.end());

to:

std::set<std::array<double, 3>> set(matrix.begin(), matrix.end());

You're building a set of matrices, not doubles. The template parameter to your set should be the same as to your vector.

answered May 24 '16 at 07:53

Smeeheey

9,906
23
39

Thanks I already changed the line. I forgot that my vector do not contain `doubles`, but `std:array` – user3794592 May 24 '16 at 08:08

Remove duplicates from unsorted vector of arrays of doubles

2 Answers2