2

I have a list<pair<int , double>> lSeedList and an unordered_set<int> sToDelete. I want to remove the pairs in the list that have their first member equal to an int in sToDelete. Currently I am using the following code :

void updateSL(list<pair<int, double> >& lSeedList, const unordered_set<int>& sAddedFacets)
{
    list<pair<int, double> >::iterator it = lSeedList.begin();
    while(it != lSeedList.end())
    {
        if(sAddedFacets.count(it->first) != 0)
            it = lSeedList.erase(it);
        else
            ++it;
    }
}

Is there a way to speed up this code ? Is it possible to efficiently parallelize it with OpenMP (dividing the list in each thread and then merging them with splice) ?

I am using Visual Studio 2010 under Windows 7. The size of lSeedList is ~1 million at the start and the size of sToDelete is ~10000. The int in the pair acts like an unique ID.

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
Cyril
  • 559
  • 5
  • 17
  • 1
    You should look into the [`erase`-`remove` idiom](http://stackoverflow.com/questions/347441/erasing-elements-from-a-vector), which is essentially what you're shooting for. – Cory Kramer Dec 03 '14 at 13:46
  • @Cyril See my updated post. At first it has a typo in the lambda expression.:) – Vlad from Moscow Dec 03 '14 at 14:21

1 Answers1

2

It is better to use either standard algorithm std::remove_if

For exameple

lSeedList.erase( std::remove_if( lSeedList.begin(), lSeedList.end(),
                                 [&]( const std::pair<int, double> &p )
                                 {
                                     return sAddedFacets.count( p.first );
                                 } ),
                                 lSeedList.end() );

Or member function remove_if of class std::list

For example

lSeedList.remove_if( [&]( const std::pair<int, double> &p )
                     {
                         return sAddedFacets.count( p.first );
                     } );
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • I implemented the second option with a struct, and believe it or not my bit of code is apparently slightly faster :) I am going to try another methods using a boolean vector. Thanks for the help ! – Cyril Dec 03 '14 at 16:07