学会吊打面试官之list
小白：大牛，我想请教一下关于C++ STL中的容器，list是什么，它的用法和特点是什么？
大牛：小白，很高兴听到你对容器感兴趣。list是STL中的双向链表容器，它有以下几个特点：
-
支持高效的插入和删除操作。由于list是双向链表，因此在任意位置插入或删除元素时只需要修改相邻节点的指针，时间复杂度为O(1)。
-
不支持随机访问。由于list不是连续存储的，因此无法通过下标来访问元素，只能通过遍历链表来访问。
-
支持高效的拷贝和移动操作。由于list的元素是独立存储的，因此可以通过拷贝或移动指针来高效地实现整个list的拷贝或移动。
下面我们来看一个实际的案例，假设我们需要实现一个简单的学生成绩管理程序，我们可以使用list容器来保存学生的成绩。
#include <iostream>
#include <list>
#include <string>struct Student {std::string name;int score;
};int main() {std::list<Student> students;students.push_back({"Tom", 80});students.push_back({"Alice", 90});students.push_back({"Bob", 85});for (auto& student : students) {std::cout << student.name << " scored " << student.score << std::endl;}return 0;
}
在上面的代码中，我们定义了一个名为Student的结构体，包含学生的姓名和成绩。我们创建了一个list容器来保存学生的信息，并使用push_back函数向其中添加了三个学生的信息。最后，我们通过for循环遍历整个list并输出每个学生的姓名和成绩。
小白：哇，list好神奇啊，谢谢大牛的讲解和案例。
大牛：我们再进一步结合一个实际的案例来详细解释list容器的使用。假设我们需要编写一个程序，实现字符串的逆序输出。我们可以使用list容器来实现这个功能。
#include <iostream>
#include <list>
#include <string>int main() {std::string str = "hello world";std::list<char> charList(str.begin(), str.end());charList.reverse();for (auto& c : charList) {std::cout << c;}std::cout << std::endl;return 0;
}
大牛：在上面的代码中，我们首先定义了一个名为str的字符串，将其转换为一个list容器charList。通过使用容器的构造函数，我们可以将一个序列（在这里是字符串）的元素添加到list容器中。
接下来，我们使用reverse函数将list容器中的元素逆序排列。最后，我们通过遍历charList容器并输出其中的元素，将逆序后的字符串输出到控制台中。
通过这个例子，我们可以看到list容器在实现字符串逆序输出时的便利性。同时，它也展示了list容器的高效性和灵活性。
小白：有什么具体案例解释一下嘛，我感觉还是没有很好理解qvq.
大牛：除了逆序输出字符串外，list容器在实际开发中还有很多应用。比如，我们可以使用list容器来实现一个简单的文本编辑器。
下面是一个简单的示例，它可以通过list容器来实现向一个文本文件中添加、删除、插入文本的功能。
#include <iostream>
#include <fstream>
#include <list>
#include <string>void read_file(std::list<char>& charList, const std::string& filename) {std::ifstream input_file(filename);if (!input_file.is_open()) {std::cerr << "Failed to open file: " << filename << std::endl;return;}char c;while (input_file.get(c)) {charList.push_back(c);}
}void write_file(const std::list<char>& charList, const std::string& filename) {std::ofstream output_file(filename);if (!output_file.is_open()) {std::cerr << "Failed to open file: " << filename << std::endl;return;}for (auto& c : charList) {output_file.put(c);}
}int main() {std::string filename = "test.txt";std::list<char> charList;read_file(charList, filename);charList.push_back('\\n');charList.push_back('a');charList.push_back('b');charList.push_back('c');charList.push_back('\\n');charList.insert(charList.begin(), 'x');charList.erase(charList.begin() + 5);write_file(charList, filename);return 0;
}
在上面的代码中，我们定义了一个名为charList的list容器，用来存储文本文件中的字符。我们通过read_file函数从文件中读取文本数据并将其存储到charList容器中。然后，我们使用push_back、insert、erase等list容器的成员函数，向charList容器中添加、删除、插入字符。
最后，我们通过write_file函数将修改后的文本数据写入到文件中。
这个例子中展示了list容器在实现文本编辑器时的便利性。使用list容器，我们可以高效地实现文本的插入、删除和修改。同时，list容器还能够很好地处理大量数据的读写操作，因为它的内部实现是通过双向链表来实现的，所以在插入和删除操作时，它的效率比较高。
小白：原来是这样，那它的底层实现是怎样的呢？
大牛：list容器的底层实现是一个双向链表，每个节点存储了一个元素和指向前一个节点和后一个节点的指针。因此，在插入和删除操作时，list容器比较高效。
具体地说，在插入元素时，list容器会创建一个新节点，并将其指针链接到前一个节点和后一个节点上，同时更新前一个节点和后一个节点的指针，将其指向新节点。这样，插入操作就完成了。
在删除元素时，list容器会找到要删除的节点，更新前一个节点的指针，将其指向下一个节点，同时更新下一个节点的指针，将其指向前一个节点，然后释放要删除的节点。这样，删除操作就完成了。
由于list容器的底层实现是双向链表，因此它的迭代器也是双向迭代器，可以进行前向和后向迭代。在实际应用中，list容器经常用于需要频繁插入、删除元素的场景，比如文本编辑器、图形界面等。
需要注意的是，由于list容器的元素存储在堆上，因此访问元素时需要通过指针进行间接访问，这可能会带来一定的性能开销。同时，由于list容器不支持随机访问，因此无法像数组一样使用下标来访问元素。因此，在使用list容器时，需要根据具体情况选择合适的容器类型。