Sign in to follow this  
sheefo

std::list manipulation

Recommended Posts

sheefo    122
Hi. I need help with manipulating an unsorted std::list object to end up with only one of each duplicate element and all lone elements removed. Example: 1, 1, 2, 3, 3, 4, 4, 5, 6, 6 // the original list (sorted for display purpose) => 1, 1, 3, 3, 4, 4, 6, 6 // remove all lone elements => 1, 3, 4, 6 // remove duplicates Can anyone help me out? Thanks.

Share this post


Link to post
Share on other sites
SiCrane    11839
You could use a couple of sets to store information as you iterate over the list. Ex:

int main(int, char **) {
int data[] = { 1, 1, 2, 3, 3, 4, 4, 5, 6, 6 };

std::list<int> source(data, data + sizeof(data)/sizeof(int));
std::set<int> all;
std::set<int> dups;

for (std::list<int>::iterator i = source.begin();
i != source.end();
++i) {
if (all.count(*i))
dups.insert(*i);
else
all.insert(*i);
}
source.assign(dups.begin(), dups.end());

std::copy(source.begin(), source.end(), std::ostream_iterator<int>(std::cout, " "));

return 0;
}

Share this post


Link to post
Share on other sites
sheefo    122
Thanks guys. I figured it out.
I copied the unique() function and edited it to return the list without any lone elements. Then I can call unique() on it and I have my results :)


template<typename T>
std::list<T> unique2(std::list<T>& list)
{
std::list<T> newlist;
// erase each element matching previous
if (2 <= list.size()) {
// worth doing
std::list<T>::iterator _First = list.begin();
std::list<T>::iterator _After = _First;
for (++_After; _After != list.end();) {
if (*_First == *_After) {
newlist.push_back(*_First);
_After = list.erase(_After);
} else {
_First = _After++;
}
}
}
return newlist;
}

Share this post


Link to post
Share on other sites
sheefo    122
Sorry SiCrane. We posted at the same time :)

I think your method is better because it can work even when this list has 2 elements... also it looks better :P

Thank You!

Share this post


Link to post
Share on other sites
Icon    146
An alternative approach:

int main()
{
int data[] = { 1, 1, 2, 3, 3, 4, 4, 5, 6, 6 };

std::list<int> source(data, data + sizeof(data)/sizeof(int));

std::list<int> uniq;
unique_copy( source.begin(), source.end(), back_inserter(uniq) );

std::list<int> result;
set_difference( source.begin(), source.end(),
uniq.begin(), uniq.end(),
back_inserter(result) );

source.assign( result.begin(), result.end() );
}


I did not think about any space/time requirements though.. :)

It only works if by duplicates, you mean 'double'. If an item can occur more than 2 times you need to 'unique' the result as well. And you have to sort the list before doing this.

Share this post


Link to post
Share on other sites
Zahlman    1682

std::list<int>::iterator it = adjacent_find(sorted.begin(), sorted.end()), end = sorted.end();

while (it != end) {
result.push_back(*it);
it = adjacent_find(find_if(it, end, bind2nd(not_equal_to<int>(), *it)), end);
}

Share this post


Link to post
Share on other sites
chairthrower    440
or generically using either a std::map or hash table to hold a tuple consisting
of the value and count

int main()
{
int data[] = { 1, 1, 2, 3, 3, 4, 4, 5, 6, 6 };
std::list<int> source( data, data + sizeof( data)/sizeof(*data));

// typedef std::map< int, unsigned> map_type;
typedef __gnu_cxx::hash_map< int, unsigned> map_type;
map_type m;

BOOST_FOREACH( int v, source)
++m[ v];

source.clear();
BOOST_FOREACH( map_type::value_type v, m)
if( v.second > 1)
source.push_back( v.first) ;

BOOST_FOREACH( int v, source)
std::cout << v << " ";
}


[edit]hash table should give O(n) behavior

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this