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.

14 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!)

ben 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.

Unknown 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.

Isabella Freddie 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.

Isabella Freddie 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.

gho said...

It’s a miracle that I am alive today. I encounter herpes virus for good four (4) years, six (6) months and twelve (12) day with my calculations, before I meet the great Dr. ODUWA. I am LEOKADIA STELLA Fresno California, united state of America and I was affected with herpes virus. Herpes is a viral infection cause by the Herpes simplex virus, marked by painful, watery blister in the skin or mucous membrane or on the genitals. This was what I suffered for good four years. I have visited CVS Pharmacy in Fresno for treatment but no improvement. I meet Dr. ODUWA online while I was searching for herpes cure I read a testimony about his work. I give a try that now becomes a testimony in my life. I contacted Dr. ODUWA via his E-mail (DR.ODUWASPELLHOME@GMAIL .COM) and he did not responds to me in time and I went back to the same testimony for his mobile number and I called him immediately (+2348070685053) and he respond to my call. He welcome me as a daughter and I explain my four years situation to him and he said is done just as I have contacted him and I believed in him. Dr. ODUWA sends me some herbal medication for herpes cure and he gave me instruction on what to do and I obeyed his instruction. Changes started after three days of applying the herbal medication. I went to the same CVS Pharmacy in Fresno for test and i was herpes negative. I do not know how to thanks Dr. ODUWA for saving my life. To God be the Glory, I am living healthy with my family today.

Indeed, Dr. ODUWA is a great man

and the only thing he requested from me is to share my Testimony for the world to see for a safe living from herpes viral disease and just as I did.

God bless Dr. ODUWA for his good work....contact hm on whatsapp +2348070585053

Tamara Barrow said...

I want to share this great testimony to the world on how Dr VOODOO cure me from HSV1&2 with his herbs, I was nervous when i first contact him about the cure for HSV but i decided to give him a try because i was desperate to get cured and be free from HSV. Dr VOODOO prepared the remedy and sent it to me through UPS,which I use just the way Dr VOODOO instructed me and thank God today I am a beneficiary to this cure and I went back to the hospital after 7 days of taking the herbs and I tested HSV1&2 Negative. So I will tell you all who are looking for a cure to his/her HSV1&2 that Dr VOODOO took research before he could finally get the solution to it and a lot of people are benefiting from him right now. He also cured my friend from HPV. Dr VOODOO heals with natural herbs. Please I urge you to contact him now through his email address: voodoospelltemple66@gmail.com or call and WhatsApp him on +2348140120719. He is capable of curing HIV/AIDS, HERPES, HPV, HSV1&2, CANCER of all kinds, DIABETES and so many other infections.