首页 > 编程笔记

C++ list(STL list)排序及合并元素方法详解

sort() 函数模板定义在头文件 algorithm 中，要求使用随机访问迭代器。但 list 容器并不提供随机访问迭代器，只提供双向迭代器，因此不能对 list 中的元素使用 sort() 算法。但是，还是可以进行元素排序，因为 list 模板定义了自己的 sort() 函数。sort() 有两个版本：无参 sort() 函数将所有元素升序排列。第二个版本的 sort() 接受一个函数对象或 lambda 表达式作为参数，这两种参数都定义一个断言用来比较两个元素。

下面是一个以断言作为参数调用 list 成员函数 sort() 的示例：

names.sort(std::greater<std::string>()); // Names in descending sequence

这里使用了定义在头文件 functional 中的模板 greater<T>。这个模板定义了一个用来比较 T 类型对象的函数对象。如果第一个参数大于第二个参数，那么成员函数 operator()() 返回 true。头文件 functional 中定义了一些定义了断言的模板，在后面，我们会看到更多的断言。排序执行完毕后，list 中的元素如下：
"Jules" "Jim" "Janet" "Jane" "Hugo" "Hannah" "Ann" "Alan"

因此，现在 names 中的元素是降序排列的。有一个简洁版的 greater<T> 断言，可以如下所示使用：

names.sort(std::greater<>()); // Function object uses perfect forwarding

简洁版的函数对象可以接受任何类型的参数，使用完美转发 (perfect forwarding) 可以避免不必要的参数拷贝。因此，完美转发总是会快很多，因为被比较的参数会被移动而不是复制到函数中。

当然，在必要时可以将自定义的函数对象传给断言来对 list 排序。尽管对一般对象来说，并不需要这样。如果为自己的类定义了 operator()()，然后就可以继续使用 std::greater<>。当我们需要比较非默认类型时，就需要一个函数对象。

例如，假设我们想对 names 中的元素进行排序，但是不想使用字符串对象标准的 std::greater<> 来比较，而是想将相同初始字符的字符串按长度排序。可以如下所示定义一个类：

// Order strings by length when the initial letters are the same
class my_greater
{
    public:
    bool operator () (const std::strings s1, const std::strings s2)
    {
        if (s1[0] == s2 [0])
            return si.length() > s2.length();
        else
            return s1 > s2;
    }
};

可以用这个来对 names 中的元素排序：

names.sort(my_greater()); // Sort using my_greater

代码执行完毕后，list 中包含的元素如下：
"Jules" "Janet" "Jane” "Jim" "Hannah" "Hugo" "Alan" "Ann"

这个结果和前面使用字符串对象标准比较方式的结果明显不同。names 中初始字符相同的元素按长度降序排列。当然，如果不需要重用 my_greater() 断言，这里也可以使用 lambda 表达式。

下面是一个用 lambda 表达式实现的示例：

names.sort([](const std::strings s1, const std::strings s2)
{
    if (s1[0] == s2[0])
        return s1.length() > s2.length();
    else
        return s1 > s2;
});

这和前面代码的作用相同。

list 的成员函数 merge() 以另一个具有相同类型元素的 list 容器作为参数。两个容器中的元素都必须是升序。参数 list 容器中的元素会被合并到当前的 list 容器中。例如：

std::list<int> my_values {2, 4, 6, 14};
std::list<int> your_values{ -2, 1, 7, 10};
my_values.merge (your_values);//my_values contains: -2 1 2 4 6 7 10 14
your_values.empty(); // Returns true

元素从 your_values 转移到 my_values，因此，在执行完这个操作后，your_values 中就没有元素了。改变每个 list 节点的指针，在适当的位置将它们和当前容器的元素链接起来，这样就实现了元素的转移。list 节点在内存中的位置不会改变；只有链接它们的指针变了。在合并的过程中，两个容器中的元素使用 operator()() 进行比较。

在另一个版本的 merge() 函数中，可以提供一个比较函数作为该函数的第二个参数，用来在合并过程中比较元素。例如：

std::list<std::string> my_words { "three","six", "eight"};
std::list<std::string> your_words { "seven", "four", "nine"};
auto comp_str = [](const std::strings s1, const std::strings s2){ return s1[0]<s2[0];};
my_words.sort (comp_str); //"eight" "six" "three"
your_words.sort (comp_str) ;  //"four" "nine" "seven"
my_words.merge (your_words, comp_str) ; // "eight" "four" "nine" "six" "seven" "three"

这里的字符串对象比较函数是由 lambda 表达式定义的，这个表达式只比较第一个字符。比较的效果是，在合并的 list 容器中，"six”在”seven”之前。在上面的代码中，也可以无参调用 merge()，这样"seven"会在"six"之前，这是一般的排序。

list 容器的成员函数 splice() 有几个重载版本。这个函数将参数 list 容器中的元素移动到当前容器中指定位置的前面。可以移动单个元素、一段元素或源容器的全部元素。下面是一个剪切单个元素的示例：

std::list<std::string> my_words {"three", "six", "eight"};
std::list<std::string> your_words {"seven", "four", "nine"};
my_words.splice(++std::begin(my_words), your_words, ++std::begin(your_words));

splice() 的第一个参数是指向目的容器的迭代器。第二个参数是元素的来源。第三个参数是一个指向源list容器中被粘接元素的迭代器，它会被插入到第一个参数所指向位置之前。代码执行完中后，容器中的内容如下：

your_words: "seven", "nine"
my_words : "three", "four", "six", "eight"

当要粘接源 list 容器中的一段元素时，第 3 和第 4 个参数可以定义这段元素的范围。例如：

your_words.splice(++std::begin(your_words),my_words,++std::begin(my_words), std::end(my_words));

上面的代码会将 my_words 从第二个元素直到末尾的元素，粘接到 your_words 的第二个元素之前。上面两个 list 容器的内容如下：

your_words:"seven", "four", "six", "eight","nine" my_words: "three"

下面的语句可以将 your_words 的全部元素粘接到 my_words 中：

my_words.splice(std::begin(my_words), your_words);

your_words 的所有元素被移到了 my_words 的第一个元素"three”之前。然后，your_words 会变为空。即使 your_words 为空，也仍然可以向它粘接元素：

your_words.splice(std::end(your_words), my_words);

现在，my_words 变为空，your_words 拥有全部元素。第一个参数也可以是 std::begin (your_words)，因为当容器为空时，它也会返回一个结束迭代器。

C++ list(STL list)排序及合并元素方法详解

推荐阅读