4.lists(双向链表)
一.概述
是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。
虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。
二.特点
(1) 不使用连续的内存空间这样可以随意地进行动态操作；
(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop 。
(3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；
Lists将元素按顺序储存在链表中，与向量(vectors)相比，它允许快速的插入和删除，但是随机访问却比较慢.。
C++标准规定：每种的容器都必须提供自己的迭代器，容器提供的一些函数以获得迭代器并以之遍历所有元素，而迭代器就是容器提供的一种遍历的方式，其本质上是一个指针。
三.常用API
| assign() | 给list赋值 |
| back() | 返回最后一个元素 |
| begin() | 返回指向第一个元素的迭代器 |
| clear() | 删除所有元素 |
| empty() | 如果list是空的则返回true |
| end() | 返回末尾的迭代器 |
| erase() | 删除一个元素 |
| front() | 返回第一个元素 |
| get_allocator() | 返回list的配置器 |
| insert() | 插入一个元素到list中 |
| max_size() | 返回list能容纳的最大元素数量 |
| merge() | 合并两个list |
| pop_back() | 删除最后一个元素 |
| pop_front() | 删除第一个元素 |
| push_back() | 在list的末尾添加一个元素 |
| push_front() | 在list的头部添加一个元素 |
| rbegin() | 返回指向第一个元素的逆向迭代器 |
| remove() | 从list删除元素 |
| remove_if() | 按指定条件删除元素 |
| rend() | 指向list末尾的逆向迭代器 |
| resize() | 改变list的大小 |
| reverse() | 把list的元素倒转 |
| size() | 返回list中的元素个数 |
| sort() | 给list排序 |
| splice() | 合并两个list |
| swap() | 交换两个list |
| unique() | 删除list中重复的元素 |
四.示例Demo
1) 使用迭代器遍历当前list元素
#include <iostream>
#include <stdlib.h>
#include <list> using namespace std;
#pragma warning(disable:4996) /*
const int arraysize = 10;
int ai[arraysize] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int *begin = ai;
int *end = ai + arraysize; // end指向的是9后面的空间
for (int *pi = begin; pi != end; ++pi)
{
cout << *pi << "";
}
*/ // 使用迭代器遍历当前链表1
void printlist(list<int> &l)
{
for (list<int>::iterator p = l.begin(); p != l.end(); ++p)
{
cout << "current item is: " << *p << endl;
}
} // 使用迭代器遍历当前链表2
void printlist2(list<int> &l)
{
list<int>::iterator current = l.begin(); // 返回第一个元素的迭代器，头指针，迭代器本质上就是一个指针
while (current != l.end()) // l.end() 代表末尾迭代器 尾指针
{
cout <<"current item is: " <<*current << endl;
current++;
} } int main() { list<int> l; for (int i = ; i < ; i++)
{
l.push_back(i + );
} cout << "current list size is: " << l.size() << endl;
printlist(l); printf("----------------------------------------\n"); list<int> s;
for (int i = ; i < ; i++)
{
s.push_front();
} list<int>::iterator s_iterator = s.begin(); // 从链表中取出链表的开头，赋值给迭代器，初始位置为0
s_iterator++;
s_iterator++;
s_iterator++; // 当前迭代器运行到3号位置(从0开始)
s.insert(s_iterator, ); // 在3号位置插入 printlist2(s); system("pause");
return ;
}
运行结果：
current list size is: 5
current item is: 1
current item is: 2
current item is: 3
current item is: 4
current item is: 5
----------------------------------------
current item is: 0
current item is: 0
current item is: 0
current item is: 5
current item is: 0
current item is: 0
current item is: 0
current item is: 0
current item is: 0
current item is: 0
current item is: 0
2) 链表元素为结构体或结构体指针
#include <iostream>
#include <stdlib.h>
#include <list> using namespace std;
#pragma warning(disable:4996) struct Teacher {
char name[];
int age;
}; // 使用迭代器遍历当前链表
void printlist(list<Teacher*> &l)
{
for (list<Teacher*>::iterator p = l.begin(); p != l.end(); ++p)
{
Teacher *teacher = *p;
cout << "Teacher, name is: " << teacher->name << ", age is: " << teacher->age << endl;
}
} // 使用迭代器遍历当前链表
void printlist2(list<Teacher> &l)
{
list<Teacher>::iterator current = l.begin(); // 返回第一个元素的迭代器，头指针，迭代器本质上就是一个指针
while (current != l.end()) // l.end() 代表末尾迭代器 尾指针
{
Teacher teacher = *current;
cout << "Teacher, name is: " << teacher.name << ", age is: " << teacher.age << endl;
current++;
} } int main() { Teacher t1, t2, t3;
strcpy(t1.name,"jack");
t1.age = ;
strcpy(t2.name,"mike");
t2.age = ;
strcpy(t3.name,"tom");
t3.age = ; list<Teacher> l;
l.push_back(t1);
l.push_back(t2);
l.push_back(t3); printlist2(l); printf("------------------指针元素-------------------\n");
list<Teacher *> m;
m.push_back(&t1);
m.push_back(&t2);
m.push_back(&t3); printlist(m); system("pause");
return ;
}
运行结果：
Teacher, name is: jack, age is: 11
Teacher, name is: mike, age is: 22
Teacher, name is: tom, age is: 33
------------------指针元素-------------------
Teacher, name is: jack, age is: 11
Teacher, name is: mike, age is: 22
Teacher, name is: tom, age is: 33
最新文章
- jQuery lazyload 懒加载
- 8.js模式-状态模式
- 我使用中的Linux命令和快捷键(For Ubuntu)
- s3c2440 J-flash 烧写 NOR flash
- vue js 用nodejs的依赖包 --2016-08-23
- Python教程：[69]strip()函数详解
- AppCan做的图片上传代码
- Delphi用TActionList下载文件
- RIA(富客户端)发展态势
- linux 建库，编码，导入数据
- Android漫游记(4)---.so文件动态调试一例
- 浅析——SCTP协议（转）
- MVC下判断用户登录和授权状态方法
- FusionCharts参数大全及详细说明（中文）
- TCP协议和UDP协议的区别
- Android studio 使用startService报错：IllegalStateException
- 解决weblogic 部署环境后出现的乱码问题
- [转]CentOS6 Linux上安装ss5服务器
- python3 练习题(多级菜单)
- hazelcast初探