C++奇迹之旅：双向链表容器list的灵活使用技巧

学习起来吧

发布于 2024-08-29 00:30:39

11800

代码可运行

文章被收录于专栏：学习C/++学习C/++

运行总次数：0

代码可运行

📝list简介

list直击查看：https://legacy.cplusplus.com/reference/list/list/?kw=list

std::list 是 C++ 标准库中的一个序列容器，它实现了双向链表（doubly linked list）。

列表是序列容器，允许在序列中的任何位置进行常数时间的插入和删除操作，并且支持双向遍历。
列表容器实现为双向链表；双向链表可以将它们包含的每个元素存储在不同且无关的存储位置。元素的顺序通过每个元素与前一个元素和下一个元素之间的链接来保持。
list与 forward_list 非常相似：主要区别在于 forward_list 对象是单向链表，因此只能向前遍历，而以此换取更小的内存占用和更高的效率。
与其他基本标准序列容器（如数组、向量和双端队列）相比，列表在容器中任何位置插入、提取和移动元素的性能通常更好，因此也更适合需要频繁执行这些操作的算法，如排序算法。
与这些其他序列容器相比，list和 forward_list 的主要缺点是缺乏按位置直接访问元素的能力；例如，要访问列表中的第六个元素，必须从已知位置（如开头或末尾）开始遍历到该位置，这需要线性时间。此外，它们还会消耗一些额外的内存来存储与每个元素相关的链接信息（这对于包含大量小型元素的大型list可能是一个重要因素）。

因此，我们又叫它双向循环列表。

🌠 构造函数

当然！以下是对 std::list 四种构造函数的详细示例：

默认构造函数（创建了一个空的 std::list<int> 对象）

    // 使用默认构造函数创建一个空的 std::list
    std::list<int> myList;

填充构造函数（构造n个相同元素一样的初始值）

    // 使用填充构造函数创建一个包含 5 个元素，每个元素初始化为 10 的 std::list
    std::list<int> myList(5, 10);

范围构造函数（迭代区间构造）

    // 使用 std::vector 创建一个范围
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用范围构造函数创建一个 std::list，包含 vector 中的元素
    std::list<int> myList(vec.begin(), vec.end());

拷贝构造函数

    // 创建一个初始的 std::list
    std::list<int> originalList = {1, 2, 3, 4, 5};

    // 使用复制构造函数创建一个新的 std::list
    std::list<int> copiedList(originalList);

explicit 关键字在 C++ 中用于控制构造函数的隐式转换行为。它防止了构造函数在不经意间被用于类型转换，从而避免可能导致意外错误或不明确的转换。具体来说，explicit 关键字主要用于防止以下两种情况：

隐式类型转换：构造函数可以被用于隐式地将一种类型的对象转换为另一个类型。例如，当构造函数可以接受一个参数并用它来初始化对象时，如果这个构造函数是 explicit 的，只有当构造函数显式地被调用时，它才会被用作转换。如果构造函数没有 explicit，则编译器可以在需要时自动执行隐式转换。
避免误用：如果构造函数不是 explicit，那么它可以在赋值或函数参数传递时被自动调用，可能会导致意外的类型转换或逻辑错误。使用 explicit 关键字可以确保构造函数只在你显式地请求时被调用，从而避免这些潜在问题。
默认构造函数

explicit list (const allocator_type& alloc = allocator_type());

解释：这个构造函数接受一个分配器 alloc 作为参数。如果没有 explicit，C++ 编译器可能会在需要 std::list 对象的地方用单一的分配器对象隐式地创建 std::list。比如，在某些模板类中，编译器可能会自动用分配器创建 std::list。添加 explicit 关键字防止了这种隐式转换，确保只有当明确调用构造函数时才会使用该构造函数。

填充构造函数

explicit list (size_type n, const value_type& val = value_type(),
                const allocator_type& alloc = allocator_type());

解释：这个构造函数用于创建一个包含 n 个初始化为 val 的元素的 std::list。如果没有 explicit，编译器可能会用单一的 size_type 和 value_type 参数隐式地创建一个 std::list。添加 explicit 关键字防止了这种隐式类型转换，确保只有当显式调用构造函数时才会创建 std::list。

🌉迭代器Iterator

迭代器使用和vector，string使用基本一样，以下是遍历list：

#include <iostream>
#include <list>

int main() {
    // 创建一个包含一些整数的 std::list
    std::list<int> myList = { 10, 20, 30, 40, 50 };

    // 1. 使用正向迭代器遍历列表并修改元素
    std::cout << "Forward iteration (modifiable): ";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        *it *= 2;  // 将每个元素乘以 2
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 2. 使用反向迭代器遍历列表
    std::cout << "Reverse iteration (modifiable): ";
    for (auto rit = myList.rbegin(); rit != myList.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    // 3. 使用常量迭代器遍历列表（只读）
    std::cout << "Constant forward iteration (read-only): ";
    for (auto cit = myList.cbegin(); cit != myList.cend(); ++cit) {
        std::cout << *cit << " ";
    }
    std::cout << std::endl;

    // 4. 使用常量反向迭代器遍历列表（只读）
    std::cout << "Constant reverse iteration (read-only): ";
    for (auto crit = myList.crbegin(); crit != myList.crend(); ++crit) {
        std::cout << *crit << " ";
    }
    std::cout << std::endl;

    return 0;
}

🌠容量操作

在 C++ 标准库中，std::list 提供了一些用于查询容器容量和大小的公共成员函数。这些函数帮助你了解 std::list 的当前状态和限制。以下是对这些函数的详细解释及示例：

empty检查 std::list 是否为空。如果列表中没有任何元素，它返回 true；否则，返回 false。

bool empty() const;

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList;

    // 检查列表是否为空
    if (myList.empty()) {
        std::cout << "The list is empty." << std::endl;
    } else {
        std::cout << "The list is not empty." << std::endl;
    }

    // 添加元素后再次检查
    myList.push_back(10);
    if (myList.empty()) {
        std::cout << "The list is empty." << std::endl;
    } else {
        std::cout << "The list is not empty." << std::endl;
    }

    return 0;
}

size返回 std::list 中元素的数量。返回值是 size_type

size_type size() const;

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};

    // 获取并输出列表的大小
    std::cout << "The size of the list is: " << myList.size() << std::endl;

    return 0;
}

max_size返回容器可以容纳的最大元素数量，这个值是系统和实现决定的。

size_type max_size() const;

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList;

    // 获取并输出列表可以容纳的最大元素数量
    std::cout << "The maximum size of the list is: " << myList.max_size() << std::endl;

    return 0;
}

🌉元素访问

front

reference front();//返回一个对列表中第一个元素的引用，可以用来修改该元素。
const_reference front() const;

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30, 40, 50};

    // 访问并修改第一个元素
    myList.front() = 15;

    // 输出第一个元素
    std::cout << "The first element is: " << myList.front() << std::endl;

    // 使用 const_reference 查看第一个元素（只读）
    const std::list<int>& constList = myList;
    std::cout << "The first element (const) is: " << constList.front() << std::endl;

    return 0;
}

back

reference back();//返回一个对列表中最后一个元素的引用，可以用来修改该元素。
const_reference back() const;

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30, 40, 50};

    // 访问并修改最后一个元素
    myList.back() = 45;

    // 输出最后一个元素
    std::cout << "The last element is: " << myList.back() << std::endl;

    // 使用 const_reference 查看最后一个元素（只读）
    const std::list<int>& constList = myList;
    std::cout << "The last element (const) is: " << constList.back() << std::endl;

    return 0;
}

🌠内容操作

push_back

void push_back(const value_type& value);//在列表的末尾插入一个新元素，`value` 是插入的值。

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3};

    // 在末尾添加一个元素 4
    myList.push_back(4);

    std::cout << "List after push_back(4): ";
    for (const auto& elem : myList) std::cout << elem << " ";
    std::cout << std::endl;

    return 0;
}

pop_back

void pop_back();//删除列表中的最后一个元素。此操作将缩小列表的大小。

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};

    // 删除最后一个元素
    myList.pop_back();

    std::cout << "List after pop_back(): ";
    for (const auto& elem : myList) std::cout << elem << " ";
    std::cout << std::endl;

    return 0;
}

insert

iterator insert(const_iterator position, const value_type& value);
iterator insert(const_iterator position, value_type&& value);
iterator insert(const_iterator position, size_type count, const value_type& value);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);

解释：

insert(const_iterator position, const value_type& value)：在指定位置插入一个元素，value 是插入的值。
insert(const_iterator position, value_type&& value)：在指定位置插入一个元素，value 是右值引用。
insert(const_iterator position, size_type count, const value_type& value)：在指定位置插入指定数量的相同元素。
insert(const_iterator position, InputIterator first, InputIterator last)：在指定位置插入一个范围的元素。

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 5};

    // 在位置 2 插入元素 3
    auto it = myList.begin();
    std::advance(it, 2);
    myList.insert(it, 3);

    // 在位置 1 插入两个元素 10
    it = myList.begin();
    myList.insert(++it, 2, 10);

    // 在末尾插入范围
    std::list<int> otherList = {20, 30};
    myList.insert(myList.end(), otherList.begin(), otherList.end());

    std::cout << "List after multiple inserts: ";
    for (const auto& elem : myList) std::cout << elem << " ";
    std::cout << std::endl;

    return 0;
}

erase

iterator erase(const_iterator position);//删除指定位置的元素。
iterator erase(const_iterator first, const_iterator last);//删除指定范围内的元素。

示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};

    // 删除位置 2 的元素
    auto it = myList.begin();
    std::advance(it, 2);
    myList.erase(it);

    // 删除从位置 1 到位置 3 的元素
    it = myList.begin();
    auto itEnd = it;
    std::advance(it, 1);
    std::advance(itEnd, 3);
    myList.erase(it, itEnd);

    std::cout << "List after erase(): ";
    for (const auto& elem : myList) std::cout << elem << " ";
    std::cout << std::endl;

    return 0;
}

这里要注意的是迭代器Insert和erase失效问题：

在 C++ 中，当你对一个 list 进行元素的插入或删除操作时，通常迭代器的失效问题需要特别注意。

在 std::list 中：

插入操作：在 list 中插入元素不会导致其他迭代器失效。也就是说，插入新元素后，已有的迭代器仍然有效。
删除操作：当你删除某个元素时，与该元素关联的迭代器会失效，而其他的迭代器不会受到影响。

第一个代码中：

void TestListIterator1()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    std::list<int> mylist(array, array + sizeof(array) / sizeof(array[0]));
    auto it = mylist.begin();
    while (it != mylist.end())
    {
        mylist.erase(it);
        ++it;
    }
}

这里的问题是，当 mylist.erase(it) 删除当前迭代器 it 指向的元素时，it 本身就已经失效。接着进行 ++it 操作时会引发未定义行为，因为 it 已经指向了一个无效的位置。

修改后的代码：你可以通过在删除元素时同时移动迭代器来避免这个问题，如下所示：

void TestListIterator()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> mylist(array, array + sizeof(array) / sizeof(array[0]));
	auto it = mylist.begin();
	while (it != mylist.end())
	{
		it = mylist.erase(it); // 通过将it指向erase的返回值来处理
	}
}

在这段代码中，mylist.erase(it) 会返回指向被删除元素后一个元素的迭代器，这样就能确保 it 在循环中始终是有效的。

🌉功能选择

splice (拼接) splice用于将元素从一个std::list转移到另一个std::list中。

成员函数： void splice(iterator pos, list& other); 说明： 将other列表中的所有元素转移到当前列表pos位置。
成员函数： void splice(iterator pos, list& other, iterator it); 说明： 将other列表中由it指向的元素转移到当前列表pos位置。
成员函数： void splice(iterator pos, list& other, iterator first, iterator last); 说明： 将other列表中从first到last（不包括last）之间的元素转移到当前列表pos位置。

示例：

#include <iostream>
#include <list>

void test_splice() {
    std::list<int> list1 = {1, 2, 3};
    std::list<int> list2 = {4, 5, 6};
    
    list1.splice(list1.end(), list2); // 将list2的所有元素移动到list1的末尾
    // list1: {1, 2, 3, 4, 5, 6}
    // list2: {}

    list1.splice(list1.begin(), list1, ++list1.begin()); // 将第二个元素移动到开头
    // list1: {2, 1, 3, 4, 5, 6}
}

remove (移除) remove函数用于从列表中移除所有指定值的元素。

成员函数： void remove(const T& value); 说明： 移除列表中所有等于指定值的元素。

示例：

#include <iostream>
#include <list>

void test_remove() {
    std::list<int> mylist = {1, 2, 3, 2, 4, 2};
    mylist.remove(2); // 移除所有值为2的元素
    // mylist: {1, 3, 4}
}

remove_if (条件移除) remove_if函数用于移除满足特定条件的元素。

成员函数模板： template<class Predicate> void remove_if(Predicate pred); 说明： 移除列表中所有满足条件的元素，该条件由谓词函数pred定义。

示例：

#include <iostream>
#include <list>

void test_remove_if() {
    std::list<int> mylist = {1, 2, 3, 4, 5, 6};
    mylist.remove_if([](int x) { return x % 2 == 0; }); // 移除所有偶数
    // mylist: {1, 3, 5}
}

unique (去重) unique函数用于移除列表中连续的重复元素。

成员函数： void unique(); 说明： 移除列表中连续的重复元素。
成员函数模板： template<class BinaryPredicate> void unique(BinaryPredicate p); 说明： 根据二元谓词p移除列表中的重复元素。

示例：

#include <iostream>
#include <list>

void test_unique() {
    std::list<int> mylist = {1, 1, 2, 3, 3, 4};
    mylist.unique(); // 移除连续的重复元素
    // mylist: {1, 2, 3, 4}
}

merge (合并) merge函数用于将两个已排序的列表合并成一个，同时保持排序顺序。

成员函数： void merge(list& other); 说明： 将other列表合并到当前列表中，前提是两个列表都已排序。
成员函数模板： template<class Compare> void merge(list& other, Compare comp); 说明： 使用自定义比较函数comp将other列表合并到当前列表中。

示例：

#include <iostream>
#include <list>

void test_merge() {
    std::list<int> list1 = {1, 3, 5};
    std::list<int> list2 = {2, 4, 6};
    
    list1.merge(list2); // 将list2合并到list1
    // list1: {1, 2, 3, 4, 5, 6}
    // list2: {}
}

sort (排序) sort函数用于对列表中的元素进行排序。

成员函数： void sort(); 说明： 将列表中的元素按升序排序。
成员函数模板： template<class Compare> void sort(Compare comp); 说明： 使用自定义比较函数comp对列表中的元素进行排序。

示例：

#include <iostream>
#include <list>

void test_sort() {
    std::list<int> mylist = {4, 1, 3, 2, 5};
    mylist.sort(); // 按升序排序
    // mylist: {1, 2, 3, 4, 5}
}

reverse (反转) reverse函数用于将列表中的元素顺序反转。

成员函数： void reverse(); 说明： 将列表中的元素顺序反转。

示例：

#include <iostream>
#include <list>

void test_reverse() {
    std::list<int> mylist = {1, 2, 3, 4, 5};
    mylist.reverse(); // 反转元素顺序
    // mylist: {5, 4, 3, 2, 1}
}

总结

splice：用于在列表之间移动元素。
remove：移除指定值的元素。
remove_if：移除满足条件的元素。
unique：移除连续的重复元素。
merge：合并两个已排序的列表。
sort：对列表中的元素进行排序。
reverse：反转列表中的元素顺序。

这些操作为处理和管理std::list中的元素提供了强大的工具，非常适合在实际开发中使用。

🚩总结

std::list是C++标准库中的双向链表容器,具有常数时间内插入和删除元素的优势。
std::list提供了四种构造函数:默认构造、填充构造、范围构造和拷贝构造,其中部分构造函数使用了explicit关键字来防止意外的类型转换。
std::list的迭代器使用和std::vector、std::string基本一致,可以进行正向、反向、只读遍历。
std::list提供了丰富的成员函数,如empty、size、max_size用于查询容器状态,front、back用于访问首尾元素,以及push_back、pop_back、insert、erase等用于元素的增删操作。
std::list的splice、remove、remove_if、unique、merge、sort、reverse等成员函数提供了强大的容器管理功能,可以灵活地处理和操作列表中的元素。
在对std::list进行插入和删除操作时,需要注意迭代器可能会失效的问题,应该及时更新迭代器或使用安全的方式操作。