详解list容器

-- TOC --

list容器特点
list容器接口
sort
merge

C++中的list是双向链表结构（doubly linked list）的顺序容器。

list容器特点

参考：https://en.cppreference.com/w/cpp/container/list

双向链表的存储结构，决定了它的特性：

任意位置的访问，都需要\(O(n)\)，fast random access is not supported，不支持快速随机位置访问。
任意位置插入或删除很快，\(O(1)\)，不需要像vector那样移动数据对象。
Adding, removing and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.
list容器没有reserve和capacity接口，我理解内存是按对象数量一个个在插入时申请，在删除时释放的。
list容器比vector容器多了很多对数据任意处理的接口，这是因为list做这些事情，效率很高。

list容器接口

empty
size
clear
//
front    // 第1个对象
back     // 最后1个对象
// iterator
begin
cbegin
rbegin
crbegin
end
cend
rend
crend
//
max_size   // 可能的最大对象数量
//
insert
emplace
erase
push_back
emplace_back
pop_back
push_front
emplace_front
pop_front
resize
swap
assign
//
reverse   // 把list中对象反过来，不管是否有序
sort
merge
unique    // 去掉连续的重复对象
splice    // 拼接两个list容器中的对象
remove
remove_if

sort

在std::sort（https://en.cppreference.com/w/cpp/algorithm/sort）存在的情况下，list容器定义了自己的sort接口，因为前者只能处理可以进行随机位置访问（random access）的容器。

merge

同样std::merge不能用在list上，因此list容器自己定义一个。将两个已经sorted的list容器，合并成一个sorted list。

C++的merge接口，都是处理已排好序的对象。

本文链接：https://cs.pynote.net/sf/c/cpp/202211271/

-- EOF --

-- MORE --