To speed up next_combination, we can store the state of generated combination so that it does not have to find which current combination elements correspond to the bigger collection. One way to do it is to store this state inside a class but this violates the design of STL algorithms. Another way to do it, is to pass this state to next_combination at every call. The declaration of next_combination and next_combination_with_state are listed below so that we can compare them side by side. The 1st one is current next_combination and 2nd one is overloaded one with 5th parameter as equality predicate and the 3rd is the new next_combination_with_state which also has 4 parameters as 1st next_combination but the last 2 parameters are of BidItIt type which is iterator whose value type is BidIt iterator. In other words, BidItIt is iterator of iterator! By storing BidIt iterator of n_begin and n_end itself, I could save some time without finding the range of r_begin and r_end that corresponds to n_begin and n_end. Reader may question if iterator of iterator violates the principle of STL algorithms as well. Well, it is one of the not-so-bad tradeoff, compared to alternative I just mentioned, we have to make for performance. We can expect performance gain of 4X to 10X, depending on how big n and r collection.

// Plain old next_combination
template <class BidIt>
inline bool next_combination(
    BidIt n_begin, 
    BidIt n_end,
    BidIt r_begin, 
    BidIt r_end);

// Plain old next_combination with equality predicate
template <class BidIt, class Prediate>
inline bool next_combination(
    BidIt n_begin, 
    BidIt n_end,
    BidIt r_begin, 
    BidIt r_end,
    Prediate Equal);

// New next_combination_with_state
// its state is stored in r_beginIT and r_endIT
// which iterators of BidIt iterators
template <class BidIt, class BidItIt>
inline bool next_combination_with_state(
    BidIt n_begin, 
    BidIt n_end,
    BidItIt r_beginIT, 
    BidItIt r_endIT);
	
// New next_combination_with_state does not have 
// version with equality predicate because it compare 
// with BidIt iterators, not elements which BidIt 
// iterator pointed to.

next_combination_with_state does not have version with equality predicate because it compare with BidIt iterators, not elements themselves.

I reproduce example of next_combination usage so that we can compare with the one of next_combination_with_state.

#include<iostream>
#include<vector>
#include<string>
#include"combination.h"

using namespace std;
using namespace stdcomb;

// for use with next_combination examples!
template<class BidIt>
void display(BidIt begin,BidIt end)
{
  for (BidIt it=begin;it!=end;++it)
      cout<<*it<<" ";
  cout<<endl;
}

//test next_combination() with iterators
int main()
{
  vector<int> ca;
  ca.push_back (1);
  ca.push_back (2);
  ca.push_back (3);
  ca.push_back (4);
  ca.push_back (5);
  ca.push_back (6);
  vector<int> cb;
  cb.push_back (1);
  cb.push_back (2);
  cb.push_back (3);
  cb.push_back (4);
   
  do
  {
    display(cb.begin(),cb.end());
  }
  while(next_combination(ca.begin (),ca.end (),cb.begin (),cb.end()) );
  
  cout<<"Complete!"<<endl;
  
  return 0;
}

The next_combination_with_state example is below. Instead of constructing a vector of integer for smaller collection, we construct cbit, a vector out of ca iterators. We also have a new display2 function to display the result, the main difference, it iterator is dereferenced twice, instead of once in display. Note, we cannot dereference first before passing to display because cbit.end() cannot be dereferenced as it is the one past the last valid iterator. Previously, I tried putting cbit.begin() and cbit.end() result back to cb, an already allocated vector. I got back the same performance, back to square one. Only use next_combination_with_state when you are comfortable with having your result as iterators of iterators. Since cbit stores ca iterators, ca must be kept alive while you still have cbit, else you got dangling iterators. next_combination_with_state requires C++17 because it uses reverse_iterator.

#include<iostream>
#include<vector>
#include<string>
#include"combination.h"

using namespace std;
using namespace stdcomb;

template<class BidItIt>
void display2(BidItIt begin, BidItIt end)
{
    for (BidItIt it = begin; it != end; ++it)
        cout << **it << " ";
    cout << endl;
}

//test next_combination_with_state() with iterators
int main()
{
  vector<int> ca;
  ca.push_back (1);
  ca.push_back (2);
  ca.push_back (3);
  ca.push_back (4);
  ca.push_back (5);
  ca.push_back (6);
  
  vector cbit;
  vector::iterator it = ca.begin();
  for(; it!=ca.end()-2; ++it)
    cbit.push_back(it);

  do
  {
    display2(cbit.begin(), cbit.end());
  }
  while(next_combination_with_state(ca.begin (),ca.end (),cbit.begin (),cbit.end () ) );
  
  cout<<"Complete!"<<endl;
  
  return 0;
}

The source code is hosted at Boost Concurrent Permutations and Combinations on CPU