4.list容器
（1）list的特点
前面讲的vector是非常常用的容器，使用频繁都非常高。
vector的优势：
vectoer的优点直接导致了它的缺点，因为vector本身就是数组，数组
是顺序（连续）存储的，因此可以很好的支持随机访问，支持随机访
问是顺序存储的优势。
vector的缺点：
在序列中频繁插入和删除的效率非常的低，因为会涉及大片内存数据被
移动，这也是顺序存储的缺点。
list的优点
list的优点就是克服了vector的缺点，链表是链式存储的，链式存储的
优点在于进行频繁插入和删除的效率非常的高，因为链式存储时，链表
的节点空间并不连续，不会涉及大片内存数据移动。
list的缺点：
同样，list的有优点直接导致了它的缺点，它不支持随机访问，因为所
有的节点空间并不是连续的，所以不能跳跃性的随机访问，只能是一个
一个节点的遍历。
（2）创建一个list
（1）创建空链表
std::list<int> data;
（2）创建指定元素个数的链表
std::list<int> data(10);
链表中内容全部会被初始化为0。
（3）创建一个给定初始值的链表
（1）所有元素初始值相同的情况
std::list<int> data(10, 9527);
10个节点，所有值会被初始化为9527。
（2）所有元素初始值不同的情况
int buf[] = {1, 2, 4, 56, 23, 45, 3, 55};
std::list<int> l(buf, buf+sizeof(buf)/sizeof(buf[0]));
（3）访问list容器的元素
（1）如何访问list
（1）方法1：使用迭代器
list支持双向迭代器，但双向迭代器不支持随机访问。
list容器提供正向和逆向两种迭代器，正向迭代器需要使用
begin()函数和end()成员函数，逆向迭代器需要使用rbegin()和
rend()成员函数，这一点与vector同。
由于list不支持随机访问，因此list没有重写[]运算符，就
算是重写了[]运行算符，实际上也是通过迭代器挨个遍历实
现的，并不是真正意义上的随机访问。
使用迭代器访问内容时，需要使用*解引用才能访问迭代器指向
的内容。
（2）front()和back()函数
front()：直接返回第一个元素内容。
back()函数直接返回最后一个元素的内容
以上这两个函数与vector提供的front()和back()函数类似，
但是由于list不支持随机访问，因此没有at()函数。
（2）例子
list也有begin()和end()两个成员函数，用于返回访问list的迭代器。
这个迭代器是由list容器提供的，有了迭代器就可以遍历访问list容
器。
例子：
#include <iostream>
#include<iterator>
#include<list>
template<class iter> void show_vector(iter first, iter last) {
for( ;first!=last; first++) {
cout << *first << " ";
}
cout << endl;
}
int main(void)
{
int buf[] = {1, 2, 4, 56, 23, 45, 3, 55};
std::list<int> l1;
std::list<int> l2(10);
std::list<int> l3(buf, buf+sizeof(buf)/sizeof(buf[0]));
cout << "显示l1中的内容" << endl;
show_vector(l1.begin(), l1.end());
cout << "\n显示l2中的内容" << endl;
show_vector(l2.begin(), l2.end());
cout << "\n显示l3中的内容" << endl;
show_vector(l3.begin(), l3.end());
return 0;
}
运行结果：
显示l1中的内容
显示l2中的内容
0 0 0 0 0 0 0 0 0 0
显示l3中的内容
1 2 4 56 23 45 3 55
例子分析：
例子中分别定义了三个list，然后显示其内容，第一个list是空的
，因此没有内容被显示。
第二个list元素个数是10个，但是内容全部被默认初始化为了0。
第三个list在被定义时，被直接初始化了一些值，因此这些值可以
被打印出来。
（4）使用list容器提供的成员函数实现元素的插入删除等操作
（1）涉及函数
（1）push_front()函数：在list头部插入新元素
（2）push_back()函数：在list尾部插入新元素
（3）pop_front()函数：删除list头部元素
（4）pop_back()函数：删除list尾部元素
（5）insert()函数：在list中指定的位置插入新元素，有三个常用的
重载版本。
（1）interator insert(iterator position, const T& x);
在指定位置插入x副本，返回指向该位置的迭代器。
（2）void insert(iterator position, size_type n, const T& x);
在指定位置插入n个x的副本。
（3）void insert(iterator position, InputIterator first, InputIterator last);
在指定位置插入第二个参数和第三个参数指定的半开间
隔中的元素，至于InputIterator类型根据情况而定，
有可能是普通指针也有可能是迭代器。
（6）ereas()函数：删除指定元素，返回的迭代器指向删除元素后面的元素，
该函数有两个重载版本。
（1）iterator erase ( iterator position );
删除position位置的元素。
（2）iterator erase ( iterator first, iterator last );
删除first与last指定的半开区间之间的元素。
（7）clear()函数：删除所有元素。
（8）empty()函数：判断list是否为空。
（9）slpice()函数：拆分list的函数，该函数提供两个重载版本和一个模板。
（1）void splice ( iterator position, list<T,Allocator>& x );
将list中内容移到调用splice函数的容器的position处。
（2）void splice ( iterator position, list<T,Allocator>& x, iterator i );
将list中i位置的内容移到调用splice函数的容器的position处。
（3）void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );
将list中[first,last)之间的内容移到调用splice函数的容器的position处。
（10）resize()：设置list的大小
（11）merge()：有两个重载版本，其中一个是模板。
void merge ( list<T,Allocator>& x );
功能：将另外一个list合并到自己中来，合并后进行默认排序。
template <class Compare> void merge ( list<T,Allocator>& x, Compare comp );
功能：同上，但是可以自己提供比较函数。
该函数的例子，在后面讲全局merge时意一并举出。
（2）函数使用举例
（1）push_front/push_back/pop_front/popback函数使用举例
#include <iostream>
#include <algorithm>
#include<iterator>
#include<list>
template<class iter> void show_vector(iter first, iter last) {
for( ;first!=last; first++) {
cout << *first << " ";
}
cout << endl;
}
int main(void)
{
std::list<int> l;
cout << "向空l中的头尾插入4个int元素" << endl;
l.push_front(1);
l.push_back(4);
l.push_front(5);
l.push_back(3);
show_vector(l.begin(), l.end());
cout << "\n从l中的头和尾删除2个int元素" << endl;
l.pop_front();
l.pop_back();
show_vector(l.begin(), l.end());
return 0;
}
（2）insert/ereas/clear/empty函数使用举例
#include <iostream>
#include <algorithm>
#include<iterator>
#include<list>
template<class iter> void show_vector(iter first, iter last) {
for( ;first!=last; first++) {
cout << *first << " ";
}
cout << endl;
}
int main(void)
{
int buf[] = {1, 2, 4, 56, 23, 45, 3, 55};
std::list<int> l;
if(l.empty()) cout<<"l为空"<<endl;
cout << "\n向l的begin()指向的位置插入-1" << endl;
l.insert(l.begin(), -1);
show_vector(l.begin(), l.end());
cout << "\n向l的end()指向的位置插入e个-2\" << endl;
l.insert(l.end(), 3, -2);
show_vector(l.begin(), l.end());
cout << "\n向l的begin()指向的位置后面一个位置插入[buf,buf+3)之间的元素" << endl;
//l.insert(l.begin()+2, buf, buf+5);//list不支持随机访问，因此迭代起+n是错误的
l.insert(l.begin()++, buf, buf+5);//支持++ --
show_vector(l.begin(), l.end());
cout << "\n清空l" << endl;
l.clear();
show_vector(l.begin(), l.end());
return 0;
}
运行结果：
l为空
向l的begin()指向的位置插入-1
-1
向l的end()指向的位置插入e个-2
-1 -2 -2 -2
向l的begin()指向的位置后面一个位置插入[buf,buf+3)之间的元素
1 2 4 56 23 -1 -2 -2 -2
清空l
（3）splice函数使用举例
#include <iostream>
#include <algorithm>
#include<iterator>
#include<list>
template<class iter> void show_vector(iter first, iter last) {
for( ;first!=last; first++) {
cout << *first << " ";
}
cout << endl;
}
int main(void)
{
int buf[] = {1, 2, 4, 56, 23, 45, 3, 55};
std::list<int> l1(buf, buf+sizeof(buf)/sizeof(buf[0]));
std::list<int> l2;
cout << "将l1中的所有内容移到l2中begin()开始的位置,移除后l1就为空" << endl;
l2.splice(l2.begin(), l1);
cout << "l1中的内容" <<endl;
show_vector(l1.begin(), l1.end());
cout << "l2中的内容" <<endl;
show_vector(l2.begin(), l2.end());
cout << "\n将l2中++l2.begin()位置的内容移到l1中begin()开始的位置" << endl;
l1.splice(l1.begin(), l2, ++l2.begin());
cout << "l1中的内容" <<endl;
show_vector(l1.begin(), l1.end());
cout << "l2中的内容" <<endl;
show_vector(l2.begin(), l2.end());
cout << "\n将l2中[++l2.begin(), --l2.end())位置的内容移到l1中++begin()开始的位置" << endl;
l1.splice(++l1.begin(), l2, ++l2.begin(), --l2.end());
cout << "l1中的内容" <<endl;
show_vector(l1.begin(), l1.end());
cout << "l2中的内容" <<endl;
show_vector(l2.begin(), l2.end());
return 0;
}
运行结果：
将l1中的所有内容移到l2中begin()开始的位置,移除后l1就为空
l1中的内容
l2中的内容
1 2 4 56 23 45 3 55
将l2中++l2.begin()位置的内容移到l1中begin()开始的位置
l1中的内容
2
l2中的内容
1 4 56 23 45 3 55
将l2中[++l2.begin(), --l2.end())位置的内容移到l1中++begin()开始的位置
l1中的内容
2 4 56 23 45 3
l2中的内容
1 55
（5）list实现管理学生信息
#include <iostream>
#include<iterator>
#include<list>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
using namespace std;
class Student {
public:
Student(const string name=" ", int num=0):name(name),num(num) { }
string getname() const { return name; }
int getnum() const { return num; }
private:
string name;
int num;
};
template<class T> class List {
public:
typedef std::list<T *> Content;
typedef typename std::list<T *>::iterator Iter;
List() { }
List(Iter first, Iter last):load(first, last) { }
void add_list(T* &stu) {load.push_front(stu);}
void add_tail(T* &stu) {load.push_back(stu);}
void ereas_head() {load.pop_front();}
void ereas_tail() {load.pop_back();}
void display() {
for(Iter iter=load.begin(); iter!=load.end(); iter++) {
cout << (*(iter))->getname() << " " << (*(iter))->getnum() <<endl;
}
}
~List() {
while(load.begin() != load.end()) {
delete(load.front());
load.pop_front();
}
}
private:
Content load;
};
void init_stu_list(List<Student> &list, int count) {
string name = "name", newname = "";
char buf[10] = {0};
int num = 0;
srand(time(NULL));
for(int i=0; i<count; i++) {
num = rand()%100;
int tmp = rand()%100;
sprintf(buf, "%d", tmp);
newname = name+buf;
Student *stup = new Student(newname, num);
list.add_tail(stup);
}
}
int main(void)
{
List<Student> list;
init_stu_list(list, 20);
while(1) {
cout<<"1. add stu to list" <<endl;
cout<<"2. delete stu form list" <<endl;
cout<<"3. find stu by num" <<endl;
cout<<"4. alter stu to list" <<endl;
cout<<"5. display list" <<endl;
cout<<"6. sort list" <<endl;
cout<<"7. exit" <<endl;
int select = 0;
cin >> select;
switch(select) {
case 5: list.display(); break;
default: cout << "未实现" << endl;
}
}
return 0;
}
例子分析：
例子中需要自己利用迭代器实现排序/查找等算法函数，但是实际上c++的STL模板
库提供了现成的全局算法函数。
网友评论