c++ - 如何使用 ordered_non_unique 索引保留顺序？

Question

我有一个 boost::multi_index_container 由一个 ordered_non_unique 键索引并排序。当我遍历非唯一索引时，条目按照它们添加到容器中的顺序出现，而不是它们在序列中的位置。

如何设置非唯一索引以保留插入顺序？我尝试使用 ordered_non_unique 和 sequenced 制作一个 composite_key，但由于 sequenced 不是键控索引，因此无法编译。

这是一个最小的例子(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

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

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

查看 Live On 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 咒语吓倒:这些只是因为我想让算法实现比你可能需要的更通用:)