顺序容器

Posted on   |   In   |  

主要介绍c++中的顺序容器

顺序容器

在c++中主要有三种类型的顺序容器:vector, list, deque;
标准库还提供了三种容器适配器: stack, queue, priority_queue

1
2
3
vector<int> ivec;
list<int> ilist;
deque<int> ideq;

容器元素初始化

函数 意义
C< T> c; 创建一个名为c的空容器
C c(c2); 创建容器c2的副本；c和c2必须拥有相同的容器类型，并存放相同类型的元素
C c(b,e); 创建c，其元素是迭代器b和e标示的范围内元素的副本,并不要求容器类型相同
C c(n, t); 用n个值为t的元素创建容器c，其中值t必须是容器类型C的元素类型，或者是可以转换成该类型的值只适用与顺序容器
C c(n); 创建有n个值初始化元素的容器c （元素要有默认构造函数）只适用与顺序容器

可以总结为四种方法

  • 空容器
  • 容器副本
  • 用一段元素的副本(特别注意与容器副本的区别)
  • 分配和初始化指定数目的元素

    容器内元素类型的约束

  • 元素类型必须支持赋值运算
  • 元素类型的对象必须可以复制
    特别需要注意的是，io库类型不支持复制或赋值

容器的容器
vector< vector < int > > //中间要用空格隔开，否则为>>

迭代器

list容器的迭代器既不支持算数运算(加法或减法)，也不支持关系运算( <= , < , >=, >),它值提供前置和后置的自增、自减运算以及相等(不等)运算。
list< int > ilist(10);
list< int >:iterator it = ilist.degin() + 2 //进行了算术运算，错误

1
2
3
4
const vector < int > ivec(10);   
vector < int >::iterator it = ivec.begin();
//错误
迭代其类型应该为const vector<int>

迭代器范围

使迭代器失效的容器操作

一些容器操作会修改容器的内在状态或移动容器内的与元素，这样做使所有指向被移动元素的迭代器失效，也可能使其他迭代器失效

顺序容器的操作

容器定义的类型别名

类型 意义
size_type 无符号类型，足以存储此容器类型的最大可能容器长度
iterator 迭代器类型
const_iterator 元素的只读迭代器类型
reverse_iterator 按逆序寻址元素的迭代器
const_reverse_iterator 元素的只读逆序迭代器
difference_type 足够存储两个迭代器差值的有符号整形，可为负
value_type 元素类型
reference 元素的左值类型，是value_type&的同义词
const_reference const value_type &

begin和end成员

begin(),end(),rbegin(),rend()
上述每个操作有两个版本：一个是const成员，另一个是非const成员，这些操作取决于容器是否为const。

在顺序容器中添加元素

常用方法：
|方法|意义|
|—|—|
|push_back()|尾部添加，返回void |
|push_front()| 前段添加，返回void|
|insert(p,t)| 在迭代器p所指向的元素前面插入值为t的新元素。返回指向新元素的迭代器|
|insert(p,n,t)|在迭代器p所指向的元素前面插入n个值为t的新元素。返回void|
|insert(p,b,e)|在迭代器p所指向的元素前面插入有迭代器b和e标记的范围内元素，返回void|

特别需要注意的是:

  • 添加元素可能会是迭代器失效
  • 要注意避免存储end操作返回的迭代器
1
2
3
4
5
6
7
8
//程序运行出错的原因在于insert操作可能导致迭代器的失效，这样last将不会是最新的end迭代器的内容
vector<int>::iterator first = v.begin()
                      last = v.end();
                      
    while(first != last){
        first = v.insert(first, 42);
        ++first;
    }

可以总结为：选取作为哨兵的迭代器一定要保证是最新的状态。不能简单的用一个迭代器存储它。

关系操作符

比较的容器必须具有相同的容器类型，而且其元素类型也相同