我有一个具有以下 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
我希望这是对我的计划的更好解释。
最佳答案
首先,扫描序列以找到比前一个元素小的第一个元素(循环或 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);
}
这应该比不加区别地对整个序列进行排序更有效,只要前面的预排序序列明显大于未排序的部分即可。
关于c++通过使用旧 vector 进行预排序来改进 vector 排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28812746/