c++ - 为什么我的“从n中选择k”算法只能与std::vector一起使用，而不能与std::map一起使用？

我需要一种迭代器，该迭代器可以迭代容器中元素的所有组合（允许重复和{1,2}=={2,1}）。我这样写：

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

在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";
}

...我收到运行时错误。使用向量时，我得到了正确的输出（另请参见here）：

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

counter = 6

为什么std::map与std::vector一起使用时为什么会中断？

最佳答案

Valgrind报告

==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)

查看第17行，它在这里：

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

如果next == combo.end()，则*next是无效的引用。

关于c++ - 为什么我的“从n中选择k”算法只能与std::vector一起使用，而不能与std::map一起使用？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42559588/