c++ - 在不修改集合的情况下按排序顺序遍历集合的算法？

Question

假设我们有一个如下所示的集合:{12, 10, 4, 5, 7}

我想保留集合的顺序，以便索引保持一致，但按排序顺序遍历集合，就像这样 {12, 10, 7, 5, 4} .

我想到的是再做一个指向元素的指针集合，然后对指针进行排序。

你有什么想法？是否已经用 C++ 实现了这样的算法？

编辑:在我的例子中，我有一个 vector<vector<double>>我想根据内部 vector 的总和以非递增顺序遍历外部 vector 集合。

Answer 1

如果你想在添加和删除元素的同时维护这两个订单作为一个持续的事情，那么你可以使用 boost multi-index:

http://live.boost.org/doc/libs/1_34_0/libs/multi_index/doc/tutorial/basics.html#multiple_sort

该页面中的这个示例几乎就是您想要的，只是以相反的顺序排序:

multi_index_container<
  int,
  indexed_by<
    sequenced<>,           // sequenced type
    ordered_unique<identity<int> > // another index
  >
> s;

如果您只想将其作为一次性操作，那么您对指针进行排序的想法听起来不错。作为一个细微的变体，您可以创建一个 vector std::pair<int,size_t> ，每对由一个值和其索引组成。然后用 std::sort 对 vector 对进行排序并指定 std::greater<std::pair<int,size_t> >作为比较器。

编辑:

鉴于您的实际情况，我肯定会建议对对进行排序，因为这样您只需计算一次每个内部 vector 的总和，并将其存储在对中。如果您只对指针/索引进行排序，则必须为每次比较计算两个总和。所以:

typedef vector<vector<double> >::const_iterator It;
typedef pair<double, It> Pair; 

vector<Pair> pairvec;
pairvec.reserve(input.size());

for (It it = input.begin(); it != input.end(); ++it) {
    // some people would split this over multiple lines
    pairvec.push_back(make_pair(accumulate(it->begin(), it->end(), 0.0), it));
}

sort(pairvec.begin(), pairvec.end(), greater<Pair>());

然后您可以迭代 pairvec。制作It如果需要的话，一个非常量迭代器。