9

再会！

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

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

有人可以这样解释我吗？

更多文字（以了解上下文）：

算法 sort、stable_sort、partial_sort 和 nth_element 需要随机访问迭代器，因此它们可能仅适用于向量、字符串、双端队列和数组。对标准关联容器中的元素进行排序是没有意义的，因为这些容器使用它们的比较函数来始终保持排序。我们可能希望使用 sort、stable_sort、partial_sort 或 nth_element 但不能使用的唯一容器是 list，而 list 通过提供它的 sort 成员函数来进行一些补偿。（有趣的是，list::sort 执行稳定的排序。）如果要对列表进行排序，则可以，但是如果要对列表中的对象使用 partial_sort 或 nth_element，则必须间接进行。一种间接方法是将元素复制到具有随机访问迭代器的容器中，然后对其应用所需的算法。第三种是使用迭代器的有序容器中的信息将列表的元素迭代地拼接到您希望它们所在的位置。如您所见，有很多选项。

4

5 回答 5

3

我不确定混淆是什么，但我怀疑它是“拼接”所指的：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);
}
于 2012-02-09T23:59:10.690 回答
2

假设您想partial_sort在清单上做一个。您可以通过提供可以使用迭代器进行排序的比较函数将迭代器存储到集合中的列表中，如下所示：

struct iterator_less
{   
    bool operator() (std::list<int>::iterator lhs,
                 std::list<int>::iterator rhs) const
    {
        return (*lhs < *rhs);
    }
};
typedef std::multiset<
    std::list<int>::iterator, iterator_less
> iterator_set;

您可以让 set 执行排序，但由于它包含要列出的迭代器，您可以 list::splice 将它们拼接成一个 partial_sorted 列表：

std::list<int> unsorted, partialSorted;
unsorted.push_back(11);
unsorted.push_back(2);
unsorted.push_back(2);
unsorted.push_back(99);
unsorted.push_back(2);
unsorted.push_back(4);
unsorted.push_back(5);
unsorted.push_back(7);
unsorted.push_back(34);

    // First copy the iterators into the set
iterator_set itSet;
for( auto it = unsorted.begin(); it!=unsorted.end();++it)
{
    itSet.insert(it);
}
    // now if you want a partial_sort with the first 3 elements, iterate through the
    // set grabbing the first item in the set and then removing it.
int count = 3;
while(count--)
{
    iterator_set::iterator setTop = itSet.begin();
    partialSorted.splice(
        partialSorted.begin(),
        unsorted,
        *setTop);
    itSet.erase(setTop);
}

partialSorted.splice(
        partialSorted.end(),
        unsorted,
        unsorted.begin(),
        unsorted.end());
于 2012-02-10T00:53:14.170 回答
1

有序容器将是std::set或std::map。如果您愿意制作一个带有迭代器的比较器std::set<std::list<mydata>::iterator,comparator>，则可以使用std::map<mydata,std::list<mydata>::iterator>. 您从begin()to遍历列表end()并将迭代器插入集合或映射中；现在您可以使用它通过迭代集合或映射来按排序顺序访问列表中的项目，因为它是自动排序的。

于 2012-02-09T23:57:23.733 回答
1

有序容器是std::set和std::multiset。std::set实现 BST。所以它说的是你应该创建一个std::set<std::list::iterators>然后使用固有的 BST 结构来进行排序。这是BST上的链接，可帮助您入门。

于 2012-02-10T02:22:09.053 回答
0

编辑啊。刚刚注意到“迭代器的有序容器”。这意味着在另一个容器中创建索引。

Boost Multi Index 有很多这样的例子（其中单个集合由几个不同的排序谓词索引，并且索引只不过是基本容器中的“指针”（通常是迭代器）的集合。

“第三种是使用有序的迭代器容器中的信息将列表的元素迭代地拼接到您希望它们所在的位置”

我认为与该描述相匹配的一件事是，在std::sort_heap处理已经std::make_heap//对其进行操作的列表push_heap/向量pop_heap时。

  • make_heap: 将序列转换为堆
  • sort_heap: 对堆进行排序
  • push_heap: 在堆中插入一个元素
  • pop_heap : 从堆中移除顶部元素

堆是序列中元素的组织，这使得在插入/删除下将集合保持在已知顺序中（相对）有效。该顺序是隐式的（就像存储在连续数组中的递归定义的二叉树），并且可以通过对其执行（高效）算法转换为相应的正确排序的序列。sort_heap

于 2012-02-09T23:50:04.447 回答