修改具有 hashed_non_unique 键的 Boost 多索引映射中的键范围

Question

我正在尝试更新多索引映射中的一系列元素，但它似乎比我预期的要复杂一些。

鉴于以下声明：

struct Information {

    int number() const {
        return number_;
    }

    int number_;
};


typedef boost::multi_index_container<
        Information, 
        boost::multi_index::indexed_by<
                boost::multi_index::hashed_non_unique<
                        boost::multi_index::tag<int>,
                        boost::multi_index::const_mem_fun<
                                Information, 
                                int, 
                                &Information::number
                        >
                >
        >
    > Information_Map;

Information_Map information_map_;

以下是对上述声明内容的总结：

• 一个 struct Information，它包含一个任意数字，它不是唯一的
• 具有以下属性的多索引映射
• • 包含类型元素 Information
• • 元素使用非唯一散列进行索引
• • 散列的键是使用成员函数构造的 Information::number()

现在，我也宣布了这样的事情：

struct Plus_One_Modifier {
    void operator()(Information& obj) const {
        obj.number_ += 1;
    }
};

前面的struct是一个修饰符，预计在调用modify函数时会用到：

// from boost/multi_index/hashed_index.hpp
template<typename Modifier> bool modify(iterator position,Modifier mod);

当此函数仅用于修改一个元素时，一切都按预期工作：

// Updates the first element
Information_Map::index<int> index = information_map_.get<int>();
index.modify(index.begin(), Plus_One_Modifier());

该问题是，在一个特殊的情况，我必须更新整个容器，是这样的：

// Update the whole container the first element
Information_Map::index<int> index = information_map_.get<int>();
for (Information_Map::index<int>::iterator it = index.begin();
     it != index.end();
     ++it) {
    index.modify(it, Plus_One_Modifier());
}

在大多数情况下，前面的代码无法遍历整个容器，在某些时候迭代器会以++it等于的方式修改end。

我发现使用第三个变量似乎可以缓解这个问题，但我不相信它是正确的，因为它比容器中的元素进行了更多的迭代。

// Update the whole container the first element
Information_Map::index<int> index = information_map_.get<int>();
Information_Map::index<int>::iterator begin = index.begin();
Information_Map::index<int>::iterator end = index.end();
while (begin != end) {
    Information_Map::index<int>::iterator it = begin++;
    index.modify(it, Plus_One_Modifier());
}

所以，问题是：

• 我想修改容器中的所有元素
• 修改元素会影响元素在容器中的索引方式，即：修改键
• 修改键会影响元素在容器中的存储方式，这意味着迭代器可能会变得有点混乱

我正在寻找一种安全的方式来更新容器中的一系列元素。

我想到的唯一解决方案如下：

• 列出容器中的所有元素
• 浏览列表并一一修改元素

这样就可以了，但是性能影响太大了

任何帮助将不胜感激

Answer 1

您无法可靠地迭代变异下的散列容器。这并非特定于 Boost Multi Index：

• 迭代器失效规则

您可以使用辅助索引进行迭代：

Live On Coliru

auto& aux = information_map_.get<idx_auxiliary>();
auto& idx = information_map_.get<idx_main>();

size_t iterations = 0;
for(auto rait = aux.begin(); rait != aux.end(); ++rait, ++iterations) {
    auto it = bmi::project<idx_main>(information_map_, rait);
    idx.modify(it, Plus_One_Modifier());
}

// iterations is equal to `information_map_.size()`

当然，请确保辅助索引在您在循环中进行的修改下具有稳定的迭代器。一个有序的索引也可能适合这个目的。

完整演示

Live On Coliru

#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/mem_fun.hpp>

struct Information {
    Information(int n = 0) : number_(n) {}

    int number_;
    int number() const { return number_; }
};

static std::ostream& operator<<(std::ostream& os, Information const& i) {
    return os << i.number();
}

namespace bmi = boost::multi_index;

typedef boost::multi_index_container<Information, 
    bmi::indexed_by<
        bmi::hashed_non_unique<
            bmi::tag<struct idx_main>,
            bmi::const_mem_fun<Information, int, &Information::number>
        >,
        bmi::random_access<bmi::tag<struct idx_auxiliary> >
    >
> Information_Map;

struct Plus_One_Modifier {
    void operator()(Information& obj) const { obj.number_ += 1; }
};

#include <iostream>

int main() {
    Information_Map information_map_;
    std::generate_n(std::inserter(information_map_, information_map_.end()), 50, [] { return rand()%20; });

    // Updates the first element
    auto& aux = information_map_.get<idx_auxiliary>();
    auto& idx = information_map_.get<idx_main>();

    std::copy(aux.begin(), aux.end(), std::ostream_iterator<Information>(std::cout, " "));

    size_t iterations = 0;
    for(auto rait = aux.begin(); rait != aux.end(); ++rait, ++iterations) {
        auto it = bmi::project<idx_main>(information_map_, rait);
        idx.modify(it, Plus_One_Modifier());
    }

    std::cout << "\nIterations done: " << iterations << "\n";
    std::copy(aux.begin(), aux.end(), std::ostream_iterator<Information>(std::cout, " "));
}

输出：

3 6 17 15 13 15 6 12 9 1 2 7 10 19 3 6 0 6 12 16 11 8 7 9 2 10 2 3 7 15 9 2 2 18 9 7 13 16 11 2 9 13 1 19 4 17 18 4 15 10 
Iterations done: 50
4 7 18 16 14 16 7 13 10 2 3 8 11 20 4 7 1 7 13 17 12 9 8 10 3 11 3 4 8 16 10 3 3 19 10 8 14 17 12 3 10 14 2 20 5 18 19 5 16 11