How to remove duplicates from a vector without sorting in order to preserve the order of objects in a vector?

  • one
    Similar question: Remove duplicates from std :: vector - AlexDenisov
  • What optimization requirements are there in terms of memory, speed? - gbg
  • without requirements. - perfect
  • @alexolut my question is the same but with the condition - perfect

4 answers 4

My solution. It seems to me that it is simpler and clearer than the answer @gbg

[unordered_]set <type> s; for (const auto &z : a) if (s.insert(a)) out.push_back(a);

We simply check if there is an element in the set, if not - then it is not duplicate and should be added to the answer, otherwise - a duplicate. Remains 1 element of all duplicates.

  • Yes, and quite so you can use - perfect
  1. Create a new vector based on the old one, but add the original index to the elements.
  2. Sort intermediate vector by value
  3. Delete non-unique elements
  4. Sort the intermediate vector by index
  5. Copy the results back
  • thank. beautiful solution. but the gbg algorithm is simpler. if it were possible to choose several correct answers, I would choose this answer. - perfect

As one of the options, first download everything to std::set :

 std::set<> s(a.begin(),a.end());

Then bang out of the array (and at the same time from the set ) everything that is not in the set , and do it faster, creating a new array.

 out.reserve(s.size); for(const auto& i : input) { const auto pos = s.find(i); if(pos != s.end()) // если мы ранее такое не встречали, тащим в выходной массив { out.push_back(i); s.erase(pos); // вот в чем цимес, из сета мы его убираем, и при новой встрече копировать не станем. } }

The version is much better (@pavel):

 for (auto z: a) if (s.insert(z)) out.push_back(z)
  • I understood from the question that if an item contains a duplicate, you only need to bang a duplicate, and not both items together. Your algorithm totally cleans everything up - Malov Vladimir
  • @MalovVladimir, everything is fine, if you need to save some of the duplicates, then we do it in the algorithm. I asked a question in the hope that there is a ready-made function - perfect
  • one
    Something I do not understand how your algorithm works. In set all elements will appear? - Pavel Mayorov
  • one
    @gbg why do you think that I have a second look? - Pavel Mayorov
  • one
    @gbg is now clear. It remains to write about the removal of an element from set in the description of the algorithm. - Pavel Mayorov

The difficulty is that “correctly delete” the concept is ambiguous. All previously proposed answers are based on time optimization, i.e. creation of an additional container, its sorting (albeit implicitly) and further transfer to the original vector.

But there is another option: do not use another container, but simply run over the existing one and delete all the same. Algorithmic complexity will certainly increase, but there will be a gain from memory.

Code example:

 void dropDup(std::vector<int>& v) { for( auto base = v.begin(); base != v.end(); ++base ) { for( auto it = base + 1; it != v.end(); ) { if( *base == *it ) { it = v.erase(it); } else { ++it; } } } }
  • I agree, but to be honest, I asked this question with the hope that there is some kind of ready-made function out of the box, something like unique without sorting , and there would be an optimization in the kit. - perfect
  • @perfect std::unique is optimal because uses only adjacent elements. More complex algorithms are probably implemented in some specialized libraries. But in std:: there are none. - αλεχολυτ