带你深入理解STL之List容器
vector和数组类似，它拥有一段连续的内存空间，并且起始地址不变，很好的支持了随机存取，但由于是连续空间，所以在中间进行插入、删除等操作时都造成了内存块的拷贝和移动，另外在内存空间不足时还需要重新申请一块大内存来进行内存的拷贝。为了克服这些缺陷，STL定义了另一种容器List，它对于数据插入和删除的时间复杂度均为O(1)，而且再内存方面不用频繁的拷贝转移。下面，就一起来看看List的实现吧！
List和Vector都是STL的序列式容器，唯一不同的地方就在于：Vector是一段连续的内存空间，List则是一段不连续的内存空间，相比于Vector来说，List在每次插入和删除的时候，只需要配置或释放一个元素空间，对于任何位置的插入和删除操作，List永远能做到常数时间。但是，List由于不连续的内存空间，导致不支持随机寻址，所以尺有所长寸有所短，在程序中选择使用那种容器还要视元素的构造复杂度和存取行为而定。
List的节点
List的节点结构如下：
struct __list_node
typedef void* void_
//型别为void*，也可以设为__list_node*
从节点结构可以看出，List就是一个双向链表，其结构如下图所示：
&vcD4NCjxoMSBpZD0="list的迭代器">List的迭代器
在Vector中，由于是连续的存储空间，支持随机存取，所以其迭代器可以直接用普通指针代替。但是，在List中行不通。List必须有能力指向List的节点，并有能力进行正确的递增、递减、取值和成员存取等操作。
List是一个双向链表，迭代器必须具备前移、后退的能力，所以List的迭代器是一个Bidirectional Iterator！在Vector中如果进行插入和删除操作后迭代器会失效，List有一个重要的性质就是插入和接合操作都不会造成原有的List迭代器失效。而且，再删除一个节点时，也仅有指向被删除元素的那个迭代器失效，其他迭代器不受任何影响。下面来看看List迭代器的源码。
struct __list_iterator
typedef __list_iterator
// 支持Iterator_traits
typedef __list_iterator const_
typedef __list_iterator
// 以下为支持Iterator_traits而定义的一些类型
typedef bidirectional_iterator_tag iterator_ //List的迭代器类型为双向迭代器
typedef T value_
typedef size_t size_
typedef ptrdiff_t difference_
typedef __list_node* link_
// 这个是迭代器实际管理的资源指针
// 迭代器构造函数
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
// 在STL算法中需要迭代器提供支持
bool operator==(const self& x) const { return node == x. }
bool operator!=(const self& x) const { return node != x. }
// 重载operator *, 返回实际维护的数据
reference operator*() const { return (*node). }
// 成员调用操作符
pointer operator-&() const { return &(operator*()); }
// 前缀自加
self& operator++()
node = (link_type)((*node).next);
// 后缀自加, 需要先产生自身的一个副本, 然会再对自身操作, 最后返回副本
self operator++(int)
self tmp = *
self& operator--()
node = (link_type)((*node).prev);
self operator--(int)
self tmp = *
List的迭代器实现了==,!=,++,&,取值和成员调用等操作，由于是存放在不连续的内存空间，所以并不支持vector那样的p+n的操作。
List的数据结构
List的数据结构个List的节点数据结构是分开定义的，SGI的List不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针，就能完整表现一个链表。
class list
protected:
typedef void* void_
typedef __list_node list_
// 这个提供STL标准的allocator接口
typedef simple_alloc list_node_
// 链表的头结点，并不存放数据
//....以下还有一堆List的操作函数
List构造函数
List提供了一个空构造函数，如下：
list() { empty_initialize(); }
// 用于空链表的建立
void empty_initialize()
node = get_node();
node-&next =
// 前置节点指向自己
node-&prev =
// 后置节点指向自己
另外，List还提供了带参的构造函数，支持如下初始化操作：
List myList(5,1); // 初始化5个1的链表，{1,1,1,1,1}
其构造函数源码如下：
// 带参构造函数
list(size_type n, const T& value) { fill_initialize(n, value); }
// 创建值为value共n个结点的链表
void fill_initialize(size_type n, const T& value)
empty_initialize();
// 先创建一个空链表
insert(begin(), n, value); // 插入n个值为value的节点
// 在指定位置插入n个值为x的节点
void insert(iterator pos, int n, const T& x)
insert(pos, (size_type)n, x);
// 在position前插入n个值为x的元素
void list::insert(iterator position, size_type n, const T& x)
for ( ; n & 0; --n)
insert(position, x);
// 好吧，到这里才是真正的插入操作
// 很简单的双向链表插入操作
iterator insert(iterator position, const T& x)
link_type tmp = create_node(x);
tmp-&next = position.
tmp-&prev = position.node-&
(link_type(position.node-&prev))-&next =
position.node-&prev =
STL的List提供了很多种构造函数，此处我列举了其中一个，以此为例。
List的其他操作函数
此函数用来配置一个节点。
// 配置一个节点并返回
link_type get_node() {
return list_node_allocator::allocate();
此函数用来释放一个节点。
// 释放指定结点, 不进行析构, 析构交给全局的destroy,
void put_node(link_type p) {
list_node_allocator::deallocate(p);
create_node
此函数用来配置并构造一个节点，并初始化其值
// 配置一个节点，并初始化其值为x
link_type create_node(const T& x)
link_type p = get_node();
construct(&p-&data, x);
//全局函数
destory_node
此函数用来析构一个节点。
// 析构结点元素, 并释放内存
void destroy_node(link_type p)
destroy(&p-&data);
//全局函数
put_node(p);
此函数用来在制定位置插入一个节点(上面提到过这个函数，这里重复一下，List的主要插入工作都交给这个函数)，该函数是一个重载函数，其有多种形式。
// 好吧，到这里才是真正的插入操作
// 很简单的双向链表插入操作
iterator insert(iterator position, const T& x)
link_type tmp = create_node(x);
tmp-&next = position.
tmp-&prev = position.node-&
(link_type(position.node-&prev))-&next =
position.node-&prev =
// 其还有如下多种形式的重载函数
// 在[first,last]区间内插入元素
void list::insert(iterator position,
InputIterator first, InputIterator last)
for ( ; first != ++first)
insert(position, *first);
// 在position位置插入元素，元素调用该型别默认构造函数
iterator insert(iterator position) { return insert(position, T()); }
在尾部插入元素，有了上面的insert函数之后，push_back就比较容易实现了。
// 在链表最后插入结点
void push_back(const T& x) { insert(end(), x); }
// 在链表前端插入结点
void push_front(const T& x) { insert(begin(), x); }
移除迭代器所指的元素
// 擦除指定结点
iterator erase(iterator position)
// 双向链表移除节点的操作
link_type next_node = link_type(position.node-&next);
link_type prev_node = link_type(position.node-&prev);
prev_node-&next = next_
next_node-&prev = prev_
destroy_node(position.node);
return iterator(next_node);
// 上述函数还有一个重载版本，移除区间内所有的节点
// 擦除[first, last)间的结点
list::iterator list::erase(iterator first, iterator last)
while (first != last) erase(first++);
移除头节点元素，有了上述的erase函数，就很方便的实现了。
// 删除链表第一个结点
void pop_front() { erase(begin()); }
移除链表中最后一个元素
// 删除链表最后一个结点
void pop_back()
iterator tmp = end();
erase(--tmp);
清除链表中的所有节点，也就是一个一个的清除
// 销毁所有结点, 将链表置空
void list::clear()
link_type cur = (link_type) node-&
while (cur != node) { //遍历每一个节点
link_type tmp =
cur = (link_type) cur-&
destroy_node(tmp);
node-&next =// 移除后注意要保持链表是一个循环链表
node-&prev =
将链表中值为value的节点移除
// 移除特定值的所有结点
// 时间复杂度O(n)
void list::remove(const T& value)
iterator first = begin();
iterator last = end();
while (first != last) { //保证链表非空
iterator next =
if (*first == value) erase(first);
//擦除该节点
将某段连续范围内的元素迁移到指定位置。（非公开接口）
void transfer(iterator position, iterator first, iterator last)
if (position != last)
(*(link_type((*last.node).prev))).next = position.
(*(link_type((*first.node).prev))).next = last.
(*(link_type((*position.node).prev))).next = first.
link_type tmp = link_type((*position.node).prev);
(*position.node).prev = (*last.node).
(*last.node).prev = (*first.node).
(*first.node).prev =
这里借用侯捷先生的《STL源码剖析》中的一幅图来说明这个过程。
List提供的接合函数是Splice，上述transfer是非公开的函数。splice函数有如下几个版本:
// 将链表x移动到position之前
void splice(iterator position, list& x)
if (!x.empty())
transfer(position, x.begin(), x.end()); //仅仅调用了transfer函数
// 将链表中i指向的内容移动到position之前
void splice(iterator position, list&, iterator i)
iterator j =
if (position == i || position == j)
transfer(position, i, j);
// 将[first, last}元素移动到position之前
void splice(iterator position, list&, iterator first, iterator last)
if (first != last)
transfer(position, first, last);
此函数用来合并两个链表，这里两个链表必须是已拍好序的。
// 假设当前容器和x都已序, 保证两容器合并后仍然有序
void list::merge(list& x)
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
while (first1 != last1 && first2 != last2)
if (*first2 & *first1) {
iterator next = first2;
transfer(first1, first2, ++next); //将first2节点迁移到first1之后
if (first2 != last2) transfer(last1, first2, last2);
//如果first2还有剩余的，直接接合再链表1尾部
此函数用来反转链表，其具体实现如下：
// 将链表倒置
void list::reverse()
if (node-&next == node || link_type(node-&next)-&next == node)
iterator first = begin();
while (first != end()) {
iterator old =
// 取出一个节点
transfer(begin(), old, first);
// 插入到begin()之后
此函数对链表进行升序排序，具体实现如下：
// 按照升序排序
void list::sort()
if (node-&next == node || link_type(node-&next)-&next == node)
list counter[64];
int fill = 0;
while (!empty()) {
// 从链表中取出一个节点
carry.splice(carry.begin(), *this, begin());
int i = 0;
// 把carry中的新元素和counter中的结果逐一进行归并
while (i & fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
// 把归并后的结果存放在counter[i]中
carry.swap(counter[i]);
// 已经达到2*fill，fill自增1
if (i == fill) ++
// 将counter中的所有元素进行归并
for (int i = 1; i & ++i) counter[i].merge(counter[i - 1]);
// 将counter链表和本链表进行交换
swap(counter[fill - 1]);
// 交换本链表和链表x
void swap(list& x) {
swap(node, x.node);
这里可以举个例子来说明一下这个过程：(以链表5,3,6,4,7,9,1,2,8)
carry每次从数组中取一个数，然后归并到counter数组中，该算法最多只能排序2的64次方个数。
《STL源码剖析》中写到此处是快速排序，其实我觉得应该是归并排序。
list链表中提供了很多操作函数，看完源码感觉自己重新复习了一遍数据结构里的常用链表操作，同时也掌握了STL链表的常用函数。受益匪浅！！另外，sort不知道是侯捷先生的笔误还是什么，怎么看都不像是快速排序啊。最后，大家有什么疑惑可以再下方留言。
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'关于STL中list容器的一些总结
字体：[ ] 类型：转载 时间：
list就是数据结构中的双向链表(根据sgi stl源代码)，因此它的内存空间是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它没有提供[]操作符的重载
1.关于list容器
list是一种序列式容器。list容器完成的功能实际上和数据结构中的双向链表是极其相似的，list中的数据元素是通过链表指针串连成逻辑意义上的线性表，也就是list也具有链表的主要优点，即：在链表的任一位置进行元素的插入、删除操作都是快速的。list的实现大概是这样的：list的每个节点有三个域：前驱元素指针域、数据域和后继元素指针域。前驱元素指针域保存了前驱元素的首地址；数据域则是本节点的数据；后继元素指针域则保存了后继元素的首地址。其实，list和循环链表也有相似的地方，即：头节点的前驱元素指针域保存的是链表中尾元素的首地址，list的尾节点的后继元素指针域则保存了头节点的首地址，这样，list实际上就构成了一个双向循环链。由于list元素节点并不要求在一段连续的内存中，显然在list中是不支持快速随机存取的，因此对于迭代器，只能通过“++”或“--”操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作，这点，是与vector等不同的地方。
我想把三个常用的序列式放在一起对比一下是有必要的：
vector ：vector和built-in数组类似，拥有一段连续的内存空间，能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当插入较多的元素后，预留内存空间可能不够，需要重新申请一块足够大的内存并把原来的数据拷贝到新的内存空间。这些影响了vector的效率，但是实际上用的最多的还是vector容器，建议大多数时候使用vector效率一般是不错的。list：list就是数据结构中的双向链表(根据sgi stl源代码)，因此它的内存空间是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。
deque：deque是一个double-ended queue，它的具体实现不太清楚，但知道它具有以下两个特点：它支持[]操作符，也就是支持随即存取，并且和vector的效率相差无几，它支持在两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多。
因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，具体可以遵循下面的原则：1. 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector2. 如果你需要大量的插入和删除，而不关心随即存取，则应使用list3. 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。
2.list中常用的函数
2.1 list中的构造函数：
list() 声明一个空列表；
list(n) 声明一个有n个元素的列表，每个元素都是由其默认构造函数T()构造出来的
list(n,val) 声明一个由n个元素的列表，每个元素都是由其复制构造函数T(val)得来的
list(n,val) 声明一个和上面一样的列表
list(first,last) 声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素
--------------------------------------------------------------------------------
2.2 begin()和end()：通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator，可以调用list容器的 end() 函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。
--------------------------------------------------------------------------------
2.3 push_back() 和push_front()：使用list的成员函数push_back和push_front插入一个元素到list中。其中push_back()从list的末端插入，而 push_front()实现的从list的头部插入。
--------------------------------------------------------------------------------
2.4 empty()：利用empty() 判断list是否为空。
--------------------------------------------------------------------------------
2.5 resize()： 如果调用resize(n)将list的长度改为只容纳n个元素，超出的元素将被删除，如果需要扩展那么调用默认构造函数T()将元素加到list末端。如果调用resize(n,val)，则扩展元素要调用构造函数T(val)函数进行元素构造，其余部分相同。
--------------------------------------------------------------------------------
2.6 clear()： 清空list中的所有元素。
--------------------------------------------------------------------------------
2.7 front()和back()： 通过front()可以获得list容器中的头部元素，通过back()可以获得list容器的最后一个元素。但是有一点要注意，就是list中元素是空的时候，这时候调用front()和back()会发生什么呢？实际上会发生不能正常读取数据的情况，但是这并不报错，那我们编程序时就要注意了，个人觉得在使用之前最好先调用empty()函数判断list是否为空。
--------------------------------------------------------------------------------
2.8 pop_back和pop_front()：通过删除最后一个元素，通过pop_front()删除第一个元素；序列必须不为空，如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。
--------------------------------------------------------------------------------
2.9 assign()：具体和vector中的操作类似，也是有两种情况，第一种是：l1.assign(n,val)将 l1中元素变为n个T(val）。第二种情况是：l1.assign(l2.begin(),l2.end())将l2中的从l2.begin()到l2.end()之间的数值赋值给l1。
--------------------------------------------------------------------------------
2.10 swap()：交换两个链表(两个重载)，一个是l1.swap(l2); 另外一个是swap(l1,l2)，都可能完成连个链表的交换。
--------------------------------------------------------------------------------
2.11 reverse()：通过reverse()完成list的逆置。
--------------------------------------------------------------------------------
2.12 merge()：合并两个链表并使之默认升序(也可改)，l1.merge(l2，greater&int&()); 调用结束后l2变为空，l1中元素包含原来l1 和 l2中的元素，并且排好序，升序。其实默认是升序，greater&int&()可以省略，另外greater&int&()是可以变的，也可以不按升序排列。
看一下下面的程序： 代码如下:#include &iostream&#include &list&
int main(){&&& list&int& l1;&&& list&int& l2(2,0);&&& list&int&::&&& l1.push_back(1);&&& l1.push_back(2);&&& l2.push_back(3);&&& l1.merge(l2,greater&int&());//合并后升序排列，实际上默认就是升序&&& for(iter = l1.begin() ; iter != l1.end() ; iter++)&&& {&&&&&&& cout&&*iter&&" ";&&& }&&& cout&&endl&&&&& if(l2.empty())&&& {&&&&&&& cout&&"l2 变为空 ！！";&&& }&&& cout&&endl&&&&& return 0;}运行结果：
2.13 insert()：在指定位置插入一个或多个元素(三个重载)：
l1.insert(l1.begin(),100); 在l1的开始位置插入100。
l1.insert(l1.begin(),2,200); 在l1的开始位置插入2个100。
l1.insert(l1.begin(),l2.begin(),l2.end());在l1的开始位置插入l2的从开始到结束的所有位置的元素。
--------------------------------------------------------------------------------
2.14 erase()：删除一个元素或一个区域的元素(两个重载)
l1.erase(l1.begin()); 将l1的第一个元素删除。
l1.erase(l1.begin(),l1.end()); 将l1的从begin()到end()之间的元素删除。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具21837人阅读
C/C++（20）
使用标准的std::list进行容器数据处理时，操作比较底层。我们可以，减少引用标准MFC标准库，减少系统的大小，但同时也存在有不方便的操作之处，这里同大家分享一些使用心得......
&&&&&&在使用std::list&&链表时，难免会对数据进行添加删除操作。而遍历链表则有两种方式：通过索引访问，象数组一样处理；通过std::list&&::iterator链表遍历器进行访问
STL&中的list&就是一&双向链表，可高效地进行插入删除元素。
list不支持随机访问。所以没有 at(pos)和operator[]。
list&对象list1,
list2&分别有元素list1(1,2,3),list2(4,5,6)&。list&&int&::iterator
constructor
destructor
赋值重载运算符
分配值
返回第一个元素的引用
返回最后一元素的引用
返回第一个元素的指针(iterator)
返回最后一个元素的下一位置的指针
返回链表最后一元素的后向指针(reverse_iterator or const)
返回链表第一元素的下一位置的后向指针
增加一元素到链表尾
push_front
增加一元素到链表头
pop_back()删除链表尾的一个元素
删除链表头的一元素
删除所有元素
删除一个元素或一个区域的元素(两个重载)
删除链表中匹配值的元素(匹配元素全部删除)
删除条件满足的元素(遍历一次链表)，参数为自定义的回调函数
判断是否链表为空
返回链表最大可能长度
返回链表中元素个数
重新定义链表长度(两重载函数)
对链表排序，默认升序
合并两个有序链表并使之有序
对两个链表进行结合(三个重载函数)&结合后第二个链表清空
在指定位置插入一个或多个元素(三个重载函数)
交换两个链表(两个重载)
删除相邻重复元素&
1.list&构造函数
list&&int&&&L0&;&&&&&&&&//&空链表
list&&int&&&L1&(9);&&&&//&建一个含个默认值是的元素的链表
list&&int&&&L2&(5,1);&//&建一个含个元素的链表，值都是
list&&int&&&L3&(L2&);&&//&建一个L&2&的&copy&链表
list&&int&&&L4&(L0&.begin&(),&L0&.end&());//&建一个含&L0&一个区域的元素
2. assign()&分配值，有两个重载
L1.&assign&(&4,3);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//
L1(3,3,3,3)
L1.&assign(&++list1.beging(),
list2.end());&&&//&L&1(2,3)
3&．&operator=&赋值重载运算符
L1 = list1;&&&//&L1&(1,2,3)
4.&front()&返回第一个元素的引用
= list1.front()&&&&// nRet = 1
5.&&&back()&返回最后一&元素的引用
= list1.back()&&&&&// nRet = 3
6.&&&begin()&返回第一个元素的指针(iterator)
list1.begin();&&&&// *it = 1
7.&&&&&end()&返回最后一个元素的&下一位置&的指针(list&为空时end()=begin())
list1.end();
--&&&&&&&&&&&&&&&&&&&&&&&//
8.rbegin()&返回链表最后一&元素的后向指针(reverse_iterator
list&&int&&::reverse_iterator&it&=&list1&.rbegin&();&&//
9.&&&&&&rend()&返回链表第一元素的&下一位置&的后向指针
list&&int&::reverse_iterator
it =&list1&.rend();
// *(--riter) = 1
10.push_back()&增加一&元素到链表尾
list1.push_back(&4)&&&&&&&//
list1(1,2,3,&4&)
11.&&&push_front()&增加一&元素到链表头
list1.push_front(&4)&&&&&&//
list1(&4&,1,2,3)
12.&&&pop_back()&删除链表尾的一个元素
list1.pop_back(&)&&&&&&&&&&//
list1(1,2)
13.pop_front()&删除链表头&的一&元素
list1.pop_front()&　&&&&&&&&&//
list1(2,3)
14&．clear()&删除所有元素
list1.clear();&&&// list1&空了,list1.size()
15.erase()&删除&一个元素&或&一个区域的元素&(&两个重载函数)
list1.erase(&list1.begin());&&&&&&&&&&&&&&&&//
list1(2,3)
list1.erase(&++list1.begin(),list1.end());
// list1(1)
16.&&&&&&&remove()&删除链表中匹配值&的元素(&匹配元素全部删除)
list&对象L1(&4&,3,5,1,&4&)
L1.remove(&4);&&&&&&&&&&&&&&&//
L1(3,5,1);
17.remove_if()&删除条件满足的元素(&遍历一次链表)&，参数为自定义的回调函数
//&小于2&的值删除
bool&myFun&(const&int&&&value&)
{&return&(value&& 2); }
list1.remove_if(&myFun&);&&&&//
list1(3)&　
18.empty()&判断是否链表为空
bool bRet = L1.empty(); //&若L1&为空，bRet
= true&，否则bRet = false&。
19.max_size()&返回链表最大可能长度
list&&int&&::size_type&nMax&=&list1&.max_size&();//&nMax&=&
20&．size()&返回链表中元素个数
list&&int&::size_type
nRet = list1.size();&&&&&&// nRet = 3
21.resize()&重新定义链表长度(&两重载函数)
list1.resize(5)&&&&// list1 (1,2,3,&0,0&)&用默认值填补
list1.resize(5,4)&&&&// list1 (1,2,3,&4,4&)&用指定值&填补
22.reverse()&反转链表:
list1.reverse(&);&&&&&//
list1(3,2,1)
23.sort()&对链表排序，默认升序(&可自定义回调函数&)
list&对象L1(4,3,5,1,4)
L1.sort(&);&&&&&&&&&&&&&&&&&//
L1(1,3,4,4,5)
L1.sort(&greater&&int&&()&);
// L1(5,4,4,3,1)
24.merge()&合并两个有序链表并使之有序
list1.merge(list2);&&&&&&&&&&//
list1(1,2,3,4,5,6) list2&现为空
L1(&3,2,1),
L1.merge(L2,&greater&&int&&()&);
// list1(6,5,4,3,2,1) list2&现为空
25.splice()&对两个链表进行结合(&三个重载函数)&结合后第二个链表清空
list1.splice(&++list1.begin(),list2);&
// list1(1,4,5,6,2,3) list2&为空
&&list1.splice(&++list1.begin(),list2,list2.begin());
//&list1(&1,4,2,3); list2(5,6)
list1.splice(&++list1.begin(),list2,++list2.begin(),list2.end());
//list1(&1,&5,6,&2,3);
26.insert()&在指定位置插入一个或多个元素(&三个重载函数)
list1.insert(&++list1.begin(),9);&&//
list1(1,9,2,3)
list1.insert(list1.begin(),2,9);&&// list1(9,9,1,2,3);
list1.insert(list1.begin(),list2.begin(),--list2.end());//list1(4,5,1,2,3);
27.swap()&交换两个链表(&两个重载)
list1.swap(list2);&&&// list1&（4&，5&，6&）&list2&（1&，2&，3&）
28.&&&unique()&删除相邻重复元素
L1(&1,&1&,4,3,5,1)
L1.unique(&);&&&&&&&&&//
L1(1,4,3,5,1)
bool&same_integral_part&(double&first&,&double&second&)
{&return&(&int&(first&)==int&(second&)
L1.unique(&same_integral_part&);
//&-------------------------------------------------------------------------
//&文件名 : list1.cpp
//&创建者 : 方煜宽
//&　邮箱 ：
//&创建时间 :
//&功能描述 : STL中的list就是一双向链表，可高效地进行插入删除元素。
//&-------------------------------------------------------------------------&
#include&&&stdafx.h&&&
#include&&&iostream&&&
#include&&&list&&&
using&namespace&
list&&&int&&&g_list1;
list&&&int&&&g_list2;
////////////////////////////////////////////////////////////////////////&//&
//&初始化全局链表&
void&InitList()
//&push_back()增加一元素到链表尾&
g_list1.push_back(&1&);
g_list1.push_back(&2&);
g_list1.push_back(&3&);
//&push_front()增加一元素到链表头&
g_list2.push_front(&6&);
g_list2.push_front(&5&);
g_list2.push_front(&4&);
//&输出一个链表&
void&ShowList(list&&&int&&&&listTemp)
//&size()返回链表中元素个数&
cout&&&&listTemp.size()&&&&
for&(list&&&int&&&::iterator
it&=&listTemp.begin(); it&!=&listTemp.end();&++&it)
cout&&&&*&it&&&&'&'&;
////////////////////////////////////////////////////////////////////////&//&
//&构造函数，空链表&
void&constructor_test0()
list&&&int&&&listT
cout&&&&listTemp.size()&&&&
//&构造函数，建一个含三个默认值是0的元素的链表&
void&constructor_test1()
list&&&int&&&listTemp(&3&);
ShowList(listTemp);
//&构造函数，建一个含五个元素的链表，值都是1&
void&constructor_test2()
list&&&int&&&listTemp(&5&,&1&);
ShowList(listTemp);
//&构造函数，建一个g_list1的copy链表&
void&constructor_test3()
list&&&int&&&listTemp(g_list1);
ShowList(listTemp);
//&构造函数，listTemp含g_list1一个区域的元素[_First, _Last)&
void&constructor_test4()
list&&&int&&&listTemp(g_list1.begin(),
g_list1.end());
ShowList(listTemp);
//&assign()分配值，有两个重载
//&template &class InputIterator&
//&void assign ( InputIterator first, InputIterator last );
//&void assign ( size_type n, const T& u );&
void&assign_test()
list&&&int&&&listTemp(&5&,&1&);
ShowList(listTemp);
listTemp.assign(&4&,&3&);
ShowList(listTemp);
listTemp.assign(&++&g_list1.begin(), g_list1.end());
ShowList(listTemp);
//&operator=&
void&operator_equality_test()
g_list1&=&g_list2;
ShowList(g_list1);
ShowList(g_list2);
//&front()返回第一个元素的引用&
void&front_test7()
cout&&&&g_list1.front()&&&&
//&back()返回最后一元素的引用&
void&back_test()
cout&&&&g_list1.back()&&&&
//&begin()返回第一个元素的指针(iterator)&
void&begin_test()
list&&&int&&&::iterator
it1&=&g_list1.begin();
cout&&&&*++&it1&&&&
list&&&int&&&::const_iterator
it2&=&g_list1.begin();
it2&++&;
//&(*it2)++;&//&*it2
为const 不用修改&
cout&&&&*&it2&&&&
//&end()返回 [最后一个元素的下一位置的指针] (list为空时end()= begin())&
void&end_test()
list&&&int&&&::iterator
it&=&g_list1.end();&//&注意是：最后一个元素的下一位置的指针&
cout&&&&*&it&&&&
//&rbegin()返回链表最后一元素的后向指针&
void&rbegin_test()
list&&&int&&&::reverse_iterator
it&=&g_list1.rbegin();
for&(; it&!=&g_list1.rend();&++&it)
cout&&&&*&it&&&&'&'&;
//&rend()返回链表第一元素的下一位置的后向指针&
void&rend_test()
list&&&int&&&::reverse_iterator
it&=&g_list1.rend();
cout&&&&*&it&&&&
//&push_back()增加一元素到链表尾&
void&push_back_test()
ShowList(g_list1);
g_list1.push_back(&4&);
ShowList(g_list1);
//&push_front()增加一元素到链表头&
void&push_front_test()
ShowList(g_list1);
g_list1.push_front(&4&);
ShowList(g_list1);
//&pop_back()删除链表尾的一个元素&
void&pop_back_test()
ShowList(g_list1);
g_list1.pop_back();
ShowList(g_list1);
//&pop_front()删除链表头的一元素&
void&pop_front_test()
ShowList(g_list1);
g_list1.pop_front();
ShowList(g_list1);
//&clear()删除所有元素&
void&clear_test()
ShowList(g_list1);
g_list1.clear();
ShowList(g_list1);
//&erase()删除一个元素或一个区域的元素(两个重载函数)&
void&erase_test()
ShowList(g_list1);
g_list1.erase(g_list1.begin());
ShowList(g_list1);
ShowList(g_list2);
g_list2.erase(&++&g_list2.begin(), g_list2.end());
ShowList(g_list2);
//&remove()删除链表中匹配值的元素(匹配元素全部删除)&
void&remove_test()
ShowList(g_list1);
g_list1.push_back(&1&);
ShowList(g_list1);
g_list1.remove(&1&);
ShowList(g_list1);
bool&myFun(&const&int&&&value)
{&return&(value&&&2&);
//&remove_if()删除条件满足的元素(会遍历一次链表)&
void&remove_if_test()
ShowList(g_list1);
g_list1.remove_if(myFun);
ShowList(g_list1);
//&empty()判断是否链表为空&
void&empty_test()
list&&&int&&&listT
if&(listTemp.empty())
cout&&&&&&listTemp为空&&&&&&
cout&&&&&&listTemp不为空&&&&&&
//&max_size()返回链表最大可能长度:&
void&max_size_test()
list&&&int&&&::size_type
nMax&=&g_list1.max_size();
cout&&&&nMax&&&&
//&resize()重新定义链表长度(两重载函数)：&
void&resize_test()
ShowList(g_list1);
g_list1.resize(&9&);&//&用默认值填补&
ShowList(g_list1);
ShowList(g_list2);
g_list2.resize(&9&,&51&);&//&用指定值填补&
ShowList(g_list2);
//&reverse()反转链表&
void&reverse_test()
ShowList(g_list1);
g_list1.reverse();
ShowList(g_list1);
//&sort()对链表排序，默认升序(两个重载函数)&
void&sort_test()
list&&&int&&&listT
listTemp.push_back(&9&);
listTemp.push_back(&3&);
listTemp.push_back(&5&);
listTemp.push_back(&1&);
listTemp.push_back(&4&);
listTemp.push_back(&3&);
ShowList(listTemp);
listTemp.sort();
ShowList(listTemp);
listTemp.sort(greater&&&int&&&());
ShowList(listTemp);
//&merge()合并两个升序序链表并使之成为另一个升序.&
void&merge_test1()
list&&&int&&&listTemp2;
listTemp2.push_back(&3&);
listTemp2.push_back(&4&);
list&&&int&&&listTemp3;
listTemp3.push_back(&9&);
listTemp3.push_back(&10&);
ShowList(listTemp2);
ShowList(listTemp3);
listTemp2.merge(listTemp3);
ShowList(listTemp2);
bool&myCmp (&int&first,&int&second)
{&return&(&int&(first)&&&int&(second)
//&merge()合并两个降序链表并使之成为另一个降序.&
void&merge_test2()
list&&&int&&&listTemp2;
listTemp2.push_back(&4&);
listTemp2.push_back(&3&);
list&&&int&&&listTemp3;
listTemp3.push_back(&10&);
listTemp3.push_back(&9&);
ShowList(listTemp2);
ShowList(listTemp3);
//&listTemp2.merge(listTemp3, greater&int&());&//&第二个参数可以是自己定义的函数如下&
listTemp2.merge(listTemp3, myCmp);
ShowList(listTemp2);
//&splice()对两个链表进行结合(三个重载函数),结合后第二个链表清空
//&void splice ( iterator position, list&T,Allocator&& x );
//&void splice ( iterator position, list&T,Allocator&& x, iterator
//&void splice ( iterator position, list&T,Allocator&& x, iterator
first, iterator last );&
void&splice_test()
list&&&int&&&listTemp1(g_list1);
list&&&int&&&listTemp2(g_list2);
ShowList(listTemp1);
ShowList(listTemp2);
listTemp1.splice(&++&listTemp1.begin(),
listTemp2);
ShowList(listTemp1);
ShowList(listTemp2);
listTemp1.assign(g_list1.begin(), g_list1.end());
listTemp2.assign(g_list2.begin(), g_list2.end());
listTemp1.splice(&++&listTemp1.begin(), listTemp2,&++&listTemp2.begin());
ShowList(listTemp1);
ShowList(listTemp2);
listTemp1.assign(g_list1.begin(), g_list1.end());
listTemp2.assign(g_list2.begin(), g_list2.end());
listTemp1.splice(&++&listTemp1.begin(), listTemp2,&++&listTemp2.begin(),
listTemp2.end());
ShowList(listTemp1);
ShowList(listTemp2);
//&insert()在指定位置插入一个或多个元素(三个重载函数)
//&iterator insert ( iterator position, const T& x );
//&void insert ( iterator position, size_type n, const T& x );
//&template &class InputIterator&
//&void insert ( iterator position, InputIterator first, InputIterator
void&insert_test()
list&&&int&&&listTemp1(g_list1);
ShowList(listTemp1);
listTemp1.insert(listTemp1.begin(),&51&);
ShowList(listTemp1);
list&&&int&&&listTemp2(g_list1);
ShowList(listTemp2);
listTemp2.insert(listTemp2.begin(),&9&,&51&);
ShowList(listTemp2);
list&&&int&&&listTemp3(g_list1);
ShowList(listTemp3);
listTemp3.insert(listTemp3.begin(), g_list2.begin(), g_list2.end());
ShowList(listTemp3);
//&swap()交换两个链表(两个重载)&
void&swap_test()
ShowList(g_list1);
ShowList(g_list2);
g_list1.swap(g_list2);
ShowList(g_list1);
ShowList(g_list2);
bool&same_integral_part (&double&first,&double&second)
{&return&(&int&(first)&==&int&(second)
//&unique()删除相邻重复元素&
void&unique_test()
list&&&int&&&listT
listTemp.push_back(&1&);
listTemp.push_back(&1&);
listTemp.push_back(&4&);
listTemp.push_back(&3&);
listTemp.push_back(&5&);
listTemp.push_back(&1&);
list&&&int&&&listTemp2(listTemp);
ShowList(listTemp);
listTemp.unique();&//&不会删除不相邻的相同元素&
ShowList(listTemp);
listTemp.sort();
ShowList(listTemp);
listTemp.unique();
ShowList(listTemp);
listTemp2.sort();
ShowList(listTemp2);
listTemp2.unique(same_integral_part);
ShowList(listTemp2);
//&主函数，下面要测试哪个就把那个注释去掉即可&
int&_tmain(&int&argc,
_TCHAR&*&argv[])
InitList();
//&ShowList(g_list1);
//&ShowList(g_list2);
//&constructor_test0();
//&constructor_test1();
//&constructor_test2();
//&constructor_test3();
//&constructor_test4();
//&assign_test();
//&operator_equality_test();
//&front_test7();
//&back_test();
//&begin_test();
//&end_test();
//&rbegin_test();
//&rend_test();
//&push_back_test();
//&push_front_test();
//&pop_back_test();
//&pop_front_test();
//&clear_test();
//&erase_test();
//&remove_test();
//&remove_if_test();
//&empty_test();
//&max_size_test();
//&resize_test();
//&reverse_test();
//&sort_test();
//&merge_test1();
//&merge_test2();
//&splice_test();
//&insert_test();
//&swap_test();
//&unique_test();&
return&0&;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：359849次
积分：2900
积分：2900
排名：第10594名
原创：53篇
转载：39篇
评论：53条
(2)(2)(5)(3)(1)(4)(4)(2)(1)(3)(2)(1)(2)(2)(7)(3)(7)(1)(1)(2)(1)(3)(2)(1)(2)(5)(4)(2)(1)(1)(4)(4)(1)(2)(3)(1)}