How can I preserve sequenced order with an ordered_non_unique index?

Question

I have a boost::multi_index_container indexed by an ordered_non_unique key as well as sequenced. When I iterate over the non-unique index, the entries come out in the order they were added to the container rather than their position in the sequence.

How can I set up the non-unique index so that it preserves the insertion order? I tried making a composite_key with ordered_non_unique and sequenced, but since sequenced isn't a keyed index it doesn't compile.

Here's a minimal example (live version here):

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

#include <iostream>
#include <vector>

using namespace boost::multi_index;
using namespace std;

struct Entry {
    int nonUniqueInt;
    string somethingExtra;
};

using Container_t = multi_index_container<Entry, indexed_by<
    sequenced<>,
    ordered_non_unique<
        // ***** What can I put here? *****
        member<Entry, int, &Entry::nonUniqueInt>
    >
>>;

std::vector<Entry> const sampleData{
    {1, "first"}, {2, "second"}, {3, "third"}, {3, "fourth"}, {2, "fifth"}, {1, "sixth"}
};

// fillFront should make the sequence LIFO
template <typename T>
void fillFront(T & container) {
    for (auto & item : sampleData) {
        container.push_front(item);
    }
}

// fillBack should make the sequence FIFO
template <typename T>
void fillBack(T & container) {
    for (auto & item : sampleData) {
        container.push_back(item);
    }
}

int main() {
    Container_t container;
    auto & sequenced = container.get<0>();
    auto & ordered = container.get<1>();

    fillFront(sequenced);
    for(auto & entry : ordered) {
        cout << entry.nonUniqueInt << ": " << entry.somethingExtra << endl;
    }

    cout << endl;
    container.clear();

    fillBack(sequenced);
    for(auto & entry : ordered) {
        cout << entry.nonUniqueInt << ": " << entry.somethingExtra << endl;
    }
}

// Expected/desired output:   Actual output:
//  1: sixth                   1: first
//  1: first                   1: sixth
//  2: fifth                   2: second
//  2: second                  2: fifth
//  3: fourth                  3: third
//  3: third                   3: forth
//           
//  1: first                   1: first
//  1: sixth                   1: sixth
//  2: second                  2: second
//  2: fifth                   2: fifth
//  3: third                   3: third
//  3: forth                   3: forth

Answer 1

You want the items to "remain stable" for equivalent keys, in the ordered index.

Boost Multi Index doesn't support that. The "best" you could do is sort the iterators by their appearance in the insertion order index.

Use the random_access index for this.

using Container_t = multi_index_container<Entry, indexed_by<
    random_access<>,
    ordered_non_unique< member<Entry, int, &Entry::nonUniqueInt> >
>>;

Here's a demo:

int main() {
    Container_t container;
    auto & sequenced = container.get<0>();

    fillFront(sequenced);

    stabled_ordered(container, [](Entry const& entry) {
            cout << entry.nonUniqueInt << ": " << entry.somethingExtra << endl;
        });

    cout << endl;
    container.clear();

    fillBack(sequenced);
    stabled_ordered(container, [](Entry const& entry) {
            cout << entry.nonUniqueInt << ": " << entry.somethingExtra << endl;
        });
}

See it Live On Coliru.

The magic, of course, is stabled_ordered, which is a modified version of std::for_each taking a container and a functor:

template <typename Container, typename F, int RA = 0, int ONU = 1>
    F stabled_ordered(Container const& container, F&& f);

The implementation iterates the Order-Non-Unique index (indicated by the ONU template argument) and calls the functor, but in the insertion order (indicated by the RA (random_access) for ranges with equivalent keys:

template <typename Container, typename F, int RA = 0, int ONU = 1>
    F stabled_ordered(Container const& container, F&& f)
{
    using RAIt  = typename Container::template nth_index<RA> ::type::const_iterator;
    using ONUIt = typename Container::template nth_index<ONU>::type::const_iterator;
    auto& ordered = container.template get<ONU>();

    for(ONUIt cursor = ordered.begin(); cursor != ordered.end(); )
    {
        // get range with equiv. keys
        auto key_range = ordered.equal_range(ordered.key_extractor()(*cursor));
        cursor = key_range.second;

        // project into first index
        std::vector<RAIt> v;

        for(auto it = key_range.first; it != key_range.second; ++it)
            v.push_back(boost::multi_index::project<RA>(container, it));

        // put into original order
        std::sort(v.begin(), v.end());

        for_each(v.begin(), v.end(), [&f](RAIt const& it) { f(*it); });
    }

    return std::forward<F>(f);
}

Don't be intimidated by the typename .... ::template incantations: these are only there because I wanted to make the algorithm implementation more generic than you probably need :)