从实现层面看,相较于Vector的线性空间,List的实现要复杂的多。 List的优势在于每次插入或删除一个元素,就分配或释放一个位置。因此,List对于空间的把控有绝对的精准。 而且,对于从任何节点增删数据,List消耗的永远是常数时间。
List和Vector的使用应该视元素的多寡、元素的构造复杂度、元素的存取频繁度而定。List优在存取,Vector优在查询。
每一个自己写过链表的人都知道,链表的节点和链表本身是分开设计的。 那我们来看一下List的节点设计:
template <typename T>
struct __list_node
{
typedef void* void_pointer;
void_pointer prev;
void_pointer neet;
T date;
}
显而易见,这是一个通用双向链表的节点(如果对通用链表不了解,建议一定要自己动手设计一个)。
#include<list>
typedef struct rect
{
···
}Rect;
list<Rect>test; //声明一个链表,用于存放结构体数据
//如果想以其他方法初始化list列表,可以移步到下一行那个Vector的介绍
Rect a;
···
test.push_back(a);
test.push_front(a);
//头尾插入(双向链表)
//定点插入
test.insert(test.begin()+10,a); //在第十个节点之前插入a
//删除test头部的元素
test.erase(test.begin());
//删除test从头到尾的元素
test.erase(test.begin(), test.end());
test.pop_back();
test.pop_front();
其实增删还是推荐使用迭代器来,因为直接对数据进行操作会存在一定的危险。 在本文第三部分详细讲述了List迭代器操作增删。
除了这个函数:test.clear();
这个函数安全得很,反正都清理掉了。
//迭代器
list<int>::iterator p;
for (p = test.begin(); p != test.end(); p++)
cout << *p << " ";
要遍历还是首推迭代器。所有和遍历有关的还是用迭代器。
#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); //这样就降序排序。
test.size(); //容器已存入数据量
test.capacity(); //容器还能存多少数据量
//其实不用担心容器不够大,容量要满的时候它会自己扩容
//去除重复的元素至只保留一个副本
test.unique();
//已经过大小排序的list才能使用
(2)合并list
test.splice(test.end(),test2);//将test2剪切到test后面
最后还是要提一下头文件: 分不清楚就都写上
#include<algorithm>
#include<list>
List的迭代器和Vector还是有一定区别的,所以我特地分一块出来。 List的迭代器不能随便用普通指针来替代,因为其节点不会在内存中持续存在。
List的迭代器在有一个很好的特性,就是它不会因为节点的增加或合并(splice)操作而失效,即使是删除,也只会使得当前指向被删节点的那个迭代器失效,而不会因记忆体的重置使得全部的迭代器失效。