C++数据结构之list详解

什么是list？

list是C++ STL库中的一个数据结构，它能够以O(1)的复杂度在任何位置进行插入或删除操作，当然它也支持随机访问指定位置的元素。list属于双向链表，它内部结构为指针连接不同的节点。

如何使用list？

包含头文件

在C++中使用list，需要包含头文件#include <list>。

定义list变量

定义一个list变量的语法是list<数据类型> 变量名。例如，我们定义了一个存储整数类型的list变量：

list<int> myList;

在list中插入元素

在list中插入元素的语法是list名.push_back(元素)或list名.push_front(元素)。其中，push_back在list末尾插入元素，push_front在list头部插入元素。

例如：

list<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_front(0);

最终myList中的元素为0，1，2。

访问list中的元素

对于list，不能像数组一样用下标访问元素。我们可以使用迭代器访问list中的元素。迭代器是一种用于遍历容器内元素的机制，类似指针。list有两种迭代器：begin和end，其中begin表示list的第一个元素，end表示list尾部的下一个位置。

我们可以用一个for循环遍历list中的元素：

list<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);

list<int>::iterator itr;
for (itr = myList.begin(); itr != myList.end(); itr++) {
  cout << *itr << " ";
}

输出会是：1 2 3。

在list中删除元素

在list中删除元素的语法是list名.remove(元素)。例如：

list<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
myList.remove(2);

最终myList中的元素为1，3。

list示例

下面我们通过两个示例来演示list的使用。

示例1：排序list

我们创建一个list变量并将一些随机数插入其中，然后对它进行排序。最后，我们使用迭代器遍历list并打印排序后的结果。

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {
  list<int> myList;
  myList.push_back(42);
  myList.push_back(23);
  myList.push_back(67);
  myList.push_back(11);
  myList.push_back(8);

  myList.sort();

  cout << "排序后的list：\n";
  copy(myList.begin(), myList.end(), ostream_iterator<int>(cout, " "));

  cout << endl;

  return 0;
}

打印结果为：排序后的list：8 11 23 42 67。

示例2：重载运算符操作list

我们创建一个放置字符串的list，然后编写一个函数，该函数可以输出list中所有字符串的大写版本。

#include <iostream>
#include <list>
#include <cctype>

using namespace std;

void toUpper(string& s) {
  for (int i = 0; i < s.size(); i++) {
    s[i] = toupper(s[i]);
  }
}

int main() {
  list<string> myList;

  myList.push_back("apple");
  myList.push_back("banana");
  myList.push_back("grape");
  myList.push_back("orange");
  myList.push_back("peach");

  for (auto& s : myList) {
    toUpper(s);
    cout << s << endl;
  }

  return 0;
}

输出结果为：

APPLE
BANANA
GRAPE
ORANGE
PEACH

结语

本文介绍了list的基本使用方法，包括定义、插入、访问、删除，同时也演示了两个list的示例，其中一个是排序list，另一个是重载运算符操作list。