【C++】List

标签：迭代 1.2 List 元素 list C++ 插入 array

目录

1.1 list的介绍

1.2 list的使用

1.2.1 list的构造

1.2.2 list iterator的使用

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list的迭代器失效

2. list与vector的对比

---

1.1 list的介绍

1.2 list的使用

1.2.1 list的构造

构造函数（ (constructor) ）	接口说明
list (size_type n, const value_type& val = value_type())	构造的 list 中包含 n 个值为 val 的 元素
list()	构造空的 list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用 [first, last) 区间中的元素构造 list

1.2.2 list iterator的使用

函数声 明	接口说明
begin + end	返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的 reverse_iterator, 即 end 位置 ， 返回最后一个元素下一个位 置的 reverse_iterator, 即 begin 位置

【注意】 1. begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动 2. rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动

1.2.3 list capacity

函数声明	接口说明
empty	检测 list 是否为空，是返回 true ，否则返回 false
size	返回 list 中有效节点的个数

1.2.4 list element access

函数声明	接口说明
front	返回 list 的第一个节点中值的引用
back	返回 list 的最后一个节点中值的引用

1.2.5 list modifiers

函数声明	接口说明
push_front	在 list 首元素前插入值为 val 的元素
pop_front	删除 list 中第一个元素
push_back	在 list 尾部插入值为 val 的元素
pop_back	删除 list 中最后一个元素
insert	在 list position 位置中插入值为 val 的元素
erase	删除 list position 位置的元素
swap	交换两个 list 中的元素
clear	清空 list 中的有效元素

1.2.6 list的迭代器失效

迭代器失效即迭代器所指向的节点的无 效，即该节点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ，因此 在 list 中进行插入 时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭 代器，其他迭代器不会受到影响 。

void TestListIterator1()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
        其赋值
        l.erase(it);
        ++it;
    }
}
// 改正
void TestListIterator()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        l.erase(it++); // it = l.erase(it);
    }
}

2. list与vector的对比

vector 与 list 都是 STL 中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及 应用场景不同，其主要不同如下：

	vector	list
底 层 结 构	动态顺序表，一段连续空间	带头结点的双向循环链表
随 机 访 问	支持随机访问，访问某个元素效率 O(1)	不支持随机访问，访问某个元 素效率 O(N)
插 入 和 删 除	任意位置插入和删除效率低，需要搬移元素，时间 复杂度为 O(N) ，插入时有可能需要增容，增容： 开辟新空间，拷贝元素，释放旧空间，导致效率更 低	任意位置插入和删除效率高， 不需要搬移元素，时间复杂度 为 O(1)
空 间 利 用 率	底层为连续空间，不容易造成内存碎片，空间利用 率高，缓存利用率高	底层节点动态开辟，小节点容 易造成内存碎片，空间利用率 低，缓存利用率低
迭 代 器	原生态指针	对原生态指针 ( 节点指针 ) 进行 封装
迭 代 器 失 效	在插入元素时，要给所有的迭代器重新赋值，因为 插入元素有可能会导致重新扩容，致使原来迭代器 失效，删除时，当前迭代器需要重新赋值否则会失 效	插入元素不会导致迭代器失 效，删除元素时，只会导致当 前迭代器失效，其他迭代器不 受影响
使 用 场 景	需要高效存储，支持随机访问，不关心插入删除效 率	大量插入和删除操作，不关心 随机访问

标签：迭代,1.2,List,元素,list,C++,插入,array
From： https://blog.csdn.net/L286594/article/details/144619756