permutations（2）

ちょっと工夫してあまりコピーが発生しないように書き直しました。

template<typename T>
class cPermutations : public cIterable<vector<T>> {
    typedef typename vector<T>::iterator    IT;
    template<typename T>
    class cPerm {
        typedef shared_ptr<cPerm<T>>    PTR;
        IT          begin;
        IT          end;
        PTR         g;
        const int   n;
        int         k;
        bool        first;
        
    public:
        cPerm(IT b, IT e, int m) :
                begin(b), end(e), n(m), k(0), first(true) { }
        
        bool exists_next() {
            if(first) {
                first = false;
                if(n <= 0) {
                    return true;
                }
                g = PTR(new cPerm<T>(begin + 1, end, n - 1));
                g->exists_next();
            }
            else {
                if(n == 0)
                    return false;
                else if(!g->exists_next()) {
                    if(k == end - begin - 1)
                        return false;
                    k++;
                    reverse(begin + 1, end);
                    T   front = *begin;
                    *begin = *(begin + k);
                    *(begin + k) = front;
                    g = PTR(new cPerm<T>(begin + 1, end, n - 1));
                    g->exists_next();
                }
            }
            return true;
        }
    };
    
    vector<T>   v;
    int             n;
    int             k;
    shared_ptr<cPerm<T>>    g;
    
public:
    cPermutations(const vector<T>& w, int m) : v(w), n(m), k(0),
            g(shared_ptr<cPerm<T>>(new cPerm<T>(v.begin(), v.end(), n))) { }
    
    bool exists_next() {
        return g->exists_next();
    }
    vector<T> value() const { return v; }
};

3倍程度速くなりましたが、ちゃんと書くよりかなり遅いです。