Efficient way to remove duplicates

Question

Following the answer in this thread "What's the most efficient way to erase duplicates and sort a vector?". I wrote the following code, but I got an error complaing no match for ‘operator<’ (operand types are ‘const connector’ and ‘const connector’) blahblah...

connector is a class I wrote myself, it basically is a line with two geometry points. uniqCntrs is a std::vector. It has 100% duplicates in it, which means each element has a duplicate, the size of uniqCntrs is quite big. What's wrong with my code, and how to deal with this situation?

std::set<connector> uniqCntrsSet;
for(unsigned int i = 0; i < uniqCntrs.size(); ++i )
{
    uniqCntrsSet.insert(uniqCntrs[i]);
}
uniqCntrs.assign(uniqCntrsSet.begin(), uniqCntrsSet.end());

Edit:

I have no idea how to define < operator for my connector class. I mean it is physically meaningless to say one line is smaller than the other.

`set` needs a way to compare objects of type `connector`, so you need to define the `<` operator, or provide one of the other ways to compare them (http://www.cplusplus.com/reference/set/set/set/) — AndyG, Mar 03 '14 at 19:35
Alternatively, since you said your vector is quite large, you can sort, and use the `std::unique_copy` or `std::unique`. It will require less memory. — Zac Howland, Mar 03 '14 at 19:38
Hmm, what if there is no way to compare two `connector`?? I guess what you are saying is that it is not a good idea to use `set` to remove duplicates in my situation...... I needs to find some other ways. — Daniel, Mar 03 '14 at 19:38
@Daniel How can you tell that some objects are duplicates if you cant compare them? — Sebastian Hoffmann, Mar 03 '14 at 19:39
@ZacHowland c++ sort doesn't require compare? Like define "<" in my `connector`? — Daniel, Mar 03 '14 at 19:40
@Paranaix I thought it would be enough if I have already defined "==" operator.... Why should I define/overload "<" operator? — Daniel, Mar 03 '14 at 19:41
@Paranaix: A class may support equality comparison without supporting relative ordering comparisons. — Benjamin Lindley, Mar 03 '14 at 19:42
@BenjaminLindley Yes, that is exactly my confusion, haha, you understand everything. :) — Daniel, Mar 03 '14 at 19:43
@Daniel: And to answer your query to Zac, yes, `std::sort` does require `operator<` or some other ordering comparison. — Benjamin Lindley, Mar 03 '14 at 19:46
@Zac Howland: and you may add does give more freedom in the ordering of the elements. — user2672165, Mar 03 '14 at 19:51
*" it is physically meaningless to say one line is smaller than the other."* -- That's not necessarily a limiting factor. It is meaningless to say that a 2d coordinate is less than another, but you can still sort them. You just have to pick, arbitrarily, either the x or the y property as the more significant. Is something like that impossible with your class? — Benjamin Lindley, Mar 03 '14 at 19:53
Oh, I see. You guys are absolutely right. I can define a "<" behavior myself. I got an idea. Since the connector is defined by pt1 and pt2. I will just define "<" as (pt1.id()+pt2.id()) < (anotherCntr.pt1.id()+anotherCntr.pt2.id()) something like that. I will try it out and let you know. — Daniel, Mar 03 '14 at 19:55
@Daniel: No, that is no good. What if, for example, `pt1.id() == 1`, and `pt2.id() == 2`, and `other.pt1.id() == 2` and `other.pt2.id() == 1`. That puts you in a situation where the objects are not equal (because their corresponding properties are not equal), but neither is one less than the other (because the sum of their properties is 3 in both cases). Instead, you should pick one of the properties as being more significant than the other. e.g. `if (pt1.id() < other.pt1.id()) return true; if (pt1.id() > other.pt1.id()) return false; return pt2.id() < other.pt2.id()` — Benjamin Lindley, Mar 03 '14 at 20:03
@Daniel Benjamin already addressed it, sort does require the ability to compare. I was simply referring to your chosen method of filtering unique items. The vector-set-vector will work (providing you have a comparison function that works for your data type), but requires that you double your memory footprint. For small data sets, this isn't a problem. For large data sets (which you indicated), this can be expensive. Sorting the existing data and eliminating non-unique items is less memory intensive in that case. — Zac Howland, Mar 03 '14 at 20:22

score 5 · Accepted Answer · answered Mar 03 '14 at 19:42

From cppreference:

std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare.

The second template argument of std::set, Compare, is defaulted to std::less which by defaults compares the objects with operator<. To fix the issue you can simply define operator< for your Key type (connector that is).

Flovdis · Answer 2 · 2014-03-03T21:10:04.670

3

Actually the operator< is just used to efficiently order the map which is used by std::set. It does not need to make any sense. The only requirement is that the operator satisfy the standard mathematical definition of a strict weak ordering.

Look at this point example:

class Point
{
public:
    Point(int x, int y) : x(x), y(y) {
    }

public:
    bool operator==(const Point &other) const {
        return x==other.x && y==other.y;
    }
    bool operator!=(const Point &other) const {
        return !operator==(other);
    }
    bool operator<(const Point &other) const {
        if (x==other.x) {
            return y<other.y;
        } else {
            return x<other.x;
        }
    }

private:
    int x;
    int y;
};

edited Mar 03 '14 at 21:10

answered Mar 03 '14 at 19:52

Flovdis

2,945
26
49

1

*"The only requirement is that the operator give predictable results." -- That's not the *only* requirement. The operator needs to satisfy the definition of a [strict weak ordering](https://www.sgi.com/tech/stl/StrictWeakOrdering.html), like your operator does. – Benjamin Lindley Mar 03 '14 at 20:22
Ben, you're right. One should be careful about the definition of "<". – Daniel Mar 03 '14 at 20:32
@BenjaminLindley You are right, this is what I meant with predictable results. I will edit my answer and also add your link. – Flovdis Mar 03 '14 at 21:08

Efficient way to remove duplicates

Edit:

2 Answers2