std::sort() 算法排序 std::vector of std::list 的效率

Question

下面的例子取自Jossuttis(2012)，有一些小改动。

本质上，它是对整数列表的向量进行排序。

我的问题如下：

std::sort() 算法是否对指针（指向列表）进行排序？
如果答案是否定的，仍然使用 std::sort() 对指向容器的（智能）指针向量进行排序的最佳方法是什么？

#include <vector>
#include <list>
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;

template<typename T>

inline void INSERT_ELEMENT(T& coll, int first, int last){
    for(int i=first; i<=last; ++i)
        coll.insert(coll.end(), i);
}

template<typename T>

inline void PRINT_ELEMENTS(const T& coll, const std::string& optcstr=""){
    std::cout << optcstr;
    for(auto elem:coll)
        std::cout << elem << " ";
    std::cout << std::endl;
}

int main(){

    list<int> c1, c2, c3, c4;
    INSERT_ELEMENT(c1, 1, 5);
    c2 = c3 = c4 = c1;

    c1.push_back(7);
    c3.push_back(2);
    c3.push_back(0);
    c4.push_back(2);

    vector<list<int>> cc{ c1, c2, c3, c4, c3, c1, c4, c2};

    for(auto elem: cc){
        PRINT_ELEMENTS(elem);
    }
    cout << endl;

    sort(
        cc.begin(), 
        cc.end(), 
        [](const list<int>& first, const list<int>& second){
            return lexicographical_compare(
                first.cbegin(), 
                first.cend(),
                second.cbegin(),
                second.cend()
            );
        }
    );
    for(auto elem: cc){
        PRINT_ELEMENTS(elem);
    }
}

Answer 1

std::sort() 算法是否对指针（指向列表）进行排序？

不，c++11 和 c++03 都没有。区别在于自 c++11 起，移动语义用于排序。

我想你实际上问的是关于 move 语义的。对于std::list，它们是可移动的，而在std::sort的实现中，元素交换是基于c++11中的移动。所以从 c++11 开始，std::vector<std::list<T>> 的类型很便宜。如果你有 pre c++11，那么我们可以考虑使用指针使交换（基于副本）便宜：std::vector<std::list<T>*> 使排序更快，建议升级旧编译器以获得性能提升.

你可以通过更改你的代码打印元素地址来验证它，它们在排序后没有改变，然后我们确认列表被移动但没有被复制，你的原始代码在循环范围内有不必要的复制，我已修复：

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>
using namespace std;

template <typename T>

inline void INSERT_ELEMENT(T& coll, int first, int last) {
  for (int i = first; i <= last; ++i) coll.insert(coll.end(), i);
}

template <typename T>

inline void PRINT_ELEMENTS(const T& coll, const std::string& optcstr = "") {
  std::cout << optcstr;
  for (auto& elem : coll) std::cout << &elem << " ";
  std::cout << std::endl;
}

int main() {
  list<int> c1, c2, c3, c4;
  INSERT_ELEMENT(c1, 1, 5);
  c2 = c3 = c4 = c1;

  c1.push_back(7);
  c3.push_back(2);
  c3.push_back(0);
  c4.push_back(2);

  vector<list<int>> cc{c1, c2, c3, c4, c3, c1, c4, c2};

  for (auto& elem : cc) {
    PRINT_ELEMENTS(elem);
  }
  cout << endl;

  sort(cc.begin(), cc.end(),
       [](const list<int>& first, const list<int>& second) {
         return lexicographical_compare(first.cbegin(), first.cend(),
                                        second.cbegin(), second.cend());
       });
  for (auto& elem : cc) {
    PRINT_ELEMENTS(elem);
  }
}

Online demo

std::sort() 算法排序 std::vector of std::list 的效率

Efficiency of std::sort() algorithm in sorting std::vector of std::list

c++

sorting

stl

smart-pointers