C++: Scott Meyers "Effective STL": item 31: know your sorting options: 帮助理解

Question

美好的一天!

Scott Meyers 在他的“Effective STL”中写道

第三种方法是使用有序的迭代器容器中的信息，以迭代方式将列表的元素拼接到您希望它们所在的位置。如您所见，有很多选择。(第 31 项，第二部分)

有人可以这样解释吗？

---

更多文字(理解上下文):

算法 sort、stable_sort、partial_sort 和 nth_element 需要随机访问迭代器，因此它们只能应用于 vector 、字符串、双端队列和数组。对标准关联容器中的元素进行排序是没有意义的，因为此类容器使用它们的比较函数来始终保持排序。我们可能想使用 sort、stable_sort、partial_sort 或 nth_element 但不能使用的唯一容器是 list，而 list 通过提供其 sort 成员函数来进行一些补偿。 (有趣的是，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()成员与排序 vector 中的迭代器一起将节点放入正确的顺序而不移动对象本身。

这看起来像这样:

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);
}