锐客网

  1. 首页 > it技术 > >

2019-10-13|2019-10-13 STL模板

STL共有六大组件
1、容器 2、算法 3、迭代器 4、仿函数 6、适配器
STL容器的实现原理
STL来管理数据十分方便,省去了我们自己构建数据结构的时间.其实,STL的实现也是基于我们常见的数据结构.
序列式容器：
1： vector 向量，支持o（1）时间的快速访问；元素不够时再重新分配内存，拷贝原来数组的元素到新分配的数组中，这一点可以通过实验进行证明
#include
#include
usingnamespacestd;
int main() {
vector vec;
for(inti = 0; i<100; i++) {
vec.push_back(i);
cout << "capacity is "<< vec.capacity() << endl;
}
}
注意事项：根据vector的插入和删除特性0（N）；再插入位置和删除位置之后所有的迭代器和指针引用都会实效。




2： list双向链表
vector强调的是通过随机访问快速访问，而list强调的是元素的快速插入和删除
3：关联式容器
map与unordered_map有序的
相同：两者都是键-值对的集合，关联容器的一种。两者中的元素都是pair，同时拥有实值和键值。两者都不允许有两个相同的键值（实值可以相同）。两个的外部接口调用基本一致。
不同：内部实现机理不同，即map内部实现了一个红黑树 logN的查找 插入和删除；unordered_map内部实现了一个哈希表。（两者的比较成为红黑树与哈希表的比较）。由于内部实现机理不同（底层实现）造成以下不同。
map的有序性：红黑树（非严格平衡二叉树），该结构具有自动排序的功能，因此map内部的所有元素都是有序的。
unordered_map的无序性：哈希表不会根据key值大小进行排序，存储时是根据key的hash值判断元素是否相同，因此unordered_map内部元素是无序的。
map的运行效率：红黑树可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
unordered_map的运行效率：哈希表的查找的时间复杂度可达到O(1)
【2019-10-13|2019-10-13 STL模板】 unordered_map内存占用比map高

    推荐阅读


    上一篇：科目三

    下一篇：第二次作业?（朱小飞--悟静）