C++:Scott Meyers"Effective STL":第31项:了解您的排序选项:帮助理解

Question

美好的一天!

在他的"有效STL"中,Scott Meyers写道

第三种方法是使用迭代器的有序容器中的信息迭代地将列表元素拼接到您希望它们所在的位置.正如您所看到的,有很多选项.(第31项,第2部分)

有人可以这样解释我吗？

---

更多文字(了解背景):

算法sort,stable_sort,partial_sort和nth_element需要随机访问迭代器,因此它们只能应用于向量,字符串,deques和数组.在标准关联容器中对元素进行排序是没有意义的,因为这样的容器使用它们的比较函数始终保持排序.我们可能希望使用sort,stable_sort,partial_sort或nth_element但不能的唯一容器是list,并且list通过提供其排序成员函数来进行补偿.(有趣的是,list :: sort执行稳定的排序.)如果要对列表进行排序,则可以,但如果要对列表中的对象使用partial_sort或nth_element,则必须间接执行.一种间接方法是将元素复制到具有随机访问迭代器的容器中,然后将所需的算法应用于该容器.另一种方法是创建一个list :: iterators的容器,在该容器上使用该算法,然后通过迭代器访问列表元素.第三种方法是使用迭代器的有序容器中的信息迭代地将列表元素拼接到您希望它们所在的位置.正如您所看到的,有很多选项.

Answer 1

我不确定混淆是什么，但我怀疑这就是“拼接”所指的：有std::list<T>一个splice()在列表之间传输节点的成员函数（好吧，实际上是几个重载）。也就是说，您创建一个并对其std::vector<std::list<T>::const_iterator>应用排序算法（例如）。std::partial_sort()然后，您创建一个新成员std::list<T>，并将该成员与排序向量中的迭代器一起使用splice()，以将节点按正确的顺序排列，而无需移动对象本身。

这看起来像这样：

std::vector<std::list<T>::const_iterator> tmp;
for (auto it(list.begin()), end(list.end()); it != end; ++it) {
    tmp.push_back(it);
}
some_sort_of(tmp);
std::list<T> result;
for (auto it(tmp.begin()), end(tmp.end()); it != end; ++it) {
    result.splice(result.end(), list, it);
}