STL 完全指南：第 2 部分 - List
4.82/5 (32投票s)
STL list 简介。
List 介绍
在本教程的第二部分，我们将介绍 STL list 容器。list 容器实现了双向链表数据结构。与 vector 容器不同，list 占用非连续内存，元素只能通过迭代器访问。
创建 list：构造函数
为了使用 list 容器，我们必须在代码中包含 <list> 头文件，为了指定我们将使用 std 命名空间中的模板类，我们通过声明使用 std 命名空间。
#include <list>
using namespace std;
list 的创建与 vector 类似。在以下示例中，我们将使用构造函数的各种形式来创建 list。我们将学习如何使用拷贝构造函数，以及如何使用 assign() 函数为 list 赋值。
// create an empty list (of zero size) capable of holding doubles
list<double> list0;
cout << "Size of list0 is " << list0.size() << endl;
// create a list with 5 empty elements
list<double> list1(5);
cout << "Size of list1 is " << list1.size() << endl;
// create a list with 5 elements, each element having the value 10.2
list<double> list2(5, 10.2);
cout << "list2: ";
list<double>::iterator it;
for(it = list2.begin(); it != list2.end(); ++it)
cout << *it << " ";
cout << endl;
// create a list based on an array of elements
// only the first 5 elements of the array are copied into the vector
double array[8] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
list<double> list3(array, array + 5);
cout << "list3: ";
for(it = list3.begin(); it != list3.end(); ++it)
cout << *it << " ";
cout << endl;
// use the copy constructor to copy list3 list into list3copy list
list<double> list3copy(list3);
cout << "list3copy: ";
for(it = list3copy.begin(); it != list3copy.end(); ++it)
cout << *it << " ";
cout << endl;
// assign 5 values of 10.2 to the list
list<double> list4;
list4.assign(5, 10.2);
cout << "list4: ";
for(it = list4.begin(); it != list4.end(); ++it)
cout << *it << " ";
cout << endl;
// Output
// Size of list0 is 0
// Size of list1 is 5
// list2: 10.2 10.2 10.2 10.2 10.2
// list3: 3.45 67 10 0.67 8.99
// list3copy: 3.45 67 10 0.67 8.99
// list4: 10.2 10.2 10.2 10.2 10.2
与 vector 类似，begin() 函数返回指向 list 第一个元素的迭代器，end() 函数返回指向 list 最后一个元素之后位置的迭代器。
打印 list 中的元素
与 vector 不同，list 没有重载 [] 操作符，也没有 at() 函数用于元素访问。打印 list 中的元素只能通过迭代器完成。与 vector 类似，我们构建一个名为 print() 的函数，该函数打印 list 中的元素，并接收两个参数：第一个参数是要打印的 list，第二个参数代表 list 的名称。
void print(list<double> lst, char * name)
{
list<double>::iterator it;
cout << name << ": ";
for(it = lst.begin(); it != lst.end(); ++it)
cout << *it << " ";
cout << endl;
}
我们还可以使用反向迭代器以及 rbegin() 和 rend() 函数，以与 vector 相同的方式反向打印 list 中的元素。
double array[8] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
list<double> lst(array, array + 5);
print(lst, "lst");
cout << "lst in reverse order: ";
list<double>::reverse_iterator rit;
for(rit = lst.rbegin(); rit != lst.rend(); ++rit)
cout << *rit << " ";
// Output
// lst: 3.45 67 10 0.67 8.99
// lst in reverse order: 8.99 0.67 10 67 3.45
向 list 中插入元素
除了 push_back() 和 insert() 函数外，list 还有一个用于添加元素的函数：push_front()，它将一个元素（作为参数给出）添加到 list 的开头，紧邻 list 的第一个元素之前。
list<double> lst;
list<double>::iterator it;
// add elements to the end of the list
lst.push_back(2.4);
lst.push_back(4.5);
lst.push_back(0.98);
print(lst, "lst");
// insert value 6.7 in the second position in the list
it = lst.begin();
lst.insert(++it, 6.7);
print(lst, "lst");
// insert elements from the array at the end of the list
double array[2] = {100.89, 789.76};
it = lst.end();
lst.insert(it, array, array + 2);
print(lst, "lst");
// add elements to the beginning of the list
lst.push_front(0.45);
lst.push_front(0.56);
lst.push_front(0.78);
print(lst, "lst");
// Output
// lst: 2.4 4.5 0.98
// lst: 2.4 6.7 4.5 0.98
// lst: 2.4 6.7 4.5 0.98 100.89 789.76
// lst: 0.78 0.56 0.45 2.4 6.7 4.5 0.98 100.89 789.76
从 list 中移除元素
list 上的 pop_back() 和 erase() 函数的使用与我们在 vector 上使用它们的方式完全相同。除此之外，list 还有一个 pop_front() 函数，用于移除 list 的第一个元素。
double array[10] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677, 100.67, 0.99};
list<double> lst(array, array + 10);
list<double>::iterator it;
print(lst, "lst");
// remove the last element of the list
lst.pop_back();
print(lst, "lst");
// remove the second element of the list
it = lst.begin();
lst.erase(++it);
print(lst, "lst");
// remove the first element of the list
lst.pop_front();
print(lst, "lst");
// Output
// lst: 3.45 67 10 0.67 8.99 9.78 6.77 34.677 100.67 0.99
// lst: 3.45 67 10 0.67 8.99 9.78 6.77 34.677 100.67
// lst: 3.45 10 0.67 8.99 9.78 6.77 34.677 100.67
// lst: 10 0.67 8.99 9.78 6.77 34.677 100.67
为了从 list 中移除元素，我们还可以使用 remove() 函数。此函数会移除 list 中所有具有特定值（作为参数给出）的元素。与按位置移除元素的 erase() 函数不同，remove() 函数按值移除元素。在下面的示例中，我们将从 list 中移除所有值为 19.25 的元素。
double array[10] = {3.45, 67, 19.25, 0.67, 8.99, 9.78, 19.25, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
print(lst, "lst");
// remove all elements with value 19.25 from the list
lst.remove(19.25);
print(lst, "lst");
// Output
// lst: 3.45 67 19.25 0.67 8.99 9.78 19.25 34.677 100.67 19.25
// lst: 3.45 67 0.67 8.99 9.78 34.677 100.67
为了有条件地从 list 中移除元素，我们使用 remove_if() 函数。此函数将一个谓词作为参数，并移除 list 中所有谓词返回 true 的元素。谓词通常实现为一个函数，它接受与 list 元素类型相同的参数，并返回一个 bool 值。remove_if() 函数遍历 list 中的所有元素，并为每个元素调用谓词。对于谓词返回 true 的元素，它们将从 list 中移除。
在下面的示例中，我们将移除 list 中所有大于或等于 15 的元素。首先，我们定义谓词，当且仅当元素大于或等于 15 时，谓词才为 true。
bool predicate(double& element)
{
return (element >= 15.0) ? true : false;
}
接下来，我们调用 remove_if() 来有效地移除 list 中满足上述谓词的元素。
double array[10] = {3.45, 67, 19.25, 0.67, 8.99, 9.78, 19.25, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
print(lst, "lst");
// remove all elements greater or equal to 15.0 from the list
lst.remove_if(predicate);
print(lst, "lst");
// Output
// lst: 3.45 67 19.25 0.67 8.99 9.78 19.25 34.677 100.67 19.25
// lst: 3.45 0.67 8.99 9.78
为了移除 list 中的重复元素，我们使用 unique() 成员函数。此函数有两种形式。第一种形式不带参数，它移除 list 中所有与其前驱元素相等的元素。从定义可以看出，list 的第一个元素永远不会被此函数移除，因为它没有前驱元素。
double array[10] = {3.45, 67, 67, 0.67, 8.99, 8.99, 8.99, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
print(lst, "lst");
// remove all duplicate elements from the list
lst.unique();
print(lst, "lst");
// Output
// lst: 3.45 67 67 0.67 8.99 8.99 8.99 34.677 100.67 19.25
// lst: 3.45 67 0.67 8.99 34.677 100.67 19.25
unique() 函数的第二种形式将一个二元谓词作为参数。谓词通常实现为一个函数，它接受两个与 list 元素类型相同的参数，并返回一个 bool 值。谓词指定了 list 中两个连续元素必须满足的条件才能被视为重复项。因此，该函数检查 list 中的所有连续元素对，并移除谓词返回 true 的那些元素。在下面的示例中，我们认为两个元素是重复的，如果它们“近似相等”（它们的绝对差值小于或等于 0.1）。
首先，我们定义一个二元谓词，用于测试两个元素是否“近似相等”。
#include <math.h>
bool almost_equal(double& el1, double& el2)
{
return (fabs(el1 - el2) <= 0.1) ? true : false;
}
接下来，我们调用 unique() 函数，使用上面定义的谓词来移除重复项。
double array[10] = {3.45, 3.455, 67, 0.67, 8.99, 9.0, 9.01, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
print(lst, "lst");
// remove all duplicate elements from the list
lst.unique(almost_equal);
print(lst, "lst");
// Output
// lst: 3.45 3.455 67 0.67 8.99 9 9.01 34.677 100.67 19.25
// lst: 3.45 67 0.67 8.99 34.677 100.67 19.25
对于 list，clear() 和 empty() 成员函数的功能保持不变。
list<double> lst;
lst.push_back(0.67);
lst.push_back(7.89);
lst.push_back(3.56);
if(lst.empty())
cout << "lst is empty" << endl;
else
cout << "lst is not empty" << endl;
// remove all the elements from the list
lst.clear();
if(lst.empty())
cout << "lst is empty" << endl;
else
cout << "lst is not empty" << endl;
// Output
// lst is not empty
// lst is empty
list 的大小和调整大小
与 vector 容器不同，list 没有 capacity() 和 reserve() 函数。用于 list 大小调整和调整大小的其他函数的使用方式与 vector 相同。因此，本节将不深入探讨细节。以下仅展示一个使用这些函数的示例。有关更多详细信息，请参阅vector 容器的文章中的同一部分。
list<double> lst;
lst.push_back(0.67);
lst.push_back(7.89);
lst.push_back(3.56);
lst.push_back(10.67);
lst.push_back(9.89);
cout << "lst size is " << lst.size() << endl;
print(lst, "lst");
// case when new size <= size of list
lst.resize(3);
cout << "lst size is " << lst.size() << endl;
print(lst, "lst");
// case when new size > size of list
lst.resize(10);
cout << "lst size is " << lst.size() << endl;
print(lst, "lst");
// Output
// lst size is 5
// lst: 0.67 7.89 3.56 10.67 9.89
// lst size is 3
// lst: 0.67 7.89 3.56
// lst size is 10
// lst: 0.67 7.89 3.56 0 0 0 0 0 0 0
反转 list
为了反转 list 中元素的顺序，我们使用 reverse() 成员函数。
list<double> lst;
lst.push_back(0.67);
lst.push_back(7.89);
lst.push_back(3.56);
lst.push_back(10.67);
lst.push_back(9.89);
print(lst, "lst");
// reverse the elements of the list
lst.reverse();
print(lst, "lst reversed");
// Output
// lst: 0.67 7.89 3.56 10.67 9.89
// lst reversed: 9.89 10.67 3.56 7.89 0.67
与仅以反向顺序打印 list 元素的反向迭代器不同，reverse() 函数实际上会反转 list 中元素的顺序。
排序 list
为了对 list 中的元素进行排序，我们使用 sort() 函数，该函数使用排序函数来比较 list 中的每一对元素。我们可以将排序函数指定为 sort() 的参数。当未指定排序函数时，sort() 使用 < 操作符来比较元素。
double array[10] = {3.45, 3.455, 67, 0.67, 8.99, 9.0, 9.01, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
print(lst, "lst");
// sort the list;
// < operator will be used as default
// the elements will be sorted in ascending order
lst.sort();
print(lst, "lst in ascending order");
// sort the list; specify the sorting function
// > operator will be used in this case
// the elements will be sorted in descending order
lst.sort( greater<double>() );
print(lst, "lst in descending order");
// sort the list; specify the sorting function
// < operator will be used in this case
// the elements will be sorted in descending order
lst.sort( less<double>() );
print(lst, "lst in ascending order");
// Output
// lst: 3.45 3.455 67 0.67 8.99 9 9.01 34.677 100.67 19.25
// lst in ascending order: 0.67 3.45 3.455 8.99 9 9.01 19.25 34.677 67 100.67
// lst in descending order: 100.67 67 34.677 19.25 9.01 9 8.99 3.455 3.45 0.67
// lst in ascending order: 0.67 3.45 3.455 8.99 9 9.01 19.25 34.677 67 100.67
交换两个 list
使用 swap() 成员函数可以交换两个 list 的内容。
double odds[5] = {1.0, 3.0, 5.0, 7.0, 9.0};
double evens[5] = {2.0, 4.0, 6.0, 8.0, 10.0};
list<double> lst1(odds, odds + 5);
list<double> lst2(evens, evens + 5);
cout << "The lists before swap: " << endl;
print(lst1, "lst1");
print(lst2, "lst2");
// swap the contents of the two lists
lst1.swap(lst2);
cout << "The lists after swap: " << endl;
print(lst1, "lst1");
print(lst2, "lst2");
// Output
// The lists before swap:
// lst1: 1 3 5 7 9
// lst2: 2 4 6 8 10
// The lists after swap:
// lst1: 2 4 6 8 10
// lst2: 1 3 5 7 9
合并两个 list
将一个 list 的元素复制到另一个 list 的一种方法是使用 splice() 成员函数。此函数有三种形式。第一种形式，我们以如下方式调用 splice()：list1.splice(it1, list2)。这将把 list list2 的所有元素复制到 list list1 中，从迭代器 it1 指定的位置开始。操作完成后，list2 将为空。
list<double> list1;
list<double> list2;
list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);
list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);
cout << "Before splice: " << endl;
print(list1, "list1");
print(list2, "list2");
list<double>::iterator it1 = list1.begin();
++it1;
// move all the elements of list2 into list1,
// starting from the second position
list1.splice(it1, list2);
cout << "After splice: " << endl;
print(list1, "list1");
print(list2, "list2");
// Output
// Before splice:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After splice:
// list1: 1 2 3 4 5 6 7 8
// list2:
在第二种形式中，我们以如下方式调用 splice()：list1.splice(it1, list2, it2)。这将把 list list2 中迭代器 it2 指向的元素移动到 list list1 中，移动到迭代器 it1 指定的位置。在这种情况下，只有被移动的元素才会从 list list2 中移除。
list<double> list1;
list<double> list2;
list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);
list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);
cout << "Before splice: " << endl;
print(list1, "list1");
print(list2, "list2");
list<double>::iterator it1 = list1.begin();
++it1;
list<double>::iterator it2 = list2.begin();
// move only the first element of list2 into list1, in the second position
list1.splice(it1, list2, it2);
cout << "After splice: " << endl;
print(list1, "list1");
print(list2, "list2");
// Output
// Before splice:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After splice:
// list1: 1 2 5 6 7 8
// list2: 3 4
调用 splice() 的第三种方式如下：list1.splice(it1, list2, it2begin, it2end)。此版本将 list list2 中的元素范围，从迭代器 it2begin 指定的位置到迭代器 it2end 指定的位置，移动到 list list1 中，移动到迭代器 it1 指定的位置。
list<double> list1;
list<double> list2;
list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);
list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);
cout << "Before splice: " << endl;
print(list1, "list1");
print(list2, "list2");
list<double>::iterator it1;
list<double>::iterator it2begin;
list<double>::iterator it2end;
it1 = list1.end();
it2begin = list2.begin();
it2end = list2.end();
--it2end;
// move from the first to the last element of list2 at the end of list1
// observe that the last element of list2 is not moved
list1.splice(it1, list2, it2begin, it2end);
cout << "After splice: " << endl;
print(list1, "list1");
print(list2, "list2");
// Output
// Before splice:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After splice:
// list1: 1 5 6 7 8 2 3
// list2: 4
用于合并两个 list 的另一个有用函数是 merge()。merge() 函数的调用方式如下：list1.merge(list2)。调用 merge() 的结果是将 list2 中的所有元素插入到 list1 中，并保持它们的有序位置。对于 list2 的每个元素 el2，merge() 找到第一个小于或等于 el2 的元素 el1，并将 el2 插入到 el1 的正后面。这是为了保持 list1 中元素的顺序。请注意，与 splice() 函数不同，为了在两个 list 上使用 merge() 函数，两个 list 都必须是已排序的。如果 list 未排序，我们必须显式地使用 sort() 函数对其进行排序。如果我们尝试在未排序的两个 list 上使用 merge()，应用程序将会崩溃。另外请注意，在调用 merge() 之后，list2 将为空。
list<double> list1;
list<double> list2;
list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);
list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);
cout << "Before merge: " << endl;
print(list1, "list1");
print(list2, "list2");
// merge the two lists
list1.merge(list2);
cout << "After merge: " << endl;
print(list1, "list1");
print(list2, "list2");
// Output
// Before merge:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After merge:
// list1: 1 2 3 4 5 6 7 8
// list2:
二维 list
二维 list 是 list 的 list。
list< list<double> > matrix;
list<double> lst1(5, 6.713);
list<double> lst2(6, 5.678);
matrix.push_back(lst1);
matrix.push_back(lst2);
list< list<double> >::iterator it2d;
for(it2d = matrix.begin(); it2d != matrix.end(); it2d++)
print(*it2d, "row");
// Output
// row: 6.713 6.713 6.713 6.713 6.713
// row: 5.678 5.678 5.678 5.678 5.678 5.678
上面，我们调用了 print() 函数，并将当前迭代器指向的地址的值（这是一个 list）作为第一个参数传递。
用户定义元素的 list
List 也可以存储用户定义的元素。在以下内容中，我们创建了 Person 类，该类具有三个成员：name（类型为 char *）、sex（类型为 char）和 age（类型为 int）。如前所述，拷贝构造函数是必不可少的，并且由于该类使用动态内存分配，因此析构函数也变得必不可少。此外，我们将重载赋值（=）运算符、小于（<）运算符、相等（==）运算符和大于（>）运算符，因为某些函数（如 sort()）将需要它们。sort() 函数基于元素的类型进行比较，因此对于用户定义的元素，这些运算符变得必不可少。
class Person
{
char * name;
char sex;
int age;
public:
// constructor
Person()
{
name = new char[strlen("Anonymous") + 1];
sex = 'N';
age = 0;
}
// constructor
Person(char * pName, char pSex, int pAge)
: sex(pSex), age(pAge)
{
name = new char[strlen(pName) + 1];
strcpy(name, pName);
}
// copy constructor
Person(const Person& rhs)
: sex(rhs.sex), age(rhs.age)
{
name = new char[strlen(rhs.name) + 1];
strcpy(name, rhs.name);
}
// overload the assignment operator
Person& operator=(const Person& rhs)
{
name = new char[strlen(rhs.name) + 1];
strcpy(name, rhs.name);
sex = rhs.sex;
age = rhs.age;
return *this;
}
// overload the == operator
// for sorting purposes, we consider that two Person objects are "equal"
// if they have the same age
bool operator==(const Person& rhs) const
{
return (age == rhs.age) ? true : false;
}
// overload the < operator
// for sorting purposes, we consider that a Person object is "less than" another
// if it's age is less than the other object's age
bool operator<(const Person& rhs) const
{
return (age < rhs.age) ? true : false;
}
// overload the > operator
// for sorting purposes, we consider that a Person object is "greater than" another
// if it's age is greater than the other object's age
bool operator>(const Person& rhs) const
{
return (age > rhs.age) ? true : false;
}
// print the object
void print()
{
cout << name << " " << sex << " " << age << endl;
}
// destructor
~Person()
{
delete []name;
}
};
我们稍微修改了用于打印 list 内容的函数。
void print(list<Person> lst, char * name)
{
list<Person>::iterator it;
cout << name << ":" << endl;
for(it = lst.begin(); it != lst.end(); ++it)
it->print();
cout << endl;
}
接下来，我们创建一个 list 来存储 Person 对象，向其中添加一些元素，打印 list 的内容，移除一些元素，然后按升序和降序对 list 进行排序。
list<Person> lst;
// create some Person objects
Person p1("Bill Gates", 'M', 50);
Person p2("Scott Meyers", 'M', 43);
Person p3("Charles Petzold", 'M', 48);
Person p4("Christina Dermayr", 'F', 30);
Person p5("Andrei Neagu", 'M', 22);
Person p6("Yin Su", 'F', 56);
Person p7("Georgeta Bills", 'F', 37);
// add the objects to the list
lst.push_back(p1);
lst.push_back(p2);
lst.push_back(p3);
lst.push_back(p4);
lst.push_back(p5);
lst.push_front(p6);
lst.push_front(p7);
print(lst, "lst");
// sort the list in ascending order
lst.sort( less<Person>() );
print(lst, "lst in ascending order");
// sort the list in descending order
lst.sort( greater<Person>() );
print(lst, "lst in descending order");
// delete the first element from the list
lst.pop_front();
print(lst, "lst");
// clear the list
lst.clear();
if(lst.empty())
cout << "lst is empty" << endl;
else
cout << "lst is not empty" << endl;
// Output
// lst:
// Georgeta Bills F 37
//Yin Su F 56
// Bill Gates M 50
// Scott Meyers M 43
// Charles Petzold M 48
// Christina Dermayr F 30
// Andrei Neagu M 22
//
// lst in ascending order:
// Andrei Neagu M 22
// Christina Dermayr F 30
// Georgeta Bills F 37
// Scott Meyers M 43
// Charles Petzold M 48
// Bill Gates M 50
// Yin Su F 56
//
// lst in descending order:
// Yin Su F 56
// Bill Gates M 50
// Charles Petzold M 48
// Scott Meyers M 43
// Georgeta Bills F 37
// Christina Dermayr F 30
// Andrei Neagu M 22
//
// lst:
// Bill Gates M 50
// Charles Petzold M 48
// Scott Meyers M 43
// Georgeta Bills F 37
// Christina Dermayr F 30
// Andrei Neagu M 22
//
// lst is empty
复杂性
其实现方式表明，list 容器主要用于存储大型对象，进行大量插入和删除操作，特别是在 list 内部，因为这些操作只需要更新一些链接而无需移动内存中的对象。甚至 sort() 和 reverse() 成员函数也是通过指针操作，而不是直接操作存储的对象。建议使用它们而不是它们的通用替代品。list 使用非连续内存的事实得出结论，一旦迭代器加载了容器元素的地址，它就不会失效，除非它指向的节点被删除。
遍历 list 中的元素比 vector 慢得多，因为它涉及到指针移动，而不是地址计算。list 容器还占用额外的内存来管理前驱和后继链接。