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

编辑：从您的集合中临时“删除”对象的一种可能方法是使用 astd::set<std::pair<T,bool>>并简单地写入it->second = falseand after it->second = true。然后，在迭代时，您可以跳过第二个值为 的条目false。这增加了一些开销，因为您在下降时必须做更多的工作。但是插入+删除元素每次都会增加对数开销，这可能更糟。

如果您使用（自定义）链接列表（也许您甚至可以std::list这样做），您可以非常便宜地删除和重新插入对象。

于 2012-04-03T22:33:57.883 回答