迭代通过无序的多图

Question

我已经在我的unordered_multimap中插入了一些元素，我发现所有值映射到使用相同范围的密钥k。现在我想通过它们的插入顺序遍历这些映射值。查看代码以获得更好的理解。

#include <iostream> 
#include <unordered_map> 
using namespace std; 
int main() 
{ 
    unordered_multimap<int,int> m; 
    m.insert(make_pair(1,2)); 
    m.insert(make_pair(1,3)); 
    m.insert(make_pair(1,4)); 
    auto it = m.equal_range(1); 
    for(auto it1 = it.first; it1 != it.second; it1++) { 
     cout<<it1->second<<endl; 
    } 
} 

输出：

4 
3 
2 

但我想在其中键和映射值插入的顺序遍历。所以，我想按顺序遍历2,3,4。可能吗？

Answer 1

有没有一种简单的方式来做你所要求的。当元素被插入到有序或无序的multimap中时，它们实际上被放置在内部结构中，并且不知它们按照何种顺序放置。

你应该有一个辅助例如一个std::queue容器，用于将迭代器追加到插入的元素。

auto inserted_pos = m.insert(make_pair(1,4));

请记住，迭代器插入时不会失效：迭代器可以从插入的获得。如果元素被删除，它们将失效，并且仅限于相关元素。

Answer 2

这里有一种方法来实现你想要的。

它使用boost::multi_index提供的一些技术。

请注意使用project将一个索引中的迭代器转换为另一个索引中的迭代器。

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <utility> 

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


namespace example { 
    struct by_id {}; 
    struct by_insertion_order {}; 

    using namespace boost; 
    using namespace boost::multi_index; 


    using item_type = std::pair<int, int>; 

typedef multi_index_container< 
    item_type,   // what we are storing 
    indexed_by< 
     // unordered multimap-type index 
     hashed_non_unique<tag<by_id>, member<item_type, int, &item_type::first> >, 

     // sequence-type index - records insertion order 
     sequenced<tag<by_insertion_order>> 
    > 
> my_store; 

    using const_insertion_sequence_iterator = decltype(std::declval<my_store>().get<by_insertion_order>().cbegin()); 

    using const_by_id_iterator = decltype(std::declval<my_store>().get<by_id>().cbegin()); 

    // convert a range of 'by_id' iterators to an ordered vector 'by_insertion_sequence' iterators 
    // @param store is a reference to the store for which the iterators are valid 
    // @param first is the first by_id iterator in the filtered range 
    // @param last is the 'one past the end' iterator of the filtered range 
    // @returns a vector of iterators to items ordered by insertion sequence 
    auto 
    projected_to_insertion_order(const my_store& store, 
           const_by_id_iterator first, 
           const_by_id_iterator last) 
    -> std::vector<const_insertion_sequence_iterator> 
    { 
     std::vector<const_insertion_sequence_iterator> result; 

     for (; first != last ; ++first) { 
      result.push_back(store.project<by_insertion_order>(first)); 
     } 

     sort(result.begin(), 
      result.end(), 
      [&store](const auto& il, const auto& ir) { 
       return distance(store.get<by_insertion_order>().cbegin(), il) 
       < distance(store.get<by_insertion_order>().cbegin(), ir); 
      }); 

     return result; 
    } 

} 


int main() 
{ 
    using namespace std; 
    using example::my_store; 
    using example::by_id; 
    using example::by_insertion_order; 
    using example::projected_to_insertion_order; 

    // define store 
    my_store m; 

    // add some items 
    m.get<by_id>().emplace(1,2); 
    m.get<by_id>().emplace(3,6); 
    m.get<by_id>().emplace(1,3); 
    m.get<by_id>().emplace(2,5); 
    m.get<by_id>().emplace(1,4); 

    // get range of items filtered by id 
    auto ip = m.get<by_id>().equal_range(1); 

    cout << "filtered but unordered\n"; 
    for (auto it = ip.first ; it != ip.second ; ++it) { 
     cout << it->first << ":" << it->second << endl; 
    } 

    // project that to a vector of iterators to items ordered by insertion sequence 

    cout << "filtered and ordered by insertion sequence\n"; 
    for (const auto& it : projected_to_insertion_order(m, ip.first, ip.second)) { 
     cout << it->first << ":" << it->second << endl; 
    } 
} 

预期输出：

filtered but unordered 
1:4 
1:3 
1:2 
filtered and ordered by insertion sequence 
1:2 
1:3 
1:4