c++拓展-7:序列式容器STL list

list容器

简要说明及其定义

list容器，又称双向链表容器，底层实现为双向链表形式，元素可分散存储在内存空间中，前后顺序靠指针维系，每个元素都配备指向前驱和后继的两个指针，第一个元素前驱为NULL，最后一个元素后继为NULL

list容器可以在序列已知的任何位置快速插入和删除元素，并且在list容器中移动元素的效率也比其他容器高，但它不能直接通过位置访问元素，而是需要顺序遍历前面的所有元素直到找到该位置

所以当需要对序列大量添加、删除元素，却不常直接访问元素数据时，list容器最为高效适用，其创建如下：

#include <list>
using namespace std;
list<int> values;	//创建空list容器
list<int> value1(10);	//创建包含10个元素的list容器
list<int> value2(10, 5);	//创建包含10个元素且初值为5的list容器
list<int> value3(value1);	//拷贝创建一个和value1一样的list容器
int a[] = { 1,2,3,4,5 };
list<int> values(a, a+5);	//拷贝普通数组创建list 容器
array<int, 5>arr{ 11,12,13,14,15 };
list<int>values(arr.begin()+2, arr.end());	//拷贝其它容器，创建list 容器

容器提供的成员函数

成员函数	功能
begin()	返回指向容器中第一个元素的双向迭代器
end()	返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器
rbegin()	返回指向最后一个元素的反向双向迭代器
rend()	返回指向第一个元素所在位置前一个位置的反向双向迭代器
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false
size()	返回当前容器实际包含的元素个数
max_size()	返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 2^32-1，所以我们很少会用到这个函数
front()	返回第一个元素的引用
back()	返回最后一个元素的引用
assign()	用新元素替换容器中原有内容
emplace_front()	在容器头部生成一个元素，该函数和 push_front() 的功能相同，但效率更高
push_front()	在容器头部插入一个元素
pop_front()	删除容器头部的一个元素
emplace_back()	在容器尾部直接生成一个元素，该函数和 push_back() 的功能相同，但效率更高
push_back()	在容器尾部插入一个元素
pop_back()	删除容器尾部的一个元素
emplace()	在容器中的指定位置插入元素，该函数和 insert() 功能相同，但效率更高
insert()	在容器中的指定位置插入元素
erase()	删除容器中一个或某区域内的元素
swap()	交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的
resize()	调整容器的大小
clear()	删除容器存储的所有元素
splice()	将一个 list 容器中的元素插入到另一个容器的指定位置
remove(val)	删除容器中所有等于 val 的元素
remove_if()	删除容器中满足条件的元素
unique()	删除容器中相邻的重复元素，只保留一个
merge()	合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的
sort()	通过更改容器中元素的位置，将它们进行排序
reverse()	反转容器中元素的顺序

list容器迭代器

list容器的迭代器相关成员函数有begin/end、rbegin/rend、cbegin/cend、crbegin/crend，具体可参见array和vector篇

但list容器配备的迭代器类型为双向迭代器，不再是之前的随机访问迭代器

这意味着，假设 p1 和 p2 都是双向迭代器，则它们支持使用 ++p1、 p1++、 p1–、 p1++、 *p1、 p1==p2 以及 p1!=p2 运算符，但不支持以下操作（其中 i 为整数）：

• p1[i]：不能通过下标访问 list 容器中指定位置处的元素
• 双向迭代器不支持使用 -=、+=、+、- 运算符
• 双向迭代器不支持使用 <、 >、 <=、 >= 比较运算符

list容器在插入insert（）、接合splice（）等操作时不会造成原有list迭代器失效，删除操作时也仅有指向被删除元素的迭代器失效，其他迭代器不受影响

访问list容器

由于list容器不支持随机访问，未提供下标操作符[ ]和at（）成员函数，也没有data（）成员函数，只能使用front（）成员函数和back（）成员函数，用于返回list容器中第一个元素和最后一个元素的引用

如果想要访问list容器存储的其他元素，只能使用list容器的迭代器，例如:

#include <iostream>
#include <list>
using namespace std;
int main()
{
    const std::list<int> mylist{1,2,3,4,5};
    auto it = mylist.begin();
    cout << *it << " ";
    ++it;
    while (it!=mylist.end())
    {
        cout << *it << " ";
        ++it;  
    }
    return 0;
}

而对于修改容器中指定元素的值，list模板类提供专门的成员函数assign（）：

• assign(count, value) ：其中count是值的个数，value是分配给元素的值
• assign(begin，end)：其中begin为起始位置，end为结束位置，常作将元素从已有列表复制过来，并覆盖该列表原来的元素值

除此之外，assign（）函数还可以实现不同容器之间，相容类型的赋值或者是对不能使用赋值符“=”进行赋值的数据类型赋值

添删元素

插入元素

list容器中，通用的增添元素方法依旧适用，如：

• push_front()：向 list 容器首个元素前添加新元素
• push_back()：向 list 容器最后一个元素后添加新元素
• emplace_front()：在容器首个元素前直接生成新的元素
• emplace_back()：在容器最后一个元素后直接生成新的元素
• emplace()：在容器的指定位置直接生成新的元素
• insert()：在指定位置插入新元素

而除deque等容器增删元素的方法外，list容器还有一个成员函数splice（），用于将其他list容器存储的多个元素添加到当前list容器的指定位置

语法格式	功能
void splice (iterator position, list& x);	position 为迭代器，用于指明插入位置；x 为另一个 list 容器。 此格式的 splice() 方法的功能是，将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator i);	position 为迭代器，用于指明插入位置；x 为另一个 list 容器；i 也是一个迭代器，用于指向 x 容器中某个元素。 此格式的 splice() 方法的功能是将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator first, iterator last);	position 为迭代器，用于指明插入位置；x 为另一个 list 容器；first 和 last 都是迭代器，[fist,last) 用于指定 x 容器中的某个区域。 此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处。

splice() 成员方法移动元素的方式，是将存储该元素的节点从 list 容器底层的链表中摘除，然后再链接到当前 list 容器底层的链表中，也就是当使用 splice() 成员方法将 x 容器中的元素添加到当前容器的同时，该元素会从 x 容器中删除，实现的过程相当于是“剪切”而不是“复制”

删除元素

list容器中，通用的删除元素方法依旧适用，如：

• pop_front() 删除位于 list 容器头部的一个元素
• pop_back() 删除位于 list 容器尾部的一个元素
• erase() 该成员函数既可以删除 list 容器中指定位置处的元素，也可以删除容器中某个区域内的多个元素
• clear() 删除 list 容器存储的所有元素

而list容器中新增的方法成员函数有：

• remove(val) 删除容器中所有等于 val 的元素
• remove_if() 删除容器中满足条件的元素
• unique() 删除容器中相邻的重复元素，只保留一份

其中unique（）可以直接无参使用，也可以自定义传入一个二元谓词函数：

#include <iostream>
#include <list>
using namespace std;

bool demo(double first, double second)	//二元谓词函数的定义
{
    return (int(first) == int(second));
}

int main()
{
    list<double> mylist{ 1,1.2,1.2,3,4,4.5,4.6 };
    //删除相邻重复的元素，仅保留一份
    mylist.unique();//{1, 1.2, 3, 4, 4.5, 4.6}
    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        cout << *it << ' ';
    cout << endl;
    //demo 为二元谓词函数，是自定义的去重规则
    mylist.unique(demo);
    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        cout << *it << ' ';
    return 0;
}

输出结果为：

1 1.2 3 4 4.5 4.6 1 3 4

谓词函数是一个判断式，一个返回bool值的函数或者仿函数。几元就是函数有几个参数，至于定义和使用，函数定义和一般的函数定义一样，仿函数就是写个类，然后重载operator()。可以在需要返回bool值的函数作参数的函数里使用。

此外，将自定义的谓词函数传给remove_if()成员函数，list容器中能使函数成立的元素都会被删除：

remove_if(begin,end,op)：其中begin是起始位置，end为结束位置，op为传入的回调函数，如果返回true，则将当前指向的参数移到尾部（故而需要和erase一起使用才能真正删除元素），其返回值为被移动区域的首个元素

#include <iostream>
#include <list>
using namespace std;
int main()
{
    list<int> mylist{ 15, 36, 7, 17, 20, 39, 4, 1 };
    //删除 mylist 容器中能够使表达式成立的所有元素
    mylist.remove_if([](int value) {return (value < 10); }); //{15 36 17 20 39}
    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        cout << ' ' << *it;
    return 0;
}

输出结果为：

15 36 17 20 39

回调函数就是一个被作为参数传递的函数。上述代码中，mylist.remove_if( [ ] (int value) {return (value < 10); });相当于前两个参数默认使用了mylist的begin和end位置，回调函数的参数是int类型的value，当value<10时，回调函数将返回这个表达式的值（false/true）

更加高效的list——forward_list

forward_list是c++11标准新添加的一类容器，底层实现和list一样采用链表，但采用的是单链表（相邻元素间只有从前驱指向后驱的指针），list采用的是双链表（相邻元素间有从前向后的指针，也有从后向前的指针）

相较list，forward_list同样擅长在序列的任何位置进行插入或删除，而不擅长随机访问元素，而且由于指针从前驱指向后驱，所以配备的迭代器也只有前向迭代器，而不是双向迭代器

使用forward_list的意义主要是效率高，且在存储相同个数元素时单链表所用空间更少，空间利用率更高，对于某些操作的执行效率也更高，故当list和forward_list都能完成时，应该首选forward_list容器

以下为forward_list的成员函数：

成员函数	功能
before_begin()	返回一个前向迭代器，其指向容器中第一个元素之前的位置。
begin()	返回一个前向迭代器，其指向容器中第一个元素的位置。
end()	返回一个前向迭代器，其指向容器中最后一个元素之后的位置。
cbefore_begin()	和 before_begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
max_size()	返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
front()	返回第一个元素的引用。
assign()	用新元素替换容器中原有内容。
push_front()	在容器头部插入一个元素。
emplace_front()	在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。
pop_front()	删除容器头部的一个元素。
emplace_after()	在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。和 insert_after() 的功能相同，但效率更高。
insert_after()	在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。
erase_after()	删除容器中某个指定位置或区域内的所有元素。
swap()	交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。
resize()	调整容器的大小。
clear()	删除容器存储的所有元素。
splice_after()	将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后。
remove(val)	删除容器中所有等于 val 的元素。
remove_if()	删除容器中满足条件的元素。
unique()	删除容器中相邻的重复元素，只保留一个。
merge()	合并两个事先已排好序的 forward_list 容器，并且合并之后的 forward_list 容器依然是有序的。
sort()	通过更改容器中元素的位置，将它们进行排序。
reverse()	反转容器中元素的顺序

如上，forward_list容器迭代器的移动除了使用++运算符单步移动之外，还能使用advance()函数：

#include <iostream>
#include <forward_list>
using namespace std;
int main()
{
    forward_list<int> values{1,2,3,4};
    auto it = values.begin();
    advance(it, 2);
    while (it!=values.end())
    {
        cout << *it << " ";
        ++it;
    }
    return 0;
}

并且，在forward_list容器中是没有提供size（）函数的，想要获取forward_list容器中的存储元素的个数，可以使用头文件< iterator >中的distance（）函数

#include <iostream>
#include <forward_list>
#include <iterator>
using namespace std;
int main()
{
    forward_list<int> my_words{1,2,3,4};
    int count = distance(begin(my_words),end(my_words));
    cout << count;
    return 0;
}

总结

• 定义方式
• list的迭代器
• 访问元素
• 添删元素

• list<数据类型> 容器名：创建空list容器
• list<数据类型> 容器名(n, a)：创建包含n个元素，初值为a的容器（a可省略）
• list<数据类型> 容器名(另一个容器名)：拷贝另一个容器创建list
• list<数据类型> 容器名(begin迭代器, end迭代器)：拷贝区间内元素创建list

• begin（）/end（）：返回“开头/结尾+1”处的元素的正向迭代器
• 前加r：返回“开头-1/结尾”的反向迭代器——rbegin（）/rend（）
• 前加c：返回const类型的元素迭代器——cbegin()/cend(),crbegin()/crend()
• 不能通过下标访问 list 容器中指定位置处的元素
• 不支持使用 -=、+=、+、- 运算符
• 不支持使用 <、 >、 <=、 >= 比较运算符

• front（）和back（）函数——返回容器中第一个和最后一个元素的引用
• 因为存储空间不连续不能使用指针，而只能使用list的迭代器访问

添加元素：

• push_front()：向 list 容器首个元素前添加新元素
• push_back()：向 list 容器最后一个元素后添加新元素
• emplace_front()：在容器首个元素前直接生成新的元素
• emplace_back()：在容器最后一个元素后直接生成新的元素
• emplace()：在容器的指定位置直接生成新的元素
• insert()：在指定位置插入新元素
• splice()：将其他 list 容器存储的多个元素剪切到当前 list 容器的指定位置处

删除元素：

• pop_front() 删除位于 list 容器头部的一个元素

• pop_back() 删除位于 list 容器尾部的一个元素

• erase() 该成员函数既可以删除 list 容器中指定位置处的元素，也可以删除容器中某个区域内的多个元素

• clear() 删除 list 容器存储的所有元素

• remove(val) 删除容器中所有等于 val 的元素

• remove_if() 删除容器中满足条件的元素

• unique() 删除容器中相邻的重复元素，只保留一份，可以直接无参使用，也可以自定义传入一个二元谓词函数

代码实例

#include <iostream>
#include <list>
using namespace std;
int main()
{
    //创建空的 list 容器
    std::list<double> values;
    //向容器中添加元素
    values.push_back(3.1);
    values.push_back(2.2);
    values.push_back(2.9);
    cout << "values size：" << values.size() << endl;
    //对容器中的元素进行排序
    values.sort();
    //使用迭代器输出list容器中的元素
    for (std::list<double>::iterator it = values.begin(); it != values.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

输出结果为：

values size：3
2.2 2.9 3.1

#include <iostream>
#include <list>
using namespace std;
int main()
{
    //创建 list 容器
    std::list<char> values{'h','t','t','p',':','/','/','c','.','b','i','a','n','c','h','e','n','g','.','n','e','t'};
    //使用begin()/end()迭代器函数对输出list容器中的元素
    for (std::list<char>::iterator it = values.begin(); it != values.end(); ++it) {
        std::cout << *it;
    }
    cout << endl;
    //使用 rbegin()/rend()迭代器函数输出 lsit 容器中的元素
    for (std::list<char>::reverse_iterator it = values.rbegin(); it != values.rend();++it) {
        std::cout << *it;
    }
    return 0;
}

输出结果为：

http://c.biancheng.net
ten.gnehcnaib.c//:ptth

#include <iostream>
#include <list>
using namespace std;
int main()
{
    //创建并初始化 2 个 list 容器
    list<int> mylist1{ 1,2,3,4 }, mylist2{10,20,30};
    list<int>::iterator it = ++mylist1.begin(); //指向 mylist1 容器中的元素 2
   
    //调用第一种语法格式
    mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                 // mylist2:
                                 // it 迭代器仍然指向元素 2，只不过容器变为了 mylist1
    //调用第二种语法格式，将 it 指向的元素 2 移动到 mylist2.begin() 位置处
    mylist2.splice(mylist2.begin(), mylist1, it);   // mylist1: 1 10 20 30 3 4
                                                    // mylist2: 2
                                                    // it 仍然指向元素 2
   
    //调用第三种语法格式，将 [mylist1.begin(),mylist1.end())范围内的元素移动到 mylist.begin() 位置处                  
    mylist2.splice(mylist2.begin(), mylist1, mylist1.begin(), mylist1.end());//mylist1:
                                                                             //mylist2:1 10 20 30 3 4 2
   
    cout << "mylist1 包含 " << mylist1.size() << "个元素" << endl;
    cout << "mylist2 包含 " << mylist2.size() << "个元素" << endl;
    //输出 mylist2 容器中存储的数据
    cout << "mylist2:";
    for (auto iter = mylist2.begin(); iter != mylist2.end(); ++iter) {
        cout << *iter << " ";
    }
    return 0;
}

输出结果为：

mylist1 包含 0个元素
mylist2 包含 7个元素
mylist2:1 10 20 30 3 4 2