13

我有一个 std::vector ,我需要为某些操作按选定的算法排序,但在其余时间保持其原始状态(例如,输入时排序的项目)。

显然,我可以使用 std::copy 创建一个临时向量并对其进行排序,但我想知道是否有更好的方法,可能是通过为输入的项目加上时间戳。

干杯

4

6 回答 6

22

您可以创建一个 std::vector 来保存第一个向量的所有索引。然后,您可以根据需要对索引向量进行排序。这应该很快,最重要的是,并不意味着您必须复制第一个向量(这可能更昂贵!)。

于 2010-02-22T17:33:05.677 回答
4

如果您不介意一点点 Boost,您可以使用 MultiIndex 库。请参阅我的这个答案,您可以在其中找到一些示例代码。

基本上,它允许您保留相同数据的多个“视图”,每个视图具有不同的顺序。在您的情况下,您将能够保留一个“序列”视图,其中数据按插入顺序(如矢量)和一个“排序”视图,其中数据根据某些标准(如地图)进行排序.

于 2010-02-22T17:42:22.147 回答
2

任何给定的向量在任何时候都将最多以一种方式排序。

有两种选择:

复制到临时向量并根据需要对其进行排序。除非向量非常大并且您的空间有限,否则这几乎肯定是最好的方法。即使您关心性能,制作副本的成本也将小于排序的成本,如果复制的成本很高,则排序将比复制慢得多。

或者,您可以保留某种方式(您提到的时间戳?)能够将向量排序回原始顺序。这会很慢,因为你只想在向量非常大的情况下这样做,但如果你不能制作一个临时向量,这是唯一的方法。

于 2010-02-22T17:33:12.090 回答
0

无论您要排序的项目是什么,您都可以将其包装在具有多个排序字段的结构中。

struct someThing
{
    int sortOrder1;
    int sortOrder2;
    ...
    int sortOrderN;
    //payload data object here
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear

(或者可能将排序顺序添加到基本结构本身?)

然后,当您需要时可以计算不同的排序顺序,并根据您需要的排序顺序重新排序您的列表。

于 2010-02-22T17:33:57.013 回答
0

我建议在每个vector. std::vector允许您提供不同的排序方法。此外,使用智能指针,当所有对项目的引用都被删除时,它们将自动销毁。

于 2010-02-22T18:12:46.470 回答
0

您可以创建另一个向量来存储索引。这是代码:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    vector<int> numbers = {50,30,20,10,40};
    vector<int> indexOfNumbers;
    
    for(int i = 0; i < numbers.size(); i++)
    {
        indexOfNumbers.push_back(i); 
    }
    // Now, indexOfNumbers = [0,1,2,3,4]

    std::sort(
        indexOfNumbers.begin(), indexOfNumbers.end(), 
        [numbers](int leftIndex, int rightIndex) 
        { 
            return numbers[leftIndex] < numbers[rightIndex]; // sort in ascending order
        }
    );
    // After sorting, indexOfNumbers = [3, 2, 1, 4, 0]

    // Access the sorted elements
    cout << "Accessing the sorted elements : ";
    for(int i = 0; i < numbers.size(); i++)
    {
        cout << numbers[indexOfNumbers[i]] << " ";
    }
    // prints numbers in sorted order i.e. [10,20,30,40,50]
   return 0;
}

来源:根据 Tyrer 的回答稍作修改(https://stackoverflow.com/a/47537314

于 2020-10-26T17:21:16.410 回答