Boost Multi-Index remove elements using list of indexes-CodePudding

My multiindex looks like this:

using pair = std::pair<int, int>;

struct Hasher{
    std::size_t operator()(const int& k) const{
        return std::hash<int>()(k);
    }
};

using memberFirst = member<
            pair,
            pair::first_type,
            &pair::first
            >;
using memberSecond = member<
            pair,
            pair::second_type,
            &pair::second
            >;

using Container = multi_index_container<
    pair,
    indexed_by<
        random_access<>,
        hashed_non_unique<memberFirst, Hasher>,
        hashed_non_unique<memberSecond, Hasher>
        >
    >;

Container container;

I have std::vector<int> indexes{10, 32, 55, 66};. This vector represent indexes, what I want to remove.

When I remove something I have to preserve insert order. For example:

1,2,3,4,5,6,7,8,9 // remove {2,5,7}
1,3,4,6,8,9

To achieve this I can use:

int index = 0;
auto it = indexes.begin();
container.remove_if([&index, &it](auto& e){
    (void)e; //never use
    if(index   == *it){
          it;
        return true;
    }
    return false;
});

But it is not optimal way to do it, because I know exactly where to start looking for element: conteiner.begin() indexes[0]; and I don't know how elements are removed:

index was remove and other indexes were moved by one to the left
index was remove and other indexes were move by number of items removed before to the left

So my gool is something like this(pseudo c code):

iterator remove_if(iterator begin, iterator end, lambda){
    int moveBy = 0;
    while(begin != end){
        if(lambda(begin.value)){
              moveBy;
        }else if(moveBy){
            (begin-moveBy).value = begin.value;
        }
          begin;
    }
    return end-moveBy;
}

And I could use it like this:

container.erase(remove_if(container.begin() indexes[0], container.end(), [..](..){...}), container.end());

Or there is more clever way to do this.

Question: How can I implement it or how can I improve it!

CodePudding user response：

I'd use standard library algorithms here.

It strikes me that you can use the random_access iterator with std::stable_partition to sort all the removables at the end before erasing in bulk:

using Record = std::pair<int, int>;

struct Hasher : std::hash<int> { };
using memberFirst  = bmi::member<Record, Record::first_type, &Record::first>;
using memberSecond = bmi::member<Record, Record::second_type, &Record::second>;

using Container = bmi::multi_index_container<
    Record,                                          //
    bmi::indexed_by<                                 //
        bmi::random_access<>,                        //
        bmi::hashed_non_unique<memberFirst, Hasher>, //
        bmi::hashed_non_unique<memberSecond, Hasher> //
        >>;

I renamed the value type to Record to avoid confusion with std::pair

void remove_indices(Container& from, std::vector<int> const& removables) {
    std::vector<std::reference_wrapper<Record const>> //
        arrangement(from.begin(), from.end());

    auto pivot = std::stable_partition(
        arrangement.begin(), arrangement.end(), [&](Record const& rec) {
            auto index = from.iterator_to(rec) - from.begin();
            return (end(removables) ==
                    std::find(removables.begin(), removables.end(), index));
        });

    from.rearrange(begin(arrangement));
    auto n_remaining = pivot - arrangement.begin();
    from.erase(from.begin()   n_remaining, from.end());
}

Demo Live On Compiler Explorer:

Before [(1, 11), (2, 22), (3, 33), (4, 44), (5, 55), (6, 66), (7, 77), (8, 88), (9, 99)]
After [(1, 11), (2, 22), (4, 44), (5, 55), (7, 77), (9, 99)]

Simpler And More Efficient?

It strikes me that the complexity largely vanishes if you know that:

indexes are a fixed order
not duplicated

So, let's use that idea as well:

void remove_indices(Container& from, std::set<int, std::greater<> > const& descending) {
    for (auto& index : descending)
        from.erase(from.iterator_to(from[index]));
}

This trades efficiencies and complexities. Use taste and profilers to decide which version to use. See it live again:

Live On Compiler Explorer

#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index_container.hpp>
namespace bmi = boost::multi_index;

using Record = std::pair<int, int>;

struct Hasher : std::hash<int> { };
using memberFirst  = bmi::member<Record, Record::first_type, &Record::first>;
using memberSecond = bmi::member<Record, Record::second_type, &Record::second>;

using Container = bmi::multi_index_container<
    Record,                                          //
    bmi::indexed_by<                                 //
        bmi::random_access<>,                        //
        bmi::hashed_non_unique<memberFirst, Hasher>, //
        bmi::hashed_non_unique<memberSecond, Hasher> //
        >>;

void remove_indices(Container& from, std::set<int, std::greater<> > const& descending) {
    for (auto& index : descending)
        from.erase(from.iterator_to(from[index]));
}

#include <fmt/ranges.h>
int main() {
    Container container{
        {1, 11}, {2, 22}, {3, 33},   {4, 44},   {5, 55},   {6, 66},   {7, 77},
        {8, 88}, {9, 99},
    };

    fmt::print("Before {}\n", container);

    remove_indices(container, {2,5,7});
    fmt::print("After {}\n", container);
}

Prints

Before {(1, 11), (2, 22), (3, 33), (4, 44), (5, 55), (6, 66), (7, 77), (8, 88), (9, 99)}
After {(1, 11), (2, 22), (4, 44), (5, 55), (7, 77), (9, 99)}

Side Note

One of the main advantages of MultiIndex containers is that you don't have to settle for non-descript types like std::pair with nondescript names as first or second_type. Brrr. Much nicer:

Live On Compiler Explorer

#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index_container.hpp>

#include <fmt/ostream.h>
#include <fmt/ranges.h>
#include <iomanip>

namespace bmi = boost::multi_index;

struct Record {
    int age;
    std::string name;

    friend std::ostream& operator<<(std::ostream& os, Record const& r) {
        return os << "(" << std::quoted(r.name) << "," << r.age << ")";
    }
};

using Container = bmi::multi_index_container<
    Record,
    bmi::indexed_by<
        bmi::random_access<>,
        bmi::hashed_non_unique<bmi::member<Record, std::string, &Record::name>>,
        bmi::hashed_non_unique<bmi::member<Record, int, &Record::age>>
        >>;

void remove_indices(Container&                           from,
                    std::set<int, std::greater<>> const& descending)
{
    for (auto& index : descending)
        from.erase(from.iterator_to(from[index]));
}

int main() {
    Container container{
        {1, "Alyssa"}, {2, "Baya"},   {3, "Chom"},  {4, "Dirk"},  {5, "Evie"},
        {6, "Ferd"},   {7, "Gerald"}, {8, "Homer"}, {9, "Isala"},
    };

    fmt::print("Before {}\n", container);

    remove_indices(container, {7, 2, 5, 7});
    fmt::print("After {}\n", container);
}

Prints

Before {("Alyssa",1), ("Baya",2), ("Chom",3), ("Dirk",4), ("Evie",5), ("Ferd",6), ("Gerald",7), ("Homer",8), ("Isala",9)}
After {("Alyssa",1), ("Baya",2), ("Dirk",4), ("Evie",5), ("Gerald",7), ("Isala",9)}

CodePudding user response：

You can use relocate to efficiently move target elements to the end of the index and then erase them all in one fell swoop:

Live Coliru Demo

#include <algorithm>
#include <initializer_list>
#include <cassert>

template<typename RandomAccessIndex,typename FwdIterator>
void remove_positions(RandomAccessIndex& i,FwdIterator first,FwdIterator last)
{
  assert(std::is_sorted(first,last));
  
  std::size_t n=0;
  for(;first!=last;  first,  n){
    i.relocate(i.end(),i.begin() *first-n);
  }
  i.erase(i.end()-n,i.end());
}

template<typename RandomAccessIndex,typename Seq>
void remove_positions(RandomAccessIndex& i,const Seq& seq)
{
  remove_positions(i,seq.begin(),seq.end());
}

template<typename RandomAccessIndex>
void remove_positions(RandomAccessIndex& i,std::initializer_list<std::size_t> seq)
{
  remove_positions(i,seq.begin(),seq.end());
}

// testing

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/key.hpp>
#include <iostream>

using namespace boost::multi_index;
using pair=std::pair<int,int>;
using container=multi_index_container<
  pair,
  indexed_by<
    random_access<>,
    hashed_non_unique<key<&pair::first>>,
    hashed_non_unique<key<&pair::second>>
  >
>;

int main()
{
  container c={
    {0,0},{1,1},{2,2},{3,3},{4,4},
    {5,5},{6,6},{7,7},{8,8},{9,9}
  };
  
  remove_positions(c,{2,5,7});
  
  for(const pair& p:c)std::cout<<p.first<<" ";
}

Output

0 1 3 4 6 8 9