在不修改集合的情况下以排序顺序遍历集合的算法？

Question

我们假设我们有如下集合: {12, 10, 4, 5, 7}

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

我想到的是创建另一个指向元素的指针集合,然后对指针进行排序.

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

编辑:在我的情况下,我有一个vector<vector<double>>,我想基于内部向量的总和以非递增的顺序遍历外部向量集合.

Answer 1

如果您想在添加和删除元素时维持两个订单作为一个持续的事情，那么您可以使用 boost 多索引：

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;

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

编辑：

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

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如果需要，创建一个非常量迭代器。