走近STL -- 你好，List

系列目录：走近STL- STL概论

好，闲话不多说，直接上干货。

1、你好，List

从实现层面看，相较于Vector的线性空间，List的实现要复杂的多。
List的优势在于每次插入或删除一个元素，就分配或释放一个位置。因此，List对于空间的把控有绝对的精准。
而且，对于从任何节点增删数据，List消耗的永远是常数时间。

List和Vector的使用应该视元素的多寡、元素的构造复杂度、元素的存取频繁度而定。List优在存取，Vector优在查询。

2、List节点

每一个自己写过链表的人都知道，链表的节点和链表本身是分开设计的。
那我们来看一下List的节点设计：

template <typename T>
struct __list_node
{
	typedef void* void_pointer;
	void_pointer prev;
	void_pointer neet;
	T date;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

显而易见，这是一个通用双向链表的节点（如果对通用链表不了解，建议一定要自己动手设计一个）。

3、List基本函数使用

1. 创

#include<list>

typedef struct rect
{
	···
}Rect;

list<Rect>test;	//声明一个链表，用于存放结构体数据

//如果想以其他方法初始化list列表，可以移步到下一行那个Vector的介绍

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

1. 增

Rect a;
···
test.push_back(a);
test.push_front(a);
//头尾插入（双向链表）

//定点插入
test.insert(test.begin()+10,a);	//在第十个节点之前插入a

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

1. 删

//删除test头部的元素
	test.erase(test.begin());

//删除test从头到尾的元素
	test.erase(test.begin(), test.end());

test.pop_back();
test.pop_front();

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

其实增删还是推荐使用迭代器来，因为直接对数据进行操作会存在一定的危险。
在本文第三部分详细讲述了List迭代器操作增删。

除了这个函数：test.clear();这个函数安全得很，反正都清理掉了。

1. 查、改

//迭代器
list<int>::iterator p；
for (p = test.begin(); p != test.end(); p++)
		cout << *p << " ";

  

 

  
1
  
2
  
3
  
4
 

要遍历还是首推迭代器。所有和遍历有关的还是用迭代器。

1. 排

#include<algorithm>
test.sort(test.begin(),test.end());	//从头到尾，默认从小到大排序

//一般排序都是要自定义排序的：
bool Comp(const int &a,const int &b)
{ return a>b;
}
sort(test.begin(),test.end(),Comp);	//这样就降序排序。 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

1. 大小

test.size();	//容器已存入数据量
test.capacity();	//容器还能存多少数据量

//其实不用担心容器不够大，容量要满的时候它会自己扩容

  

 

  
1
  
2
  
3
  
4
 

1. 其他
   (1)压缩list

//去除重复的元素至只保留一个副本
	test.unique();
	//已经过大小排序的list才能使用

  

 

  
1
  
2
  
3
 

	(2)合并list

  

 

  
1
 

test.splice(test.end(),test2);//将test2剪切到test后面

  

 

  
1
 

最后还是要提一下头文件：
分不清楚就都写上

#include<algorithm>
#include<list>

  

 

  
1
  
2
 

4、迭代器

List的迭代器和Vector还是有一定区别的，所以我特地分一块出来。
List的迭代器不能随便用普通指针来替代，因为其节点不会在内存中持续存在。

List的迭代器在有一个很好的特性，就是它不会因为节点的增加或合并（splice）操作而失效，即使是删除，也只会使得当前指向被删节点的那个迭代器失效，而不会因记忆体的重置使得全部的迭代器失效。

填上STL删除的大坑！
Vector的迭代器怎么了？

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/105372304