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
  • 36,513
  • 20
  • 115
  • 270
Cyril
  • 559
  • 2
  • 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
  • 265,791
  • 20
  • 170
  • 303
  • 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