Sunday, April 13, 2008

Remove duplicates from vector

Q. How do you remove duplicates from a vector?

A. This is how:

    template<typename T>
    void removeDuplicates(std::vector<T>& vec)
    {
        std::sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    }

If I needed a container to keep itself populated of only unique values, I would probably choose std::set but then choosing the right container depends on so many other different factors as well.

Edit Comment : Corrected above by replacing remove with erase as there isn't such a member function in std::vector. std::erase, however, is and the code works with just that replacement.

12 comments:

Alex K said...

Hi Abhishek,

I just tried your solution to remove duplicates - as I was looking for that.

First of all remove is not a method of vector - it should be erase. remove can be used with std::remove. So how can you compile that?

Second: When I tried to compile with the erase() function even more errors appeared pointing to a file called "algorithm".

Can you give a working solution - I'm using Visuall C++ 2005 Express.

Regards, Alex

abnegator said...

Hi Alex,

Thanks for pointing out the error. Yes, it should be vec.erase since there isn't a member remove(). I will correct the blog post. As for your problem, the following should compile fine:

//------CODE-------
#include <iostream>
#include <vector>
#include <algorithm>

void removeDuplicates(std::vector<int>& vec)
{

   std::sort(vec.begin(), vec.end());
   vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

int main()
{

   std::vector<int> vec(10);
   vec.push_back(20); vec.push_back(20);
   vec.push_back(30); vec.push_back(20);
   std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, "\t"));
   removeDuplicates(vec);
   std::cout << std::endl;
   std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, "\t"));
}
//---------CODE---------

Cheers!

Alex K said...

Hi again,

thx for your effort :) . In VC++ 2005 it works.

i didn't know that copying to an output-stream is so easy - nice version.

But there is still one thing i don't get. I have a special type I use in the vector, so the vector declaration looks like this:

typedef std::vector<alex::color> my_vec_t;

my_vec_t v;

Well, if I use your code with my type in the vector there are 18 erros pointing to the file "algoritm" (as before) - so what is the key to the solution aka door ^^?

Why does it only work with int? Any idea?

thx in advance,

Rgds, Alex

abnegator said...

Hi Alex,

Do you have operator< and operator== defined for your class? Those two would be needed. operator< for std::sort and operator== for std::unique.

For fundamental types like an "int" those operators are in-built but for the user defined classes they should be implemented. Usually, you should be able to find which operator is needed for which algorithm from the documentation. Sometimes though, it might not be as clear.

Hope this helps.

Cheers!

Alex K said...

Hi Abhishek,

actually I have a user-defined operator created as a struct - implemented with a "bigger than" operator (which should be no problem).

The code for such a user-defined sort is like this, right?:

std::sort(v.begin(), v.end(),userDefinedOperator);

this is how it worked for me.

But I have no idea how to code a "== operator".

I think the problem is that there's code from my lecturer at university which is a template to work with as a basis.

The error I get is that "the bool std::operator ==(...) could not be derived from alex::color".

So in fact it's a problem of implementation (as you said) - well I think I'm gonna stop trying to code as it is just an extra task to do - i think i've done more than i had to actually ;)

Thx for your time & effort,

Greets, Alex

Angelo said...

I didn't know about std::unique before... So this was a good illustration. However, I would like to point out that this code is quite inefficient because it employs sorting of the vector elements. Another problem is that the ordering of the vector elements will be lost once sorting is done. This may not be feasible in some cases.

Arthur said...

std::vector::erase() is also quite inefficient. If the first element is erased, every remaining element will be copied to its new position (an O(N) operation). This makes the remove duplicates O(N^2) because of erase...so the sort (O(N log N)) isn't even the biggest potential bottleneck.

If the original ordering does not matter, the following is an alternate approach that's a bit faster:

if (!v.empty())
{
std::vector u;
u.reserve(std::max(v.size() - guessAtNumberOfDuplicates, 1));

std::sort(v.begin(), v.end());

u.push_back(v.front());
for (std::vector::iterator it = v.begin() + 1; it != v.end(); ++it)
{
if (u.back() != *it)
u.push_back(*it);
}
u.swap(v);
}

(Sorry, blogger has removed the indentation and the template T on vector!)

admin said...

Apologies - I misread the example. erase() will only be called once in the original post. It will not be O(N^2) as I previously suggested. The erase(unique()) approach is likely to be as efficient as the vector copy approach.

jesus.dallas said...

amigo,

i found your example very useful.

thank you for your help,
jh, in dallas tx.

Jesus Mckinney said...

Irrespective of receiving daily oral or future injectable depot therapies, these require health care visits for medication and monitoring of safety and response. If patients are treated early enough, before a lot of immune system damage has occurred, life expectancy is close to normal, as long as they remain on successful treatment. However, when patients stop therapy, virus rebounds to high levels in most patients, sometimes associated with severe illness because i have gone through this and even an increased risk of death. The aim of “cure”is ongoing but i still do believe my government made millions of ARV drugs instead of finding a cure. for ongoing therapy and monitoring. ARV alone cannot cure HIV as among the cells that are infected are very long-living CD4 memory cells and possibly other cells that act as long-term reservoirs. HIV can hide in these cells without being detected by the body’s immune system. Therefore even when ART completely blocks subsequent rounds of infection of cells, reservoirs that have been infected before therapy initiation persist and from these reservoirs HIV rebounds if therapy is stopped. “Cure” could either mean an eradication cure, which means to completely rid the body of reservoir virus or a functional HIV cure, where HIV may remain in reservoir cells but rebound to high levels is prevented after therapy interruption.Dr Itua Herbal Medicine makes me believes there is a hope for people suffering from,Parkinson's disease,Schizophrenia,Cancer,Scoliosis,Fibromyalgia,Fluoroquinolone Toxicity
Syndrome Fibrodysplasia Ossificans Progressiva.Fatal Familial Insomnia Factor V Leiden Mutation ,Epilepsy Dupuytren's disease,Desmoplastic small-round-cell tumor Diabetes ,Coeliac disease,Creutzfeldt–Jakob disease,Cerebral Amyloid Angiopathy, Ataxia,Arthritis,Amyotrophic Lateral Sclerosis,Alzheimer's disease,Adrenocortical carcinoma.Asthma,Allergic diseases.Hiv_ Aids,Herpe ,Copd,Diabetes,Hepatitis,I read about him online how he cure Tasha and Tara so i contacted him on drituaherbalcenter@gmail.com even talked on whatsapps +2348149277967 believe me it was easy i drank his herbal medicine for two weeks and i was cured just like that isn't Dr Itua a wonder man? Yes he is! I thank him so much so i will advise if you are suffering from one of those diseases Pls do contact him he's a nice man.

juliana Erick said...

i am from USA, i am here to give my testimony how i was cured from HIV, i
contacted my HIV via blade. a friend of my use blade to peel of her
finger nails and drop it where she use it, so after she has left i did know
what came unto me i looked at my nails, my nails were very long and i took
the blade which she just used on her own nails to cut of my finger nails,
as i was maintaining my names, i mistakenly injured myself. i did even
bothered about it, so when i got to the hospital the next week when i was
ill the doctor told me that i am HIV positive, i wondered where did i got
it from so i remembered how i use my friend blade to cut off my hand so i
feel so sad in my heart to the extent that i don’t even know what to do, so
one day i was passing through the internet i met a testimony of a lady that all
talk about how she was cured by a doctor called DR Imoloa so i quickly
emailed the doctor email, and he also replied to me an told me the
requirements which i will provide and I do according to his command,
he prepare a herbal medicine for me which i took. he
called me the next week that i should go for a test which i did to my own
surprise i found that i was HIV negative. Thanks to him once more the great
doctor that cured me DR Imoloa so you can also emailed him at
{drimoloaherbalmademedicine@gmail.com} or whatssapp him on +2347081986098} God Bless you Sir.

juliana Erick said...

i am from USA, i am here to give my testimony how i was cured from HIV, i
contacted my HIV via blade. a friend of my use blade to peel of her
finger nails and drop it where she use it, so after she has left i did know
what came unto me i looked at my nails, my nails were very long and i took
the blade which she just used on her own nails to cut of my finger nails,
as i was maintaining my names, i mistakenly injured myself. i did even
bothered about it, so when i got to the hospital the next week when i was
ill the doctor told me that i am HIV positive, i wondered where did i got
it from so i remembered how i use my friend blade to cut off my hand so i
feel so sad in my heart to the extent that i don’t even know what to do, so
one day i was passing through the internet i met a testimony of a lady that all
talk about how she was cured by a doctor called DR Imoloa so i quickly
emailed the doctor email, and he also replied to me an told me the
requirements which i will provide and I do according to his command,
he prepare a herbal medicine for me which i took. he
called me the next week that i should go for a test which i did to my own
surprise i found that i was HIV negative. Thanks to him once more the great
doctor that cured me DR Imoloa so you can also emailed him at
{drimoloaherbalmademedicine@gmail.com} or whatssapp him on +2347081986098} God Bless you Sir.