std::list manipulation
Author
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.
You gave yourself the answer already...
First, sort the list with std::sort.
Then it's trivial to find the loners and duplicates, because similar elements will be next to each other.
First, sort the list with std::sort.
Then it's trivial to find the loners and duplicates, because similar elements will be next to each other.
Author
Wow! Speedy replies :)
Thanks. But how do I remove the lone elements before calling unique()?
Thanks. But how do I remove the lone elements before calling unique()?
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;}
Author
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 :)
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;}
Author
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!
I think your method is better because it can work even when this list has 2 elements... also it looks better :P
Thank You!
An alternative approach:
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.
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.
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);}
or generically using either a std::map or hash table to hold a tuple consisting
of the value and count
[edit]hash table should give O(n) behavior
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 << " ";}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
