Jump to content
  • Advertisement
Sign in to follow this  
sheefo

std::list manipulation

This topic is 3629 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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
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
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
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

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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!