6

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
4

1 回答 1

6

对于有序索引中的等效键，您希望项目“保持稳定”。

Boost Multi Index 不支持这一点。您可以做的“最好”是按迭代器在插入顺序索引中的外观对迭代器进行排序。

为此使用 random_access 索引。

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

这是一个演示：

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;
        });
}

看到它住在 Coliru 上。

当然，神奇的是stabled_ordered，它是std::for_each采用容器和函子的修改版本：

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

实现迭代 Order-Non-Unique 索引（由ONU模板参数指示）并调用函子，但在插入顺序（由RA( random_access) 指示具有等效键的范围：

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);
}

不要被typename .... ::template咒语吓倒：这些只是因为我想让算法实现比你可能需要的更通用:)

于 2014-05-01T23:08:08.310 回答