A multi-index where one index is a subset of the whole collection

Question

I would like to build a multi-index with two sequenced views, where I can remove values from only one view.

In code:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>

#include <algorithm>
#include <iterator>
#include <vector>

using namespace boost::multi_index;

typedef multi_index_container<
  int,
  indexed_by<
    sequenced<>,
    sequenced<> 
    > 
  > container;

int main()
{
  container c;
  std::vector<int> 
    // complete
    data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 
    // only uneven
    uneven_data;
  std::copy_if(begin(data), end(data), 
               std::back_inserter(uneven_data), 
               [](int i) { return i % 2 != 0; });

  container cont;
  std::copy(begin(data), end(data), std::back_inserter(cont));

  auto& idx0 = cont.get<0>();
  auto& idx1 = cont.get<1>();
  // remove all uneven from idx1
  idx1.remove_if([](int i) { return i % 2 == 0; });

  // behavior I would like to be true, but now both idx0 and idx1 are
  // equal to uneven_data
  assert(std::equal(begin(data), end(data), begin(idx0)));
  assert(std::equal(begin(uneven_data), end(uneven_data), begin(idx1)));

  return 0;
}

Is something like this possible with boost::multi_index?

Answer 1

No. In a boost multi_index_container, the indices are coupled together as separate views of the same values. This is an important guarantee of boost multi_index_containers.

"Boost.MultiIndex allows for the specification of multi_index_containers comprised of one or more indices with different interfaces to the same collection of elements" (boost multi_index tutorial).

With two distinct sequenced<> indices you can re-arrange the order in two different ways, but they must both contain all values.

If you wish to view a subset of elements according to a boolean predicate (eg: value is odd), consider using boost::filter_iterator. This does not attempt to erase values in the container but instead skip them during iteration.

Alternatively, selection/filtering can be obtained by ordering, using a multi_index ordered_non_unique index with an appropriate key extractor.

For example, an ordered_non_unique index based on a key extractor: [](int i) { return i % 2; } will place the odd and even values in distinct groups, so an iterator range to all odd values can be obtained using equal_range.

Answer 2

As I mentioned above, a more flexible (non-predicate based) approach using boost intrusive. Using two or more list hooks you can make one object participate in two or more sequences simultaneously.

#include <boost/intrusive/list.hpp>
#include <boost/foreach.hpp>

#include <algorithm>
#include <memory>

#include <iostream>
namespace intr = boost::intrusive;
template<class Value>
struct Sequence2
{
    typedef intr::link_mode< intr::auto_unlink > AutoUnlinkMode;
    typedef intr::list_member_hook< AutoUnlinkMode > SeqHook;

    struct Node
    {
        Node( const Value& i ) : value(i) {}

        operator Value&()
        {
            return value;
        }

        Value value;

        SeqHook mainHook;
        SeqHook hook0;
        SeqHook hook1;
    };

    typedef intr::member_hook< Node, SeqHook,&Node::mainHook > UsingMainHook;
    typedef intr::member_hook< Node, SeqHook,&Node::hook0 > UsingSeqHook0;
    typedef intr::member_hook< Node, SeqHook,&Node::hook1 > UsingSeqHook1;

    typedef intr::constant_time_size<false> NonConstantTimeSized;

    typedef intr::list< Node, UsingMainHook, NonConstantTimeSized > NodesList;
    typedef intr::list< Node, UsingSeqHook0, NonConstantTimeSized > Sequence0;
    typedef intr::list< Node, UsingSeqHook1, NonConstantTimeSized > Sequence1;

    NodesList nodes;
    Sequence0 seq0;
    Sequence1 seq1;

    typename NodesList::iterator insert( const Value& item )
    {
        Node* node = new Node(item);

        nodes.push_back( *node );

        typename NodesList::iterator iter = nodes.end(); iter--;
        seq0.push_back( *node );
        seq1.push_back( *node );
        return iter;
    }

    typename Sequence0::iterator iterator0( typename NodesList::iterator iter )
    {
        return seq0.iterator_to( *iter );
    }
    typename Sequence1::iterator iterator1( typename NodesList::iterator iter )
    {
        return seq1.iterator_to( *iter );
    }

    //! Erase from both sequences
    void erase( typename NodesList::iterator at )
    {
        nodes.erase_and_dispose( at, std::default_delete<Node>() );   
    }
    //! Erase from sequence 0
    void erase( typename Sequence0::iterator at )
    {
        Node& n = *at;

        assert( n.hook0.is_linked() );
        if( ! n.hook1.is_linked() )
        {
            seq0.erase_and_dispose( at, std::default_delete<Node>() );   
        }
        else
        {
            seq0.erase(at);
        }
    }
    //! Erase from sequence 1
    void erase( typename Sequence1::iterator at )
    {
        Node& n = *at;

        assert( n.hook1.is_linked() );
        if( ! n.hook0.is_linked() )
        {
            seq1.erase_and_dispose( at, std::default_delete<Node>() );   
        }
        else
        {
            seq1.erase(at);
        }
    }

    ~Sequence2()
    {
        nodes.clear_and_dispose( std::default_delete<Node>() );
    }
};

template< class T >
void show( Sequence2<T>& mseq, const std::string& comment )
{
    std::cout << comment << "\nseq 0:\t";
    BOOST_FOREACH( T& i, mseq.seq0 )
    {
        std::cout << i << " ";
    }
    std::cout << "\nseq 1:\t";
    BOOST_FOREACH( T& i, mseq.seq1 )
    {
        std::cout << i << " ";
    }
    std::cout << "\n\n";
}

int main(void)
{
    Sequence2< std::string > mseq;

    mseq.insert( "." );
    auto iterX = mseq.insert("X");
    auto iterY = mseq.insert("Y");
    auto iterZ = mseq.insert("Z");
    mseq.insert(".");
    mseq.insert(".");

    show(mseq, "start" );

    mseq.seq0.reverse();
    show(mseq, "after reverse seq0");    

    mseq.erase( mseq.iterator0(iterY) );
    show(mseq, "after erase Y in seq0");

    // Update a value in both sequences
    std::string& v = *iterZ;
    v = "z";
    show(mseq, "after modify Z in both");


    mseq.erase( iterX );
    show(mseq, "after erase X in both");

    mseq.erase( iterY );
    show(mseq, "after erase Y in both");

    return 0;
}

Which produces:

start
seq 0:  . X Y Z . . 
seq 1:  . X Y Z . . 

after reverse seq0
seq 0:  . . Z Y X . 
seq 1:  . X Y Z . . 

after erase Y in seq0
seq 0:  . . Z X . 
seq 1:  . X Y Z . . 

after modify Z in both
seq 0:  . . z X . 
seq 1:  . X Y z . . 

after erase X in both
seq 0:  . . z . 
seq 1:  . Y z . . 

after erase Y in both
seq 0:  . . z . 
seq 1:  . z . .