BOOST::INTRUSIVE Q4

Question

The following program doesn't act the way I expect it to. After executing

values.erase(
            std::remove_if(begin(values), end(values), std::mem_fn(&MyClass::bIsMarkedToDelete)));

I would think that values didn't contain any "Mike" and the length would be 7, or 11 - 4. Instead the "Mike" seems to be added to the end of std::vector<MyClass> value and the count is 10?

#include <vector>
#include <iostream>
#include <vector>
#include <functional>

#include <boost/intrusive/unordered_set.hpp>

namespace bic = boost::intrusive;

std::hash<std::string> hash_fn;

struct MyClass : bic::unordered_set_base_hook<bic::link_mode<bic::auto_unlink>>
{
    std::string name;
    int anInt1;
    mutable bool bIsMarkedToDelete;

    MyClass(std::string name, int i) : name(name), anInt1(i), bIsMarkedToDelete(false) {}

    bool operator==(MyClass const& o) const
    {
        //return anInt1 == o.anInt1 && name == o.name;
        return name == o.name;
    }

    struct hasher
    {
        size_t operator()(MyClass const& o) const
        {
            return o.anInt1;
            //return hash_fn(o.name);
        }
    };
};

typedef bic::unordered_set<MyClass, bic::hash<MyClass::hasher>, bic::constant_time_size<false> > HashTable;

int main()
{
    std::vector<MyClass> values
    {
        MyClass { "John", 0     },
        MyClass { "Mike",  1    },
        MyClass { "Dagobart", 2 },
        MyClass { "John", 3     },
        MyClass { "Mike",  4    },
        MyClass { "Dagobart", 5 },
        MyClass { "John", 6     },
        MyClass { "Mike",  7    },
        MyClass { "Dagobart", 8 },
        MyClass { "John", 9     },
        MyClass { "Mike", 10    }
    };

    HashTable::bucket_type buckets[100];
    HashTable hashtable(values.begin(), values.end(), HashTable::bucket_traits(buckets, 100));

    for(auto& e: values)
        std::cout << e.name << " ";

    std::cout << '\n';
    std::cout << "values size first " << values.size() << '\n';
    std::cout << "hash size fist " << hashtable.size() << '\n';

    for(auto& e: values)
        e.bIsMarkedToDelete |= ("Mike" == e.name);

    std::cout << "removing all with bIsMarkedToDelete";
    for(auto& e: values)
        if(e.bIsMarkedToDelete)
            std::cout << e.name << " ";

    std::cout << '\n';

    values.erase(
        std::remove_if(begin(values), end(values), std::mem_fn(&MyClass::bIsMarkedToDelete)));

    std::cout << "values size now " << values.size() << '\n';
    std::cout << "hash size now " << hashtable.size() << '\n';

    std::cout << "Contents of value after removing elements " << '\n';
    for(auto& e: values)
        std::cout << e.name << " ";

    std::cout << '\n';

    values.clear();

    std::cout << values.size() << '\n';
    std::cout << hashtable.size() << '\n';

    std::cout << "Done\n";

    int j;
    std::cin >> j;
}

Edit:

FIXED by replacing

values.erase(
    std::remove_if(std::begin(values), std::end(values), std::mem_fn(&MyClass::bIsMarkedToDelete),
                   std::end(values)));

by

for (auto it = values.begin();
          it != values.end();  /* nothing */)
{
    auto& e = *it;

    if(e.bIsMarkedToDelete)
    {
        //std::remove(e);

        it = values.erase(it);

        if(it == values.end())
            break;
    }
    else
    {
        //std::cout << "Provider not equal\n";
        ++it; // this is where we increment
    }
}

Edit 2:

Even better is

values.erase(
    std::remove_if(std::begin(values), std::end(values), std::mem_fn(&MyClass::bIsMarkedToDelete)),
                   std::end(values));

The erase-remove idiom requires the use of two iterators to erase: `values.erase(remove(..), values.end())` Removing the elements "moves" the elements you want to places before the iterator it returns. Then, you want to erase all elements after that iterator, until the end of the container. This is similar to partitioning the container into wanted and unwanted elements, and then erasing from the partition point to the end of the container. — dyp, Mar 22 '15 at 16:27
but this gives and error? values.erase( std::remove_if(std::begin(values), std::end(values), std::mem_fn(&MyClass::bIsMarkedToDelete), std::end(values))); — Ivan, Mar 22 '15 at 16:32
You placed the `std::end(values)` as an argument to `remove_if`. It should be an argument of `values.erase`. I.e. move the `)`. — dyp, Mar 22 '15 at 16:33
Thanks I had actually made this mistake before and forgot the answer. See the Edit above. — Ivan, Mar 22 '15 at 16:39
Alternatively, you can use `boost::remove_erase_if` [Live example](http://coliru.stacked-crooked.com/a/641ec9bdffb97f88) — dyp, Mar 22 '15 at 16:39
Your solution is rather inefficient: `erase` with a single argument performs O(N) assignments **for each iteration of your loop**, whereas the erase-remove idiom only performs O(N) assignments **in total**. — dyp, Mar 22 '15 at 16:41

BOOST::INTRUSIVE Q4

0 Answers0