STL:主要是一些“容器”的集合;“容器”有:vector(数组)、list(双向链表)、deque(双向队列)、set(集合)、map(图:内部结构红黑树)
STL也是算法和其他一些组件的集合,是泛型编程的一个经典范例。
STL的目的是标准化组件,这样就不用重新开发,可以使用现成的组件。
-
STL六个组成部分
1、容器:特殊的数据结构,实现了数组、链表、队列等,实质是类模板。
2、迭代器:一种复杂的指针,可以通过其读写容器中的对象,实质是运算符重载。
3、算法:读写容器对象的逻辑算法:排序、遍历、查找.......,实质是模板函数。
4、空间配置器:分配空间。
5、配接器:用来修饰容器、仿函数、迭代器接口,配合仿函数使用。
6、仿函数:类似函数,通过重载()运算符来模拟函数行为的类
-
组件间的关系
容器通过配置器取得数据存储空间,算法通过迭代器存取容器内容,仿函数可以协助算法完成不同的策略变化,配接器可以修饰或套接仿函数。
-
vector(单向数组)
规定只能从尾巴进行插入、尾巴进行删除,数组空间可扩容。
可以在中间插入删除,但不建议使用。
成员函数(迭代器相关)
begin:返回指向元素首地址的迭代器(指向元素开头),++操作(后)右走iterator
end:返回指向元素末尾的迭代器,最后一个元素的下一个位置。iterator
rbegin:逆向迭代器(指向元素末尾),++操作(前)左走reverse_iterator
rend:逆向迭代器(指向元素开头)reverse_iterator
cbegin:返回一个常量迭代器,指向vector容器的第一个元素的位置。const_iterator
cend:返回一个常量迭代器,指向容器中最后一个元素的下一个位置。const_iterator
容量
size:返回元素个数。
max_size:容量
resize:改变大小
empty:判空
重载
[ ]
at
使用方法
push_back:入栈。
back:返回最后一个元素。
pop_back:出栈,删除,无返回值。
insert:插入
swap:交换
clear:清空
sort:排序,头文件<algorithm>
erase:删除迭代器指向元素/删除一段元素
例:
vector<int> arr; //定义了一个名为arr的vector容器,arr容器中每个元素为int类型。
vector<vector<int>> arr; //定义了一个名为arr的二维容器,此容器中每个元素是一个int类型的容
器。
vector<int> arr (5); //定义了一个名为arr的vector容器,vector容器中共有5个元素,每个元素为int类型。
vector<int> arr (3,100); //定义了一个名为arr的vector容器,vector容器中共有3个元素,每个元素都初始化为100。
push_back:自动扩容
[ ]:会自动扩容
at:需要设置容量
迭代器:指针,vector成员iterator
swap:交换元素值
sort:升序排序 头文件<algorithm>
erase:删除迭代器指向元素
erase:删除一段元素
总结
vector向量相当于一个数组,在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。
优点:
可以不指定大小,使用push_back、pop_back来进行动态操作。
随机访问方便,即支持[ ]操作符与at()
节省空间
缺点:
在内部进行插入、删除的效率低。
只能在最后进行push和pop。
当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放。
-
list(双向链表)
每一个节点都包含一个信息块Infor,一个前驱指针Pre,一个后驱指针Post。可以不分配必须的内存大小,方便进行增加和删除操作。使用的是非连续的内存空间进行存储。常使用迭代器进行操作。
优点:
不使用连续内存完成动态操作;
在内部方便得进行插入和删除操作;
可在两端进行push、pop
缺点:
不能在内部进行随机访问,即不支持.at()、[ ]操作符
相对于vector占用内存多(vector只有数据块,list多了指针)
访问list一般情况都使用迭代器。
函数
push_front:头插
push_back:尾插
pop_front:头出
pop_back:尾出
成员函数(迭代器相关)
begin、end、rbegin、rend、cbegin、cend、crbegin、crend
容量
empty、size、max_size
使用方法
insert、erase、swap、resize、clear
示例
begin、end
rbegin、rend返回reverse_iterator逆向迭代器
cbegin、cend返回const_iterator常量迭代器
总结
双向链表;插入和删除在任意位置效率都很高;不能随机访问,不支持[ ],at();访问list一般情况都使用迭代器。
-
deque(双向队列)
存储方式采用分块存储;deque在功能上合并了vector和list。
优点:
随机访问方便,即支持[ ]和vector.at();
在内部方便地进行插入和删除操作;
可在两端进行push、pop。
缺点:
占用内存多。
erase:删除迭代器所指位置/一段数据
deque<int> mydeque;
1、mydeque.erase(mydeque.begin()+5); //begin()返回的是迭代器(指针)
2、mydeque.erase(mydeque.begin(),mydeque.begin()+3);
C++11新特性
emplace : insert
emplace_front : push_front
emplace_back : push_back
使用区分
如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector;
如果你需要大量的插入和删除,而不关心随机存取,则应使用list;
如果你需要随机存取,而且关心两端数据的插入和删除,则应使用deque。
STL序列容器:vector、deque、list
STL关联容器:set、multiset、map、multimap
STL迭代器:iterator
-
set(集合)
set是一个有序的集合,其中的元素插入后就会按照某种规则进行排序,从小到大。
内部红黑树,无值相同的元素。
s.find:返回指向查找的指定元素的迭代器
s.count:查找指定数据是否存在,存在则1,不存在则0
lower_bound:
函数返回的迭代器指向的元素是集合中第一个不小于给定值的元素。
upper_bound:
函数返回一个指向大于给定值的元素的迭代器,即返回指向第一个大于给定值的元素的迭代器。
示例
从小到大排列,且插入相同的值,只有第一次有效。
count:查找指定数据是否存在,存在则1,不存在则0
红黑树排列:12578
erase:删除2-8之间的元素(包括2,不包括8)
find:返回指向查找的指定元素的迭代器。
排序:12578
lower_bound:由于有5,则返回指向5的迭代器,无则指向5的下一位数7
upper_bound:指向给定值7的下一位数8
erase:删除5-8之间的数(包括5,不包括8)
-
map(图)
内部红黑树
是一种关联容器,用于存储键值对。每个键值对称为一个元素,键和值可以是任意数据类型。Map中的元素按照键的大小自动排序,并且每个键只能在map中出现一次。
map中键不能重复,重复则第二次为修改。
map中值可以相同。
map中会按照键从小到大排列
C++官网:www.cplusecpluse.com