How to remove duplicated elements from vector?

Question

Hence I have std::vector<type>.

Class type has no operator< but has operator==. Thus, I cannot sort my vector using std::unique.

How I can remove duplicated elements from vector?

Without ordering you've little chance to do this efficiently. unsorted (which it must be without ordering capabilities) will toss you straight into O(N^2) - land. — WhozCraig, Feb 24 '14 at 08:36
@WhozCraig: Not necessarily, if you can whip up a perfect hash you can do it in O(N). — Matthieu M., Feb 24 '14 at 08:38
@MatthieuM. If you can deliver a perfect hash, what is this doing in an unordered vector rather than an `std::unordered_set` in the first place? I was basing my claim given the *only* thing we had to work with is the OP's provided info. If they have a reasonable hash (perfect or not), then the X in this problem is "why am I using the wrong container for this?" And obviously I cannot say given such a hash it wouldn't work; clearly it would. — WhozCraig, Feb 24 '14 at 08:48
Actually, in this case I should find out whether my container holds duplicated elements, and after remove them. — Eduard Rostomyan, Feb 24 '14 at 08:59
@WhozCraig: maybe because sequence order is important ? maybe because a `vector` is more efficient for generic manipulations ? I don't know, I am not the OP. — Matthieu M., Feb 24 '14 at 09:53
@EduardRostomyan Since this question is already close, I can't do much for offering up a stop-gap solution. Given the constraints of your question as-presented, [**this may do what you want**](http://ideone.com/ArsKOa). It *should* work for the restrictions given, using only `operator ==` for equality comparison, though admittedly I only tested it on a simple scalar type. None the less, I hope it helps you out. Best of luck, sir. — WhozCraig, Feb 24 '14 at 10:49

score 1 · Accepted Answer · answered Feb 24 '14 at 08:37

I think best option is to write some binary predicate to use for the sorting of the vector and use std::unique afterwards. Keep in mind that the predicate must be transitive!

If this is not an option you can not do anything else but use the quardatic algorithm:

std::vector<type> a
std::vector<type> result;
for (unsigned i = 0; i < a.size(); ++i) {
  bool repeated = false;
  for (int j = 0; j < i; ++j) {
    if (a[j] == a[i]) {
      repeated = true;
      break;
    }
  }
  if (!repeated) {
    result.push_back(a[i]);
  }
}

// result stores the unique elements.

How to remove duplicated elements from vector?

1 Answers1