- Mastering the C++17 STL
- Arthur O'Dwyer
- 201字
- 2021-07-08 10:20:24
Merges and mergesort
As long as we're on the topic of sorting algorithms, let's write sort a different way!
std::inplace_merge(a,mid,b) takes a single range [a,b) which has already been sorted with the equivalent of std::sort(a,mid) and std::sort(mid,b), and merges the two subranges together into a single sorted range. We can use this building block to implement the classic mergesort algorithm:
template<class RandomIt>
void sort(RandomIt a, RandomIt b)
{
auto n = std::distance(a, b);
if (n >= 2) {
auto mid = a + n/2;
std::sort(a, mid);
std::sort(mid, b);
std::inplace_merge(a, mid, b);
}
}
However, beware! The name inplace_merge seems to imply that the merging is happening "in-place" without the need for any additional buffer space; but this is not what happens in fact. In actuality, the inplace_merge function allocates a buffer for its own use, typically by calling operator new. If you are programming in an environment where heap allocation is problematic, then you should avoid inplace_merge like the plague.
The other standard algorithms that may allocate temporary buffers on the heap are std::stable_sort and std::stable_partition.
std::merge(a,b,c,d,o) is the non-allocating merge algorithm; it takes two iterator-pairs representing the ranges [a,b) and [c,d) and merges them into the output range defined by o.
- Learning Microsoft Windows Server 2012 Dynamic Access Control
- Web前端開發技術:HTML、CSS、JavaScript(第3版)
- Visual C++程序設計教程
- Getting Started with PowerShell
- HTML5 and CSS3 Transition,Transformation,and Animation
- Eclipse Plug-in Development:Beginner's Guide(Second Edition)
- Web程序設計(第二版)
- Mastering Apache Spark 2.x(Second Edition)
- Hands-On Swift 5 Microservices Development
- 自制編程語言
- SQL經典實例(第2版)
- 區塊鏈底層設計Java實戰
- Python語言實用教程
- Building Wireless Sensor Networks Using Arduino
- Android傳感器開發與智能設備案例實戰