私の "choose k from n"アルゴリズムはstd :: vectorでは動作しますが、std :: mapでは動作しないのはなぜですか？

Question

コンテナ内の要素のすべての組み合わせを繰り返し処理できるような一種のイテレータが必要です（繰り返しは許可され、{1,2}=={2,1}）。 std::map ...

int main(){ 
    //std::vector<std::string> xx = {"A","B","C"}; 
    std::map<int,int> xx; 
    xx[1] = 1; 
    xx[2] = 2; 

    auto kn = createChooseKfromN(xx.begin(),xx.end(),2); 
    int counter = 0; 
    do { 
     for (auto it = kn.begin();it != kn.end();it++){ 
      std::cout << (**it).first << "\t"; 
     } 
     std::cout << "\n"; 
     counter++; 
    } while(kn.increment()); 
    std::cout << "counter = " << counter << "\n"; 
} 

でこれを使用して

#include <iostream> 
#include <map> 
#include <vector> 

template <typename T> 
struct ChooseKfromN{ 
    T mbegin; 
    T mend; 
    std::vector<T> combo; 
    ChooseKfromN(T first,T last,int k) : mbegin(first),mend(last),combo(k,first) {} 
    bool increment(){ 
     for (auto it = combo.begin();it!=combo.end();it++){ 
      if (++(*it) == mend){ 
       if (it != combo.end()){ 
        auto next = it; 
        next++; 
        auto nexit = (*next); 
        nexit++; 
        std::fill(combo.begin(),next,nexit); 
       } 
      } else { return true;} 
     } 
     std::cout << "THIS IS NEVER REACHED FOR A MAP !! \n" << std::endl; 
     return false; 
    } 
    typename std::vector<T>::const_iterator begin(){ return combo.begin();} 
    typename std::vector<T>::const_iterator end() { return combo.end();} 
}; 

template <typename T> 
ChooseKfromN<T> createChooseKfromN(T first,T last,int k) { 
    return ChooseKfromN<T>(first,last,k); 
} 

...私はランタイムエラーを取得する：私はこれを書きました。ベクターで私は正しい出力を取得しますが（もhereを参照してください）：それはstd::vectorで動作するとき

A A 
B A 
C A 
B B 
C B 
C C 
THIS IS NEVER REACHED FOR A MAP !! 

counter = 6 

は、なぜそれがstd::mapのために壊すのか？

Answer 1

Valgrindのは、ライン17を見ると

==32738== Invalid read of size 8 
==32738== at 0x109629: ChooseKfromN<std::_Rb_tree_iterator<std::pair<int const, int> > >::increment() (42559588.cpp:17) 
==32738== by 0x108EFE: main (42559588.cpp:43) 
==32738== Address 0x5a84d70 is 0 bytes after a block of size 16 alloc'd 
==32738== at 0x4C2C21F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==32738== by 0x10B21B: __gnu_cxx::new_allocator<std::_Rb_tree_iterator<std::pair<int const, int> > >::allocate(unsigned long, void const*) (new_allocator.h:104) 
==32738== by 0x10B113: std::allocator_traits<std::allocator<std::_Rb_tree_iterator<std::pair<int const, int> > > >::allocate(std::allocator<std::_Rb_tree_iterator<std::pair<int const, int> > >&, unsigned long) (alloc_traits.h:416) 

を報告し、それがここにあります：

  if (it != combo.end()){ 
       auto next = it; 
       next++; 
       auto nexit = (*next); // Line 17 
       nexit++; 

== combo.end()next場合、*nextが無効な参照です。

Answer 2

ビットマップ方式を使用して固定コード（https://stackoverflow.com/a/28714822/2015579を参照）

私は他のコンテナ内のアイテムへの参照のベクトルで、1は我々が並べ替えることができます有効インデックスのビットマップで、2つのベクトルを維持しています。

同じ汎用コードはマップ、ベクトル、セット、unordered_mapsなどを操作することができますので、私は

#include <iostream> 
#include <map> 
#include <vector> 
#include <functional> 
#include <iterator> 


template <typename Iter> 
struct ChooseKfromN 
{ 
    using iterator_type = Iter; 
    using value_type = typename std::iterator_traits<iterator_type>::value_type; 
    using result_type = std::vector<std::reference_wrapper<const value_type>>; 

    result_type values_; 
    std::vector<bool> bitset_; 
    int k_; 

    ChooseKfromN(Iter first,Iter last,int k) 
     : values_(first, last) 
     , bitset_(values_.size() - k, 0) 
     , k_(k) 
    { 

     std::reverse(values_.begin(), values_.end()); 
     bitset_.resize(values_.size(), 1); 
    } 

    result_type& get(result_type& target) const 
    { 
     target.clear(); 

     for (std::size_t i = bitset_.size() ; i ;) { 
      --i; 
      if (bitset_[i]) { 
       target.push_back(values_[i]); 
      } 
     } 
     return target; 
    } 

    bool increment(){ 
     return std::next_permutation(bitset_.begin(), bitset_.end()); 
    } 
}; 

template <typename T> 
ChooseKfromN<T> createChooseKfromN(T first,T last,int k) { return ChooseKfromN<T>(first,last,k); } 


template<class T> 
std::ostream& emit_key(std::ostream& os, const T& t) 
{ 
    return os << t; 
} 

template<class K, class V> 
std::ostream& emit_key(std::ostream& os, const std::pair<const K, V>& kv) 
{ 
    return os << kv.first; 
} 

template<class Container> 
void test(Container const& c) 
{ 
    auto kn = createChooseKfromN(c.begin(),c.end(),2); 
    using ChooserType = decltype(kn); 
    using ResultType = typename ChooserType::result_type; 

    int counter = 0; 
    ResultType result_buffer; 
    do { 
     kn.get(result_buffer); 
     for (auto&& ref : result_buffer) 
     { 
      emit_key(std::cout, ref.get()) << '\t'; 
     } 
     std::cout << "\n"; 
     counter++; 
    } while(kn.increment()); 
    std::cout << "counter = " << counter << "\n"; 
} 


int main(){ 
    std::map<int,int> xx; 
    xx[1] = 1; 
    xx[2] = 2; 
    xx[3] = 3; 
    xx[4] = 4; 

    std::vector<std::string> yy = {"A","B","C"}; 

    test(xx); 
    test(yy); 
} 

テンプレートemit()機能をも提供している予想される出力：

1 2 
1 3 
2 3 
1 4 
2 4 
3 4 
counter = 6 
A B 
A C 
B C 
counter = 3