c++通过使用旧 vector 进行预排序来改进 vector 排序

Question

我有一个具有以下 typdef 的对 vector

typedef std::pair<double, int> myPairType;
typedef std::vector<myPairType> myVectorType;
myVectorType myVector;

我用 double 填充这个 vector 值和 int该对的一部分是索引。然后 vector 看起来像这样

0.6594 1
0.5434 2
0.5245 3
0.8431 4
...

我的程序有许多时间步，在 double 中略有变化。值和每个时间步我用 std::sort 对这个 vector 进行排序到这样的事情。

0.5245 3
0.5434 2
0.6594 1
0.8431 4

现在的想法是以某种方式使用来自最后一个时间步骤的 vector (“旧 vector ，已经排序”)对当前 vector (新 vector ，尚未排序)进行预排序。并使用插入排序或 tim 排序来对然后预分类的 vector 的“其余部分”进行排序。

这有可能吗？我找不到按一个部分(int 部分)对"new" vector 对排序的函数。如果可能的话，这会比对整个未排序的"new" vector 进行排序更快吗？

感谢任何指向正确方向的指示。

时间

更新

首先感谢所有的建议和代码示例。我将查看它们中的每一个，并进行一些基准测试，看看它们是否会加快流程。

既然有一些关于 vector 的问题，我将尝试更详细地解释我想要完成的事情。

正如我所说，我有一个时间步数 1至 n .对于每个时间步，我都有一个 vector double具有大约 260000 个元素的数据值。

在每个时间步骤中，我都会向该 vector 添加一个索引，这将导致一个 vector 对 <double, int> .请参阅以下代码片段。

typedef typename myVectorType::iterator myVectorTypeIterator; // iterator for myVector
std::vector<double> vectorData; // holds the double data values
myVectorType myVector(vectorData.size()); // vector of pairs <double, int>

myVectorTypeIterator myVectorIter = myVector.begin();
// generating of the index
for (int i = 0; i < vectorData.size(); ++i) {
    myVectorIter->first = vectorData[i];
    myVectorIter->second = i;
    ++myVectorIter;
}

std::sort(myVector.begin(), myVector.end() );

(索引是基于 0 的。对于我在上面的例子中最初的错误感到抱歉)我对每个时间步都这样做，然后用 std::sort 对这个 vector 对进行排序.

现在的想法是使用时间步长对的排序 vector j-1 (让我们称之为 vectorOld )在时间步长 j作为"new"的“预分类器”myVector因为我假定已排序的"new"myVector 的顺序时间步长 j仅在某些情况下与已排序的 vectorOld 不同时间步长 j-1 .

对于“presorter”，我的意思是重新排列"new"中的对 myVector成一个 vector presortedVector类型 myVectorType按与 vectorOld 相同的索引顺序然后让 tim 排序或一些在预排序日期方面表现良好的类似排序算法进行其余排序。

一些数据示例:myVector的开头是这样的看起来像时间步j-1排序前。

0.0688015 0
0.0832928 1
0.0482259 2
0.142874 3
0.314859 4
0.332909 5
...

排序后

0.000102207 23836
0.000107378 256594
0.00010781 51300
0.000109315 95454
0.000109792 102172
...

所以我在下一个时间步j这是我的vectorOld我喜欢使用索引为 23836 的元素"new"myVector并将其放在presortedVector的第一位, 索引为 256594 的元素应该是 presortedVector 中的第二个元素等等。但元素必须保留其原始索引。所以256594不会是索引 0但在 presortedVector 中只有元素 0仍然有索引 256594

我希望这是对我的计划的更好解释。

Answer 1

首先，扫描序列以找到比前一个元素小的第一个元素(循环或 C++11 的 std::is_sorted_until )。这是未排序部分的开始。使用 std::sort在其余部分，然后将两半与 std::inplace_merge 合并.

template<class RandomIt, class Compare>
void sort_new_elements(RandomIt first, RandomIt last, Compare comp)
{
    RandomIt mid = std::is_sorted_until(first, last, comp);
    std::sort(mid, last, comp);
    std::inplace_merge(first, mid, last, comp);
}

这应该比不加区别地对整个序列进行排序更有效，只要前面的预排序序列明显大于未排序的部分即可。