<C++程序设计>数据结构

Vector重新分配内存时，要全部把元素拷贝走，往尾部添加元素在常数时间内完成，往首部或者中间插入元素时间复杂度为O(n),要把元素一个一个移动，动态数组

1.Deque是双向队列，在两端增删元素有较好的性能，从队头走到队尾是存储空间Deque的大小

2.List是双向链表，不支持随机存取

3.Set即集合，set不允许有相同的元素存在，multiset允许存在相同的元素

4.Map/MultiMap

Map与Set的不同在于map存放的元素仅且只有两个，一个名为first，一个名为second，map会根据first的值大小进行从小到大的排序，并快速根据first进行索引元素，map和multimap的区别在于后者允许有相同的first出现

顺序容器：vector,deque,list

关联容器:set,multiset,map,multimap

容器适配器:stack,queue,Priority_queue(优先级队列，优先级最高的元素总是第一个出列)

顺序容器和关联容器都有的成员函数

begin:返回第一个元素的迭代器

end:返回最后一个元素后面位置的迭代器

rbegin:最后一个元素

rend:第一个元素前面的位置

erase:删除一个或几个元素

clear:删除所有元素

顺序容器的常用成员函数（Vector,deque,list）

front ：返回容器中第一个元素的引用

back：返回容器中最后一个元素的引用

push_back 在容器的末尾增加新元素

pop_back 删除容器的末尾的新元素

erase: 删除迭代器指向的元素，或删除一个区间，返回被删除元素后面那个元素的迭代器

迭代器

迭代器是访问容器中元素的，相当于中介，用起来跟指针一样

1.用于指向顺序容器和关联容器中的元素

2.迭代器的用法和指针类似

3.有const 和非const之分

4.通过迭代器可以读取它指向的元素

5.通过非const迭代器还能修改其指向的元素

定义一个容器类迭代器的方法是：

容器类名::iterator 变量名; 或 容器类名::const iterator 变量名；迭代器上可以执行++操作访问下一个元素，到达末尾再执行++操作就会报错

Vector的使用方法

#include<Vector>

int main(){

Vector<int> V;//一个存放int元素的数组

V.push_back(1); V.push_back(2);

Vector<int> ::const iterator i;//定义一个常量迭代器，只访问不能修改

for(i=V.begin();i!=V.end();i++)

cout<<*i<<",";//  取出迭代器指向的元素

}



Vector<int> ::reverse iterator r;//反向迭代器，r++是向前走，指向前一个元素