您的位置：首页 > 游戏 > 手游 > 国家新冠疫情最新政策_建筑公司资质等级_站长工具ping_免费发广告的网站大全

国家新冠疫情最新政策_建筑公司资质等级_站长工具ping_免费发广告的网站大全

2025/3/10 19:11:50 来源：https://blog.csdn.net/qq_44955826/article/details/146020008  浏览:  次   关键词：国家新冠疫情最新政策_建筑公司资质等级_站长工具ping_免费发广告的网站大全
国家新冠疫情最新政策_建筑公司资质等级_站长工具ping_免费发广告的网站大全

概念

std::list 是标准模板库（STL）提供的一个容器类，它实现了双向链表的数据结构。

实现原理

内部结构

双向链表由多个节点连接而成。其中每个节点包含三个部分：

  • 内容/数据域：用于存储实际的数据元素。
  • 前驱：指向前一个节点的指针。
  • 后继：指向后一个节点的指针。

节点管理

当创建一个 std::list 对象时，它会维护一个头节点和尾节点，用于标记链表的起始和结束位置。头节点和尾节点通常是虚拟节点，不存储实际的数据，仅用于简化链表的操作。

插入操作

  • 在头部插入：创建一个新节点，将新节点的 next 指针指向原来的头节点的下一个节点，将原来头节点的下一个节点的 prev 指针指向新节点，然后更新头节点的 next 指针指向新节点，新节点的 prev 指针指向头节点。
  • 在尾部插入：创建一个新节点，将新节点的 prev 指针指向原来的尾节点的前一个节点，将原来尾节点的前一个节点的 next 指针指向新节点，然后更新尾节点的 prev 指针指向新节点，新节点的 next 指针指向尾节点。
  • 在中间插入：先找到插入位置的节点，创建一个新节点，调整新节点和相邻节点的 prev 和 next 指针，以将新节点插入到合适的位置。

删除操作

  • 删除头部元素：找到头节点的下一个节点，将头节点的 next 指针指向该节点的下一个节点，将该节点下一个节点的 prev 指针指向头节点，然后释放该节点的内存。

  • 删除尾部元素：找到尾节点的前一个节点，将尾节点的 prev 指针指向该节点的前一个节点，将该节点前一个节点的 next 指针指向尾节点，然后释放该节点的内存。
  • 删除中间元素：找到要删除的节点，调整其相邻节点的 prev 和 next 指针，跳过该节点，然后释放该节点的内存。

查找操作

从头节点开始遍历整个链表，直到找到指定元素或遍历完整个链表。

基本操作与方法接口

定义、初始化和赋值

#include <iostream>
#include <list>int main() 
{// 定义一个空的 list，存储 int 类型的元素std::list<int> List1;// 定义并初始化一个包含 5 个元素，每个元素都是默认值（0）的 liststd::list<int> List2(5);// 定义并初始化一个包含 5 个元素，每个元素的值都是 10 的 liststd::list<int> List3(5, 10);// 用另一个 list 初始化新的 liststd::list<int> List4(List3);// 用另一个 list 的迭代器范围初始化新的 liststd::list<int> List5(List4.begin(), List4.end());// 使用"拷贝初始化"初始化 liststd::list<int> List6 = { 1, 2, 3, 4, 5 };// 使用"直接列表初始化"初始化 liststd::list<int> List7{ 1, 2, 3, 4, 5 };
}

元素访问

front

访问第一个元素

List.front()
List.front() = 6;   //将第一个元素赋值为6
back

访问最后一个元素

List.back();
List.back() = 6;   //将最后一个元素赋值为6

迭代器

list 的节点在内存中是离散分布的，只能通过节点的指针依次访问相邻的节点。因此，其迭代器只支持双向访问，即可以使用 ++ 和 -- 操作符将迭代器向前或向后移动一个位置，但不支持随机访问操作。以下是 list  迭代器不支持的操作：

算术运算：不能使用 + 和 - 运算符将迭代器直接移动多个位置，因为要访问指定位置的元素，必须从当前位置开始，沿着链表依次遍历，时间复杂度为 (O(n))（较高）。如果非要使用 +- 运算，可以使用 std::advance 泛型算法。

部分比较运算：虽然可以使用 == 和 != 来判断两个迭代器是否相等，但不支持 >、<、<=、>= 等比较运算符，因为链表节点在内存中没有连续的地址顺序，无法直接比较位置关系。

正向迭代器

begin：返回容器中第一个元素的正向迭代器

end：返回容器中最后一个元素的后一个位置的正向迭代器

#include <iostream>
#include <list>int main() 
{std::list<int> List(5);// 使用正向迭代器为list赋值for (std::list<int>::iterator it = List.begin(); it != List.end(); ++it){*it = 3;}// 使用正向迭代器遍历list并打印其值for (std::list<int>::iterator it = List.begin(); it != List.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;
}

cbegin：返回容器中第一个元素的正向常量迭代器

cend：返回容器中最后一个元素的后一个位置的正向常量迭代器

常量迭代器的特点是，它只能用于读取元素，不能通过它来修改所指向的元素，这有助于在需要保证数据不被修改的场景下使用。

#include <iostream>
#include <list>int main() 
{std::list<int> List = {1, 2, 3, 4, 5 };// 遍历容器并输出元素for (std::list<int>::const_iterator it = List.cbegin(); it != List.cend(); ++it){// 可以读取元素std::cout << *it << " ";// 以下代码会编译错误，因为不能通过常量迭代器修改元素// *it = 10;}std::cout << std::endl;
}

反向迭代器

rbegin：返回容器中最后一个元素的反向迭代器

rend：返回容器中第一个元素的前一个位置的反向迭代器

#include <iostream>
#include <list>int main() 
{std::list<int> List = {1, 2, 3, 4, 5 };std::list<int>::reverse_iterator rit = List.rbegin();*rit = 23;std::cout << *rit;
}

crbegin：返回容器中第一个元素的反向常量迭代器

crend：返回容器中最后一个元素的后一个位置的反向常量迭代器

#include <iostream>
#include <list>int main() 
{std::list<int> List = {1, 2, 3, 4, 5 };//反向迭代器倒序遍历容器std::list<int>::const_reverse_iterator rit1 = List.crbegin();while (rit1 != List.crend()){std::cout << *rit1 << " ";		//先打印再自增++rit1;}std::cout << std::endl;/*不能使用下面的方法来正序遍历迭代器。 因为list 的迭代器是双向迭代器，不是随机访问迭代器，不能使用 rit2 - 1 这样的操作std::list<int>::const_reverse_iterator rit2 = List.crend();while (rit2 != List.crbegin()){std::cout << *(rit2 - 1) << " ";--rit2;}std::cout << std::endl;*///反向迭代器正序遍历容器std::list<int>::const_reverse_iterator rit2 = List.crend();while (rit2 != List.crbegin()){--rit2;		//先自减再打印std::cout << *rit2 << " ";}std::cout << std::endl;
}

对于反向迭代器：rbegin和crbegin到rend和crend为迭代器的正方向。rbegin和crbegin小于rend和crend，rbegin和crbegin通过自加可以到达rend和crend的位置。rend和crend大于rbegin和crbegin，rend和crend通过自减可以到达rbegin和crbegin的位置。

基于范围的for循环

注意向vector写入元素时，for循环中要加引用符&。原因见：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客

#include <iostream>
#include <list>using namespace std;int main() 
{list<int> List = {1, 2, 3, 4, 5 };for (int num : List){cout << num;}cout << endl;for (int& num : List){num = 9;cout << num;}cout << endl;for (int num : List){cout << num;}cout << endl;
}

容量

empty

判断容器是否为空，如果为空则返回 true，否则返回 false。

List.empty()
size

返回当前存储的元素个数

List.size()
max_size

返回可容纳的最大元素数量，即一直向list中添加元素直到溢出时的元素个数

List.max_size()

修改器

clear

清除list中的所有内容

List.clear()
insert

在指定位置插入元素

#include <iostream>
#include <list>
#include <array>// 打印vector中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 2, 3, 4, 5 };// 1. 在指定位置插入单个元素List.insert(List.begin(), 10);std::cout << "在指定位置插入单个元素: ";printList(List);// 2. 在指定位置插入多个相同值的元素List.insert( -- List.end(), 3, 20);std::cout << "在指定位置插入多个相同值的元素: ";printList(List);// 3. 在指定位置插入另一个容器的元素范围std::array<int, 2> a = { 30, 40 };List.insert(List.begin(), a.begin(), a.end());std::cout << "在指定位置插入另一个容器的元素范围: ";printList(List);// 4. 在指定位置插入初始化列表中的元素List.insert(List.end(), { 50, 60 });std::cout << "在指定位置插入初始化列表中的元素: ";printList(List);
}
emplace

原位构造元素

未完待续

emplace_back

在容器末尾原位构造元素

未完待续

emplace_front

在容器头部原位构造元素

未完待续

erase

移除单个元素

iterator erase(iterator position);

    position：这是一个迭代器，指向要移除的元素。

    返回一个迭代器，该迭代器指向被移除元素之后的那个元素。若移除的是列表的最后一个元素，就返回 end() 迭代器。

    移除一个范围内的元素

    iterator erase(iterator first, iterator last);

    first 和 last：这是两个迭代器，它们定义了要移除的元素范围 [first, last)。也就是说，这个范围包含 first 指向的元素，但不包含 last 指向的元素。

    返回一个迭代器，该迭代器指向被移除范围之后的第一个元素。若移除的是列表末尾的元素，就返回 end() 迭代器。

    #include <iostream>
#include <list>
#include <iterator>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };printList(List);List.erase(List.begin());printList(List);// 保存开始迭代器向前移动2个位置的迭代器auto it1 = List.begin();std::advance(it1, 2);// 保存结束迭代器向前移动3个位置的迭代器auto it2 = List.end();std::advance(it2, -3);List.erase(it1, it2);printList(List);
}

    push_front

    将元素添加到容器开头

    List.push_back("abc")    //将“abc”插入List开头
    push_back

    将元素添加到容器末尾

    List.push_back("abc")    //将“abc”插入List末尾
    pop_front

    移除开头元素

    List.pop_front()
    pop_back

    移除末尾元素

    List.pop_back()
    resize

    改变存储元素的个数

    #include <iostream>
#include <list>
#include <iterator>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 2, 3 };std::cout << "原始List： ";printList(List);List.resize(5);std::cout << "增加大小到 5 后： ";printList(List);List.resize(2);std::cout << "减少大小到 2 后： ";printList(List);List.resize(6, 4);std::cout << "增加大小到 6 并将新增的元素赋予默认值 4 后： ";printList(List);List.resize(3, 3);std::cout << "减少大小到 3 并将新增的元素（实际没有）赋予默认值 3 后： ";printList(List);
}

    swap

    交换两个list中的内容

    #include <iostream>
#include <list>
#include <iterator>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List1 = { 1, 2, 3 };std::list<int> List2 = { 4, 5 };List1.swap(List2);std::cout << "List1: ";printList(List1);std::cout << "List2: ";printList(List2);
}

    assign

    将值赋给容器

    #include <iostream>
#include <list>
#include <string>int main()
{std::list<char> List;// 使用Lambda表达式打印list中的元素auto print_list = [&](){for (char c : List){std::cout << c << ' ';}std::cout << '\n';};List.assign(5, 'a');print_list();const std::string extra = "hello world";List.assign(extra.begin(), extra.end());print_list();List.assign({ 'C', '+', '+', '1', '1' });print_list();
}

    操作

    sort

    对元素进行排序

    有两种重载形式。第一种是升序排序，第2种是按照自定义的比较规则排序。

    void sort();template< class Compare >
void sort( Compare comp );
    #include <functional>   //std::greater<int>()
#include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List{ 8, 7, 5, 9, 0, 1, 3, 2, 6, 4 };std::cout << "初始：";printList(List);List.sort();std::cout << "升序：";printList(List);List.sort(std::greater<int>());std::cout << "降序：";printList(List);
}

    merge

    合并两个有序列表，准确来说是按照一定比较规则将指定列表中的元素剪切至原列表中。

    默认比较方式

    void merge( list& other );
void merge( list&& other );

    other：要合并到当前列表的另一个 std::list 对象，可以是左值引用或右值引用。

    功能：将 other 列表中的所有元素合并到当前列表中，合并后 other 列表会变为空。两个列表都必须按照默认的比较规则（通常是 operator<）进行排序。

    示例代码：

    #include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List1 = { 5, 9, 1, 3, 3 };std::list<int> List2 = { 8, 7, 2, 3, 4, 4 };List1.sort();List2.sort();std::cout << "list1："; printList(List1);std::cout << "list2："; printList(List2);List1.merge(List2);std::cout << "合并后的list1："; printList(List1);std::cout << "合并后的list2："; printList(List2);
}

    自定义比较方式

    template< class Compare >
void merge( list& other, Compare comp );
template< class Compare >
void merge( list&& other, Compare comp );

    other：要合并到当前列表的另一个 std::list 对象，可以是左值引用或右值引用。

    comp：一个二元比较函数，用于定义元素的排序规则。该函数接受两个参数，返回一个布尔值，表示第一个参数是否应该排在第二个参数之前（如果返回的值为true，那么第一个参数要在第二个参数前）。

    功能描述：将 other 列表中的所有元素合并到当前列表中，合并后 other 列表会变为空。两个列表都必须按照 comp 指定的比较规则进行排序。

    示例代码：

    #include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}// 自定义比较函数，按降序排序
bool greater(int a, int b) 
{return a > b;
}int main()
{std::list<int> List1 = { 5, 9, 1, 3, 3 };std::list<int> List2 = { 8, 7, 2, 3, 4, 4 };List1.sort(greater);List2.sort(greater);std::cout << "list1："; printList(List1);std::cout << "list2："; printList(List2);List1.merge(List2, greater);std::cout << "合并后的list1："; printList(List1);std::cout << "合并后的list2："; printList(List2);
}

    splice

    从另一个 list 中移动元素

    转移整个列表

    void splice(const_iterator position, list& other);
void splice(const_iterator position, list&& other);

    position：这是一个常量迭代器，它指定了在目标列表中插入元素的位置。

    other：这是要转移元素的源列表，可以是左值引用或者右值引用。

    功能：把 other 列表中的所有元素转移到目标列表的 position 位置之前，转移完成后，other 列表会变为空。

    转移单个元素

    void splice(const_iterator position, list& other, const_iterator it);
void splice(const_iterator position, list&& other, const_iterator it);

    参数说明：

    position：常量迭代器，指定在目标列表中插入元素的位置。

    other：源列表，可以是左值引用或者右值引用。

    it：常量迭代器，指向 other 列表中要转移的单个元素。

    功能描述：把 other 列表中 it 所指向的元素转移到目标列表的 position 位置之前，转移后，该元素会从 other 列表中移除。

    转移元素范围

    void splice(const_iterator position, list& other, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& other, const_iterator first, const_iterator last);

    参数说明：

    position：常量迭代器，指定在目标列表中插入元素的位置。

    other：源列表，可以是左值引用或者右值引用。

    first 和 last：常量迭代器，定义了要转移的元素范围 [first, last)，也就是包含 first 指向的元素，但不包含 last 指向的元素。

    功能描述：把 other 列表中 [first, last) 范围内的元素转移到目标列表的 position 位置之前，转移后，这些元素会从 other 列表中移除。

    代码示例

    #include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List1 = { 1, 2, 3 };std::list<int> List2 = { 4, 5, 6 };// 把 List2 的所有元素转移到 List1 的开头List1.splice(List1.begin(), List2);std::cout << "List1: ";   printList(List1);std::cout << "List2: ";   printList(List2);std::list<int> List3 = { 1, 2, 3 };std::list<int> List4 = { 4, 5, 6 };// 把 List4 的第二个元素转移到 list1 的开头List3.splice(List3.begin(), List4, ++List4.begin());std::cout << "List3: ";     printList(List3);std::cout << "List4: ";     printList(List4);std::list<int> List5 = { 1, 2, 3, 4, 5, 6 };std::list<int> List6 = { 7, 8, 9 };// 把 List5 的第二个到倒数第二个之间的元素转移到 list6 的开头List6.splice(List6.begin(), List5, ++List5.begin(), --List5.end());std::cout << "List5: ";     printList(List5);std::cout << "List6: ";     printList(List6);
}

    remove

    移除列表中所有值等于指定值的元素

    C++20前，该方法没有返回值； C++20及C++20后，该方法返回移除的数量。

    #include <list>
#include <iostream>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 100, 2, 3, 10, 1, 11, -1, 12 };auto count = List.remove(1);std::cout << "移除了 " << count << " 个等于 1 的元素\n";printList(List);
}

    remove_if

    移除满足特定标准的元素

    C++20前，该方法没有返回值； C++20及C++20后，该方法返回移除的数量。

    void remove_if( UnaryPredicate p );
size_type remove_if( UnaryPredicate p );

    p：一个一元谓词函数（关于谓词函数的相关知识可以查看：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客），接受列表元素类型的参数，返回一个布尔值。如果返回 true，则表示该元素需要被移除。

    #include <list>
#include <iostream>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}// 定义一个一元谓词函数，判断元素是否为奇数
bool isOdd(int num) 
{return num % 2 != 0;
}int main() 
{std::list<int> List = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };// 移除所有奇数元素List.remove_if(isOdd);// 输出移除元素后的列表printList(List);
}
    reverse

    逆转容器中的元素顺序

    List.reverse()
    unique

    从列表中移除连续重复的元素，仅保留每个连续重复元素序列中的第一个元素

    默认比较方式

    void unique();    (C++20 前)
size_type unique();    (C++20 起)

    返回值：移除的元素数量。

    功能：使用 operator== 来比较相邻的元素，移除所有连续重复的元素，只保留每个连续重复元素序列中的第一个元素。

    #include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 1, 2, 2, 2, 3, 3, 1, 1 };List.unique();printList(List);
}

    自定义比较方式

    template< class BinaryPredicate >
void unique( BinaryPredicate p );    (C++20 前)template< class BinaryPredicate >
size_type unique( BinaryPredicate p );    (C++20 起)

      p：一个二元谓词函数 （关于谓词函数的相关知识可以查看：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客），用于比较相邻的元素。该函数接受两个参数，返回一个布尔值，表示这两个参数是否被视为相等。

      返回值：移除的元素数量。

      功能：使用用户提供的二元谓词 p 来比较相邻的元素，移除所有被 p 判断为相等的连续元素，只保留每个连续重复元素序列中的第一个元素。

      #include <iostream>
#include <list>// 自定义二元谓词，判断两个元素的绝对值是否相等
bool absEqual(int a, int b) 
{return std::abs(a) == std::abs(b);
}// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main() 
{std::list<int> List = { 1, -1, 2, 2, -2, 3, 3, -1, 1 };List.unique(absEqual);printList(List);
}

      参考与引用

      C++ STL list 容器详解-CSDN博客

      C++——list的简介及使用_c++ list-CSDN博客

      std::list - cppreference.com

      百度安全验证

      未完待续

      写出容器方法的底层实现原理和复杂度。

      未完待续

      版权声明:

      本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

      我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

      最新新闻

      热搜词

      java在事务提交后的执行方法 数据结构和算法学习网站 日志说明 大数据究竟值多少钱？ GitHub上传项目 P4017 最大食物链计数

      声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

      客户服务 | 关于我们 | 版权声明

      版权所有：

      Copyright 2024 尧图网 All Rights Reserved.QQ:809451989