Why does my "choose k from n" algorithm work with std::vector but not with std::map?

Question

I need a kind of iterator that allows me to iterate over all combinations of elements in a container (repetitions are allowed and {1,2}=={2,1}). I wrote this:

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

Using this on a 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";
}

... I get a runtime error. While with the vector I get the correct output (see also here):

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

counter = 6

Why does it break for a std::map when it works with a std::vector?

@Holt when I run it, it prints everything before `THIS IS NEVER...` and then only says `runtime error`, nothing more — 463035818_is_not_an_ai, Mar 02 '17 at 15:40
works perfectly for me - oh no wait - it errors out with BAD_ACCESS — Richard Hodges, Mar 02 '17 at 15:43
I think you're getting UB because the program is ill-formed. I am getting a segfault in the last pass of increment() — Richard Hodges, Mar 02 '17 at 15:46
For me, it doesn't work for `vector` either. It [prints garbage](http://rextester.com/NIYMIO4629) — Igor Tandetnik, Mar 02 '17 at 15:47
Same as @IgorTandetnik for `vector`. I think your code is over-complicated, and thus likely to contain UB, especially simply for retrieving combinations... — Holt, Mar 02 '17 at 15:48
`auto nexit = (*next)` Here, `next` may be `combo.end()` and thus not dereferenceable. — Igor Tandetnik, Mar 02 '17 at 15:49
@Holt the code was nice and bug free when I was counting `{1,2}` and `{2,1}` as different elements, but once it changed that, yeah it got overly complicated — 463035818_is_not_an_ai, Mar 02 '17 at 15:49
To help people answer your question, you'll need to be more specific about the error. Please [edit] your post to incorporate the exact errors you get from your [mcve] (preferably using copy+paste to avoid transcription errors). — Toby Speight, Mar 02 '17 at 15:51
@IgorTandetnik thanks, thats most probably it. Vote to close this question as OP should learn to use a debugger ;) — 463035818_is_not_an_ai, Mar 02 '17 at 15:51

score 2 · Accepted Answer · answered Mar 02 '17 at 16:01

Valgrind reports

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

Looking at line 17, it's here:

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

If next==combo.end(), then *next is an invalid reference.

score 1 · Answer 2 · edited May 23 '17 at 12:09

Fixed code using the bitmap method (see https://stackoverflow.com/a/28714822/2015579)

I am maintaining 2 vectors, one is a bitmap of enabled indexes which we can permute, the other is a vector of references to items in the container.

I have also offered a templated emit() function so the same generic code can operate on maps, vectors, sets, unordered_maps, etc.

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

expected output:

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

I was a bit too fast with accepting this.... Is it possible to use a similar method to get the combinations when repetitions are allowed? e.g. `A A` should be in the list — 463035818_is_not_an_ai, Mar 02 '17 at 17:29
In that case simply use std::next_permutation on the vector of references and drop the bitmap — Richard Hodges, Mar 02 '17 at 17:39
Ah I see. Well a quick search should find that algorithm, which you can retro fit into this class. The point is that I am storing a vector of references to simplify the expression of the algorithm. You can manipulate that vector as you wish. — Richard Hodges, Mar 03 '17 at 08:07
thanks for the help. I wasnt too happy about that `**it` either — 463035818_is_not_an_ai, Mar 04 '17 at 10:44

Why does my "choose k from n" algorithm work with std::vector but not with std::map?

2 Answers2