2

私はCプログラマーであり、C++を上手にしようとしています。（STLアルゴリズムを使用せずに）順列関数を実装したい。私は次のアルゴリズムを思いついた（私のCの考え方から）が、

a) it crashes for k > 2 (I suppose because the element that the iterator 
   points to, gets deleted, is inserted back and then incremented).
b) erase/insert operation seem unnecessary.

あなたの中のC++の専門家はそれをどのように実装しますか？

template <class T>
class Ordering {
    public:
          Ordering(int n);
          int combination(int k);
          int permutation(int k);
    private:
          set<T> elements;
          vector<T> order;
}

template <class T>
int Ordering<T>::permutation (int k) {
    if (k > elements.size()) {
        return 0;
    }

    if (k == 0) {
        printOrder();
        return 1;
    }

    int count = 0;
    for (typename set<T>::iterator it = elements.begin();
        it != elements.end();
        it++
    )
    {
        order[k-1] = *it;
        elements.erase(*it);
        count += permutation(k-1);
        elements.insert(*it);
    }
    return count;
}
4

1 に答える 1

0

問題は、セットに対する反復にありますelements。削除したイテレータをインクリメントしようとします。それはうまくいきません。

このアプローチの使用を主張する場合はit、を呼び出す前に、の後続を保存する必要がありますset::erase。つまり、forループのインクリメント部分をループに移動する必要があります。

このような：

for (typename set<T>::iterator it = elements.begin();
    it != elements.end();
    /* nothing here */
)
{
    order[k-1] = *it;
    typename set<T>::iterator next = it;
    ++next;
    elements.erase(*it);
    count += permutation(k-1);
    elements.insert(order[k-1]);
    it = next;
}

編集：セットからオブジェクトを一時的に「削除」する1つの可能な方法は、を作成し、その後にstd::set<std::pair<T,bool>>単純に書き込むことです。次に、反復中に、2番目の値が。であるエントリをスキップできます。下降中にさらに多くの作業を行う必要があるため、これにより少しオーバーヘッドが追加されます。ただし、要素の挿入と削除は毎回対数のオーバーヘッドを追加します。これはおそらくさらに悪いことです。it->second = falseit->second = truefalse

（カスタム）リンクリストを使用した場合（おそらくそれを実行することもできstd::listます）、オブジェクトを非常に安価に削除して再挿入できます。

于 2012-04-03T22:33:57.883 に答える