Archived

This topic is now archived and is closed to further replies.

DerekSaw

Extract (and remove) duplicates...

Recommended Posts

Given a sorted container, is there any algorithms combo in STL to extract duplicates out into another empty container? Or better still, I''m thinking something like this: container1 elements: [1 2 2 3 3 4] after the process: container1 elements: [1 4] new container2 elements: [2 3]

Share this post


Link to post
Share on other sites
std::unique_copy and the erase member function on your container will get you from:

c1: [1 2 2 3 3 4]

to:

c2: [1 2 3 4]

std::set_difference will get you even further:

c1: [1 2 2 3 3 4]
c2: [1 2 3 4]
c3: [2 3]
c4: [1 4]



Update GameDev.net system time campaign - success at last

[edited by - dalleboy on March 8, 2003 11:28:24 AM]

Share this post


Link to post
Share on other sites

    
#include <vector>

#include <algorithm>

#include <iterator>

#include <iostream>

void print(const char* name, const std::vector<int>& vec)
{
std::vector<int>::const_iterator pIter = vec.begin();
const std::vector<int>::const_iterator pIterEnd = vec.end();
std::cout << name << ": ";
for (; pIter != pIterEnd; ++pIter)
{
std::cout << *pIter << " ";
}
std::cout << std::endl;
}

int main()
{
const int pStart[] = { 1, 2, 2, 3, 3, 4 };
std::vector<int> vecAll(pStart, pStart + 6);
print("vecAll", vecAll);
std::sort(vecAll.begin(), vecAll.end());
print("vecAll", vecAll);
std::vector<int> vecAllUniques;
vecAllUniques.reserve(vecAll.size());
std::unique_copy(vecAll.begin(), vecAll.end(), std::back_inserter(vecAllUniques));
print("vecAllUniques", vecAllUniques);
std::vector<int> vecOnlyDuplicates;
vecOnlyDuplicates.reserve(vecAll.size());
std::set_difference(vecAll.begin(), vecAll.end(), vecAllUniques.begin(), vecAllUniques.end(), std::back_inserter(vecOnlyDuplicates));
print("vecOnlyDuplicates", vecOnlyDuplicates);
std::vector<int> vecOnlyUniques;
vecOnlyUniques.reserve(vecAllUniques.size());
std::set_difference(vecAllUniques.begin(), vecAllUniques.end(), vecOnlyDuplicates.begin(), vecOnlyDuplicates.end(), std::back_inserter(vecOnlyUniques));
print("vecOnlyUniques", vecOnlyUniques);
}


[edited by - dalleboy on March 8, 2003 11:30:11 AM]

Share this post


Link to post
Share on other sites
You also may have to make the vecOnlyDuplicates result vector unique, it will contain duplicates itself if the original vector have more than 2 duplicates in a row:

vecAll: 1 2 2 3 3 3 4
vecAllUniques: 1 2 3 4
vecOnlyDuplicates: 2 3 3
vecOnlyUniques: 1 4

To fix this, do like this:
vecOnlyDuplicates.erase(std::unique(vecOnlyDuplicates.begin(), vecOnlyDuplicates.end()), vecOnlyDuplicates.end());



Update GameDev.net system time campaign - success at last

Share this post


Link to post
Share on other sites
Yeah, that kinda solve what I really want. Anyway thanks alot. Is there any other way with lesser step, of course, that is possible for STL?

//-----------
// your steps:
c1: [1 2 2 3 3 4]
c2: [1 2 3 4]
c3: [2 3]
c4: [1 4]

//-----------
// i hope:
c1: [1 2 2 3 3 4]
c2: [2 3]
c3: [1 4]


...Getting c2 from c1, all that I could think of is using custom loop.

Share this post


Link to post
Share on other sites