浅谈C++|STL之list+forward_list篇

2023-09-13 22:50:12

在这里插入图片描述
一.list基本概念

功能:将数据进行链式存储

链表(list)是一种物理存储单元上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的组成:链表由—系列结点组成

结点的组成:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域

STL中的链表是一个双向循环链表

在这里插入图片描述

由于链表的存储方式并不是连续的内存空间,因此链表list中的迭代器只支持前移和后移,属于双向迭代器

list的优点:
·采用动态存储分配,不会造成内存浪费和溢出
·链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素

list的缺点:
·链表灵活,但是空间(指针域)和时间(遍历)额外耗费较大
List有一个重要的性质,插入操作和删除操作都不会造成原有list迭代器的失效,这在vector是不成立的。

总结:STL中List和vector是两个最常被使用的容器,各有优缺点

二.list构造函数

以下是在每个构造函数后添加的示例代码:

  1. 默认构造函数:
std::list<int> myList;  // 创建一个空的 int 类型的双向链表容器
  1. 带有元素个数参数的构造函数:
std::list<int> myList(5, 10);  // 创建一个包含 5 个值为 10 的 int 类型的双向链表容器
  1. 区间构造函数:
std::vector<int> myVector = {1, 2, 3, 4, 5};
std::list<int> myList(myVector.begin() + 1, myVector.end() - 1);  // 创建一个包含 myVector 中除了第一个和最后一个元素的剩余元素的双向链表容器
  1. 拷贝构造函数:
std::list<int> originalList = {1, 2, 3, 4, 5};
std::list<int> copiedList(originalList);  // 创建一个拷贝 originalList 的新双向链表容器
  1. 移动构造函数:
std::list<int> originalList = {1, 2, 3, 4, 5};
std::list<int> movedList(std::move(originalList));  // 创建一个移动 originalList 元素到新双向链表容器中的新容器
  1. 初始化列表构造函数:
std::list<int> myList = {1, 2, 3, 4, 5};  // 使用初始化列表中的元素初始化一个 int 类型的双向链表容器
构造函数示例
默认构造函数std::list<int> myList;
带有元素个数参数的构造函数std::list<int> myList(5, 10);
区间构造函数std::vector<int> myVector = {1, 2, 3, 4, 5};
std::list<int> myList(myVector.begin() + 1, myVector.end() - 1);
拷贝构造函数std::list<int> originalList = {1, 2, 3, 4, 5};
std::list<int> copiedList(originalList);
移动构造函数std::list<int> originalList = {1, 2, 3, 4, 5};
std::list<int> movedList(std::move(originalList));
初始化列表构造函数std::list<int> myList = {1, 2, 3, 4, 5};

三.list赋值和交换

当涉及到赋值、交换和 assign 函数时,你可以使用以下方法来操作 std::list 容器:

  1. 赋值操作符(operator=):

    std::list<int> list1 = {1, 2, 3, 4, 5};
    std::list<int> list2;
    
    // 使用赋值操作符将 list1 中的元素赋值给 list2
    list2 = list1;
    
  2. swap 函数:

    std::list<int> list1 = {1, 2, 3, 4, 5};
    std::list<int> list2 = {10, 20, 30};
    
    // 使用 swap 函数交换 list1 和 list2 中的所有元素
    list1.swap(list2);
    
    // 或者使用 std::swap
    std::swap(list1, list2);
    
  3. assign 函数:

    std::list<int> myList;
    
    // 使用 assign 函数将特定值赋给 myList
    myList.assign(5, 10);
    
    // 使用 assign 函数将范围内的元素赋给 myList
    std::vector<int> myVector = {1, 2, 3, 4, 5};
    myList.assign(myVector.begin() + 1, myVector.end() - 1);
    
    // 使用 assign 函数使用初始化列表中的元素进行赋值给 myList
    myList.assign({1, 2, 3, 4, 5});
    

通过使用这些操作,你可以方便地在 std::list 容器中进行赋值、交换和赋特定值、赋范围以及使用初始化列表进行赋值的操作。请记住,在这些操作之后,原容器中的元素将被替换为新赋值的元素,原容器中的迭代器、引用和指针等将不再有效。

操作示例
赋值操作符(operator=std::list<int> list1 = {1, 2, 3, 4, 5};
std::list<int> list2;
list2 = list1;
swap 函数std::list<int> list1 = {1, 2, 3, 4, 5};
std::list<int> list2 = {10, 20, 30};
list1.swap(list2);
// 或者使用 std::swap
std::swap(list1, list2);
assign 函数std::list<int> myList;
myList.assign(5, 10);
std::vector<int> myVector = {1, 2, 3, 4, 5};
myList.assign(myVector.begin() + 1, myVector.end() - 1);
myList.assign({1, 2, 3, 4, 5});

四.list大小操作

当涉及到获取和调整 std::list 的大小时,你可以使用以下函数:

  1. 获取大小:

    • size 函数:返回列表中元素的数量。
    • max_size 函数:返回列表所能容纳的最大元素数量。
    • empty 函数:检查列表是否为空。

    示例:

    std::list<int> myList = {1, 2, 3, 4, 5};
    
    size_t length = myList.size();              // 获取列表的大小
    size_t maxSize = myList.max_size();          // 返回列表能够容纳的最大元素数量
    bool isEmpty = myList.empty();               // 检查列表是否为空
    
  2. 调整大小:

    • resize 函数:调整列表的大小。
    • clear 函数:清空列表中的所有元素。

    示例:

    std::list<int> myList = {1, 2, 3, 4, 5};
    
    myList.resize(10);               // 调整列表的大小为 10
    myList.resize(8, 0);             // 调整列表的大小为 8,并插入值为 0 的元素
    myList.clear();                  // 清空列表中的所有元素
    

通过使用这些函数,你可以方便地获取列表的大小、最大容量以及检查列表是否为空。同时,你也可以调整列表的大小或清空列表中的元素。请根据实际需求选择适合的函数来操作 std::list 容器。
下面是整理成表格的关于获取和调整 std::list 大小的函数接口及示例:

操作示例描述
获取大小std::list<int>::size()返回列表中元素的数量。
获取最大容量std::list<int>::max_size()返回列表所能容纳的最大元素数量。
检查是否为空std::list<int>::empty()检查列表是否为空。
调整大小std::list<int>::resize(size_type count)调整列表的大小。
带默认值的调整大小std::list<int>::resize(size_type count, const T& value)调整列表的大小,并插入默认值元素。
清空列表std::list<int>::clear()清空列表中的所有元素。

示例:

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    
    // 获取大小
    size_t length = myList.size();              // 获取列表的大小
    std::cout << "Size: " << length << std::endl;

    // 获取最大容量
    size_t maxSize = myList.max_size();          // 返回列表能够容纳的最大元素数量
    std::cout << "Max Size: " << maxSize << std::endl;
    
    // 检查是否为空
    bool isEmpty = myList.empty();               // 检查列表是否为空
    std::cout << "Is Empty: " << std::boolalpha << isEmpty << std::endl;
    
    // 调整大小
    myList.resize(10);               // 调整列表的大小为 10
    myList.resize(8, 0);             // 调整列表的大小为 8,并插入值为 0 的元素

    // 清空列表
    myList.clear();                  // 清空列表中的所有元素

    return 0;
}

五.list的插入和删除

在C++中,使用STL的list容器可以实现高效的插入和删除操作。以下是关于list的插入和删除的一些基本操作:

  1. 插入元素:
    • 在列表头部插入元素:使用push_front()函数。
    • 在列表尾部插入元素:使用push_back()函数。
    • 在指定位置之前插入元素:使用insert()函数,传递需要插入的位置和要插入的元素的值。
std::list<int> myList;
myList.push_front(10);  // 在头部插入元素
myList.push_back(20);   // 在尾部插入元素
auto it = std::next(myList.begin());  // 获取迭代器指向第一个元素之后的位置
myList.insert(it, 15);  // 在指定位置之前插入元素
myList.insert(it, 15015);  // 在指定位置之前插入150个元素
myList.insert(myList.begin(),myList.end());  // 迭代器插入
  1. 删除元素:
    • 删除列表头部的元素:使用pop_front()函数。
    • 删除列表尾部的元素:使用pop_back()函数。
    • 删除指定位置的元素:使用erase()函数,传递要删除的元素的位置。
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.push_back(30);
myList.pop_front();  // 移除头部元素
myList.pop_back();   // 移除尾部元素
auto it = std::next(myList.begin());  // 获取迭代器指向第一个元素之后的位置
myList.erase(it);    // 移除指定位置的元素
myList.erase(myList.begin(),myList.end());    // 移除指定区间的元素
  1. remove()函数用于删除list容器中所有与指定值相等的元素。它会对容器进行遍历,将符合条件的元素删除。以下是示例代码:
std::list<int> myList { 10, 20, 30, 40, 10, 50 };

myList.remove(10); // 删除所有值为10的元素

// 打印剩余的元素
for (const auto& elem : myList) {
    std::cout << elem << " ";
}
// 输出: 20 30 40 50
  1. clear()函数用于清空整个list容器,将其变为空列表。以下是示例代码:
std::list<int> myList { 10, 20, 30 };

myList.clear(); // 清空list

std::cout << "Size of list: " << myList.size() << std::endl; // 输出: 0

remove()函数删除所有与指定值相等的元素,而非删除指定位置的元素。若要删除指定位置的元素,仍需使用erase()函数。

list容器支持常数时间复杂度的插入和删除操作,但在访问和查找元素方面相对较差。同时,list容器不支持随机访问,只能通过迭代器进行访问。

auto是什么?

在C++11及以后的版本中,可以使用关键字auto来自动推导变量的类型。当使用auto声明变量时,编译器会根据变量的初始化值来推导出变量的类型。

在上述示例代码中,auto被用于声明一个迭代器it,通过调用std::next()函数来获取myList中第一个元素之后的位置。std::next()函数返回一个迭代器,而使用auto让编译器根据返回值来自动推导出it的类型,以保证类型匹配。

使用auto关键字的好处是可以简化代码,减少类型声明的冗余,并且在某些情况下可以更灵活地处理不同类型的变量。然而,需要注意的是,auto并不是完全的类型推导,它只能在编译时确定变量的类型,而不能用于运行时动态类型的情况。

接口描述
insert(pos, value)在指定位置之前插入一个元素,并返回指向新插入元素的迭代器。
insert(pos, count, value)在指定位置之前插入多个相同值的元素,并返回指向第一个新插入元素的迭代器。
insert(pos, first, last)在指定位置之前插入另一个迭代器范围内的元素,并返回指向第一个新插入元素的迭代器。
emplace(pos, args…)在指定位置之前就地构造一个元素,并返回指向插入元素的迭代器。此函数避免额外的拷贝或移动操作。
push_back(value)在容器末尾插入一个元素。
push_front(value)在容器开头插入一个元素。
pop_back()移除容器末尾的元素。
pop_front()移除容器开头的元素。
erase(pos)移除指定位置的元素,并返回指向被删除元素之后的一个元素的迭代器。
erase(first, last)移除一个迭代器范围内的元素,并返回指向最后一个被删除元素之后的一个元素的迭代器。
remove(value)移除容器中所有与给定值相等的元素。

六.数据存取和遍历

在这里插入图片描述

在C++的STL中,list容器是一个双向链表,其数据存取方式与使用索引进行访问的容器(例如vector)有所不同。

要访问list容器中的数据,可以使用迭代器。迭代器提供了一种访问容器元素的通用方式,而不需要依赖索引。以下是一些常用的数据存取操作:

  1. 访问首尾元素:
    • 使用front()函数可以访问容器的第一个元素。
    • 使用back()函数可以访问容器的最后一个元素。
std::list<int> myList { 10, 20, 30 };
int firstElement = myList.front();   // 访问第一个元素
int lastElement = myList.back();     // 访问最后一个元素
  1. 使用迭代器遍历元素:
    • 使用begin()函数获取指向容器第一个元素的迭代器。
    • 使用end()函数获取指向容器最后一个元素之后位置的迭代器。
std::list<int> myList { 10, 20, 30 };
for (auto it = myList.begin(); it != myList.end(); ++it) {
    // 使用迭代器访问元素
    int element = *it;
    // 进行操作
}
  1. 使用范围遍历语法:
    • 使用C++11引入的范围遍历语法,可以更简洁地遍历容器元素。
std::list<int> myList { 10, 20, 30 };
for (const auto& element : myList) {
    // 使用范围遍历访问元素
    // 进行操作
}

需要注意的是,由于list是一个双向链表,它不能像vector那样通过索引直接访问元素,因为链表的元素没有直接的索引位置。因此,在list中按索引进行访问或查找需要通过迭代器和线性搜索来实现。

加强for循环

当使用范围遍历语法时,可以更简洁地遍历容器元素,不需要显式地操作迭代器。以下是对第三种遍历方法的详细介绍:

  1. 范围遍历语法:

    std::list<int> myList { 10, 20, 30 };
    for (const auto& element : myList) {
        // 使用范围遍历访问元素
        // 进行操作
    }
    
    • myList是一个std::list<int>类型的容器,初始化了三个整型元素。
    • for循环遍历myList容器中的每个元素。
    • const auto& element定义了一个循环变量element,用于依次访问容器中的元素。auto关键字用于自动推导element的类型。
    • element是一个常量引用,可以以只读方式访问容器中的元素值。
  2. 范围遍历的优点:

    • 简洁:范围遍历语法更加简洁,不需要手动操作迭代器。
    • 安全:范围遍历中的循环变量为常量引用,防止意外修改元素。
    • 自动推导类型:使用auto关键字可以自动推导循环变量的类型,无需显式声明。

范围遍历适用于大多数容器类型,包括vectorlistsetmap等。然而,范围遍历仅适用于对容器中元素的只读访问。如果需要对元素进行修改,可以将循环变量声明为非常量引用。

操作描述
front()访问容器的第一个元素。
back()访问容器的最后一个元素。
begin()获取指向容器第一个元素的迭代器。
end()获取指向容器最后一个元素之后位置的迭代器。
for-each (范围遍历语法)使用C++11引入的范围遍历语法,按顺序遍历容器中的每个元素。

七.反转和排序

  1. 反转(Reverse):
    • 可以使用reverse()函数对std::list容器进行反转操作。
    • 这将会使容器中的元素逆序排列。

示例代码:

std::list<int> myList { 1, 2, 3, 4, 5 };
myList.reverse();  // 反转容器中的元素
  1. 排序(Sort):
    • 可以使用sort()函数对std::list容器进行排序操作。
    • 默认情况下,sort()函数按升序对容器元素进行排序。
    • 也可以通过提供自定义的比较函数来实现自定义排序。

示例代码:

std::list<int> myList { 5, 3, 1, 4, 2 };
myList.sort();  // 按升序对容器中的元素进行排序

自定义排序的示例代码:

bool descendingOrder(int a, int b) {
    return a > b;
}

std::list<int> myList { 5, 3, 1, 4, 2 };
myList.sort(descendingOrder);  // 按降序对容器中的元素进行排序

由于std::list是一个双向链表,排序操作可能比较耗时,因为它需要通过链表中的指针进行交换操作。而对于反转操作来说,它可以在常数时间内完成。

操作描述
reverse()反转容器中的元素。
sort()按升序对容器中的元素进行排序(默认)。
sort(comp)按指定的比较函数对容器中的元素进行排序,用于自定义排序规则。

八.函数接口

构造函数
list();默认构造函数
explicit list(const Allocator& alloc);带分配器的构造函数
explicit list(size_type count, const T& value = T(), const Allocator& alloc = Allocator());使用初始元素和分配器的构造函数
迭代器
iterator begin();返回指向首元素的迭代器
const_iterator begin() const;返回指向首元素的常量迭代器
iterator end();返回指向尾后元素的迭代器
const_iterator end() const;返回指向尾后元素的常量迭代器
reverse_iterator rbegin();返回指向尾元素的反向迭代器
const_reverse_iterator rbegin() const;返回指向尾元素的常量反向迭代器
reverse_iterator rend();返回指向首前元素的反向迭代器
const_reverse_iterator rend() const;返回指向首前元素的常量反向迭代器
容量
bool empty() const;检查列表是否为空
size_type size() const;返回列表中的元素数量
size_type max_size() const;返回列表可容纳的最大元素数量
元素访问
reference front();返回第一个元素的引用
const_reference front() const;返回第一个元素的常量引用
reference back();返回最后一个元素的引用
const_reference back() const;返回最后一个元素的常量引用
修改器
template <class... Args> void emplace_front(Args&&... args);在列表开始处插入元素
void push_front(const T& value);在列表开始处插入元素
void push_front(T&& value);在列表开始处插入移动元素
void pop_front();移除列表开始处的元素
template <class... Args> void emplace_back(Args&&... args);在列表末尾插入元素
void push_back(const T& value);在列表末尾插入元素
void push_back(T&& value);在列表末尾插入移动元素
void pop_back();移除列表末尾的元素
template <class... Args> iterator emplace(const_iterator pos, Args&&... args);在迭代器指定位置插入元素
iterator insert(const_iterator pos, const T& value);在迭代器指定位置插入元素
iterator insert(const_iterator pos, T&& value);在迭代器指定位置插入移动元素
iterator insert(const_iterator pos, size_type count, const T& value);在迭代器指定位置插入多个元素
template <class InputIterator> iterator insert(const_iterator pos, InputIterator first, InputIterator last);在迭代器指定位置插入范围内的元素
iterator erase(const_iterator pos);移除指定位置的元素
iterator erase(const_iterator first, const_iterator last);移除指定范围内的元素
void swap(list& other);交换两个列表的内容
void resize(size_type count);改变列表的大小
void resize(size_type count, const value_type& value);改变列表的大小并填充元素
void clear();移除列表中的所有元素
操作
void remove(const T& value);移除与指定值相等的所有元素
template <class Predicate> void remove_if(Predicate pred);移除满足谓词的所有元素
void unique();移除连续相等的元素
template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);根据二元谓词移除连续满足条件的元素
void merge(list& other);合并另一个列表
template <class Compare> void merge(list& other, Compare comp);根据比较函数合并另一个列表
void sort();对列表进行排序
template <class Compare> void sort(Compare comp);使用自定义比较函数对列表排序
void reverse();反转列表中元素的顺序
双向链表专属操作
void splice(const_iterator pos, list& other);将另一个列表合并到指定位置之前
void splice(const_iterator pos, list&& other);将右值引用的列表合并到指定位置之前
void splice(const_iterator pos, list& other, const_iterator it);将另一个列表中的一个元素移动到指定位置之前
void splice(const_iterator pos, list&& other, const_iterator it);将右值引用列表中的一个元素移动到指定位置之前
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);将另一个列表中的一段元素移动到指定位置之前
void splice(const_iterator pos, list&& other, const_iterator first, const_iterator last);将右值引用列表中的一段元素移动到指定位置之前
比较操作
bool operator==(const list& other) const;列表相等比较
bool operator!=(const list& other) const;列表不相等比较
bool operator<(const list& other) const;列表小于比较
bool operator<=(const list& other) const;列表小于等于比较
bool operator>(const list& other) const;列表大于比较
bool operator>=(const list& other) const;列表大于等于比较

九.forward_list单向链表

操作描述
emplace_front(args)在链表的前方插入一个元素,使用参数 args 构造元素。
push_front(value)在链表的前方插入一个已构造的元素。
pop_front()移除链表的第一个元素。
begin()返回指向链表开头的迭代器。
end()返回指向链表末尾之后位置的迭代器。
empty()检查链表是否为空。
size()返回链表中的元素个数。
erase_after(pos)移除链表中 pos 之后的元素。
insert_after(pos, value)在链表中 pos 之后插入一个已构造的元素。
resize(count)改变链表的大小,使其包含 count 个元素。
swap(other_list)交换两个链表的内容。
更多推荐

【从入门到起飞】JavaAPI—System,Runtime,Object,Objects类

🎊专栏【JavaSE】🍔喜欢的诗句:更喜岷山千里雪三军过后尽开颜。🎆音乐分享【如愿】🎄欢迎并且感谢大家指出小吉的问题🥰文章目录🍔System类⭐exit()⭐currentTimeMillis()🎄用处⭐arraycopy()🍔Runtime类⭐创建对象⭐exit()⭐availableProcesso

写一篇nginx配置指南

nginx.conf配置找到Nginx的安装目录下的nginx.conf文件,该文件负责Nginx的基础功能配置。配置文件概述Nginx的主配置文件(conf/nginx.conf)按以下结构组织:配置块功能描述全局块与Nginx运行相关的全局设置events块与网络连接有关的设置http块代理、缓存、日志、虚拟主机等

【计算机网络】网络编程接口 Socket API 解读(6)

Socket是网络协议栈暴露给编程人员的API,相比复杂的计算机网络协议,API对关键操作和配置数据进行了抽象,简化了程序编程。本文讲述的socket内容源自Linuxman。本文主要对各API进行详细介绍,从而更好的理解socket编程。recvrecv()遵循POSIX.1-20081.库标准c库,libc,-lc

Ubuntu 安装 CUDA 与 CUDNN GPU加速引擎

一、NVIDIA(英伟达)显卡驱动安装NVIDIA显卡驱动可以通过指令sudoaptpurgenvidia*删除以前安装的NVIDIA驱动版本,重新安装。1.1.关闭系统自带驱动nouveau注意!在安装NVIDIA驱动以前需要禁止系统自带显卡驱动nouveau:可以先通过指令lsmod|grepnouveau查看no

嵌入式笔试面试刷题(day11)

文章目录前言一、字节流,数据报,报文二、makefile怎么引入库和模块三、多次free一块内存空间会怎么样四、字符操作函数越界会发生什么五、QT中一个信号可以连接多个槽函数吗六、QT中一个槽函数可以对应多个信号吗总结前言本篇文章继续刷题。一、字节流,数据报,报文1.数据报(Datagram):数据报是一种独立的、特定

Linux:基础开发工具之Makefile和缓冲区的基本概念

文章目录动静态库自动化构建代码缓冲区原理实现具体实现动静态库首先要知道什么是链接:C程序中,并没有定义printf的函数实现,且在预编译中包含的stdio.h中也只有该函数的声明,而没有定义函数的实现系统把这些函数实现都被做到名为libc.so.6的库文件中去了,在没有特别指定时,gcc会到系统默认的搜索路径“/usr

JAVA面经整理(2)

一)解决哈希冲突的方法有哪些?哈希冲突指的是在哈希表中,不同的键值映射到了相同的哈希桶,也就是数组索引,导致键值对的冲突1)设立合适的哈希函数:通过哈希函数计算出来的地址要均匀的分布在整个空间中2)负载因子调节:2.1)开放地址法:1)当发生哈希冲突时,如果哈希表中没有装满,说明哈希表中一定还有空余位置,那么可以把ke

基于Python Django的公务员考试信息管理系统

文章目录1简介2.技术栈3功能分析4功能具体设计4.1软件功能模块设计4.2数据库设计与实现4.2.1概念模型设计4.2.2数据库逻辑结构设计5系统详细设计5.1系统功能模块5.2管理员功能模块六源码咨询1简介公务员考试信息管理系统的开发运用Python技术,MIS的总体思想,以及MYSQL等技术的支持下共同完成了该系

Linux系统编程(信号处理 sigacation函数和sigqueue函数 )

文章目录前言一、sigaction二、sigqueue函数三、代码示例总结前言本篇文章我们来介绍一下sigacation函数和sigqueue函数。一、sigactionsigaction是一个用于设置和检查信号处理程序的函数。它允许我们指定信号的处理方式,包括指定一个函数作为信号处理程序、设置标志位以及指定信号处理程

Linux系统编程(信号处理机制)

文章目录前言一、中断,异常,信号的区别二、信号在Linux中的标识三、信号处理相关函数四、代码实验总结前言本篇文章我们来讲解信号的处理机制,信号处理在Linux操作系统中必不可少,这一点值得大家注意,信号又会与中断,异常一起讨论,那么下面我们就来看看到底什么是信号吧。一、中断,异常,信号的区别中断、异常和信号是计算机系

MAC MINI 2012安装Montery折腾笔记

MACMINI2012安装Montery折腾笔记(作为电视盒子/远程开发机)起因:手头有个macmini,2018年买的2手。一直都是10.12系统,处理python和苹果开发都受制于旧系统,很多软件也装不上,于是有了升级的需求,打算折腾下再战3年直接升级使用因特网恢复系统模式,恢复到最新适配的版本开机时,按Win+A

热文推荐