文章目录
注:文章来源是网上博客内容整理而来,具体见参考。
零、概述
0.1、容器
实质上是一组相同类型对象的集合,但它不仅仅是数组那么简单,它实现了比数组更复杂的数据结构,能够实现更复杂的功能。C++标准模版库里提供了10种通用的容器,它基本可以解决程序中遇到的大部分问题。
C++中容器的定义如下:数据存储上,有一种对象类型,它可以持有其他对象或指向其他对象的指针,这种对象类型叫容器。通俗的说容器就是保存其他对象的对象,这种“对象”还包含了一些列处理其他对象的方法,这也体现了容器类的一个好处,“容器类对特定代码重用问题的良好的解决方案”。
容器另一个好处就是可以自行扩展,解决问题是我们不知道需要存储多少个对象,数组在这方面是个欠缺。容器可以为你申请内存、释放内存,并且使用最优的算法来执行你的命令。
0.2、分类
标准容器 | 类 | 说明 | |
顺序容器 | 向量 | vector | 从后面快速的插入与删除,直接访问任何元素 |
列表 | list | 双链表,从任何地方快速插入与删除 | |
队列 | deque | 从前面或后面快速的插入与删除,直接访问任何元素 | |
关联容器 | 集合 | map | 一对多映射,基于关键字快速查找,不允许重复 |
映射 | set | 快速查找,不允许重复值 | |
多重集合 | multimap | 一对多映射,基于关键字快速查找,允许重复值 | |
多重映射 | multiset | 快速查找,允许重复值 | |
容器适配器 | 栈 | stack | 后进先出 |
队列 | queue | 先进先出 | |
优先级队列 | priority_queue | 最高优先级元素总是第一个出列 |
0.3、共有函数
1、所有标准库共有函数
默认构造函数 | 提供容器默认初始化的构造函数。 |
复制构造函数 | 将容器初始化为现有同类容器副本的构造函数 |
析构函数 | 不再需要容器时进行内存整理的析构函数 |
empty | 容器中没有元素时返回true,否则返回false |
max_size | 返回容器中最大元素个数 |
size | 返回容器中当前元素个数 |
operator= | 将一个容器赋给另一个容器 |
operator< | 如果第一个容器小于第二个容器,返回true,否则返回false, |
operator<= | 如果第一个容器小于或等于第二个容器,返回true,否则返回false |
operator> | 如果第一个容器大于第二个容器,返回true,否则返回false |
operator>= | 如果第一个容器大于或等于第二个容器,返回true,否则返回false |
operator== | 如果第一个容器等于第二个容器,返回true,否则返回false |
operator!= | 如果第一个容器不等于第二个容器,返回true,否则返回false |
swap | 交换两个容器的元素 |
2、顺序容器和关联容器共有函数
begin | 该函数两个版本返回iterator或const_iterator,引用容器第一个元素 |
end | 该函数两个版本返回iterator或const_iterator,引用容器最后一个元素后面一位 |
rbegin | 该函数两个版本返回reverse_iterator或const_reverse_iterator,引用容器最后一个元素 |
rend | 该函数两个版本返回reverse_iterator或const_reverse_iterator,引用容器第一个元素前面一位 |
erase | 从容器中清除一个或几个元素 |
clear | 清除容器中所有元素 |
3、顺序容器和关联容器中常用的typedef
value_type | 容器中存放元素的类型 |
reference | 容器中存放元素类型的引用 |
const_reference | 容器中存放元素类型的常量引用,这种引用只能读取容器中的元素和进行const操作 |
pointer | 容器中存放元素类型的指针 |
iterator | 指向容器中存放元素类型的迭代器 |
const_iterator | 指向容器中存放元素类型的常量迭代器,只能读取容器中的元素 |
reverse_iterator | 指向容器中存放元素类型的逆向迭代器,这种迭代器在容器中逆向迭代 |
const_reverse_iterator | 指向容器中存放元素类型的逆向迭代器,只能读取容器中的元素 |
difference_type | 引用相同容器的两个迭代器相减结果的类型(list和关联容器没有定义operator-) |
size_type | 用于计算容器中项目数和检索顺序容器的类型(不能对list检索) |
一、顺序性容器
1.0、概要
1、使用选择:
如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector
如果你需要大量的插入和删除,而不关心随机存取,则应使用list
如果你需要随机存取,而且关心两端数据的插入和删除,则应使用deque
若需要随机访问操作,则选择vector;
若已经知道需要存储元素的数目, 则选择vector;
若需要随机插入/删除(不仅仅在两端),则选择list
只有需要在首端进行插入/删除操作的时候,才选择deque,否则都选择vector。
若既需要随机插入/删除,又需要随机访问,则需要在vector与list间做个折中。
当要存储的是大型负责类对象时,list要优于vector;当然这时候也可以用vector来存储指向对象的指针,同样会取得较高的效率,但是指针的维护非常容易出错,因此不推荐使用。
1.1、vector
1、基本概念
vector向量相当于一个数组;
在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacity() 函数返回的大小,当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
2、优缺点
优点:
1) 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组进行动态操作。通常体现在push_back() pop_back()
2) 随机访问方便,即支持[ ]操作符和vector.at()
3) 节省空间。
缺点:
1) 在内部进行插入删除操作效率低。
2) 只能在vector的最后进行push和pop,不能在vector的头进行push和pop。
3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放。
3、使用
//1.定义和初始化 vector<int> vec1; //默认初始化,vec1为空 vector<int> vec2(vec1); //使用vec1初始化vec2 vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2 vector<int> vec4(10); //10个值为的元素 vector<int> vec5(10,4); //10个值为的元素 //2.常用操作方法 vec1.push_back(100); //添加元素 int size = vec1.size(); //元素个数 bool isEmpty = vec1.empty(); //判断是否为空 cout<<vec1[0]<<vec1.at(0)<<endl;//取得第一个元素 vec1.insert(vec1.end(),5,3); //从vec1.back位置插入个值为的元素 vec1.pop_back(); //删除末尾元素 vec1.erase(vec1.begin(),vec1.end());//删除之间的元素,其他元素前移 cout<<(vec1==vec2)?true:false; //判断是否相等==、!=、>=、<=... vector<int>::iterator iter = vec1.begin(); //获取迭代器首地址 vector<int>::const_iterator c_iter = vec1.begin(); //获取const类型迭代器 vec1.clear(); //清空元素 //3.遍历 //下标法 int length = vec1.size(); for(int i=0;i<length;i++) cout<<vec1[i]; cout<<endl<<endl; //迭代器法 vector<int>::const_iterator iterator = vec1.begin(); for(;iterator != vec1.end();iterator++) cout<<*iterator;
4、实现
1.2、list
1、基本概念
具有双链表结构,每个元素维护一对前向和后向指针,因此支持前向/后向遍历。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
2、优缺点
优点:
1) 不使用连续内存完成动态操作。
2) 在内部方便的进行插入和删除操作
3) 可在两端进行push、pop
缺点:
1) 不能进行内部的随机访问,即不支持[ ]操作符和vector.at()
2) 相对于verctor占用内存多
3、使用
//1.定义和初始化 list<int> lst1; //创建空list list<int> lst2(3); //创建含有三个元素的list list<int> lst3(3,2); //创建含有三个元素的list list<int> lst4(lst2); //使用lst2初始化lst4 list<int> lst5(lst2.begin(),lst2.end()); //同lst4 //2.常用操作方法 lst1.assign(lst2.begin(),lst2.end()); //分配值 lst1.push_back(10); //添加值 lst1.pop_back(); //删除末尾值 lst1.begin(); //返回首值的迭代器 lst1.end(); //返回尾值的迭代器 lst1.clear(); //清空值 bool isEmpty1 = lst1.empty(); //判断为空 lst1.erase(lst1.begin(),lst1.end()); //删除元素 lst1.front(); //返回第一个元素的引用 lst1.back(); //返回最后一个元素的引用 lst1.insert(lst1.begin(),3,2); //从指定位置插入个 lst1.rbegin(); //返回第一个元素的前向指针 lst1.remove(2); //相同的元素全部删除 lst1.reverse(); //反转 lst1.size(); //含有元素个数 lst1.sort(); //排序 lst1.unique(); //删除相邻重复元素 //3.遍历 //迭代器法 for(list<int>::const_iterator iter = lst1.begin();iter != lst1.end();iter++) cout<<*iter; cout<<endl;
4、实现
1.3、deque
1、基本概念
deque是在功能上合并了vector和list。
类似于vector,不同之处在于,deque提供了两级数组结构,第一级完全类似于vector,代表实际容器;另一级维护容器的首位地址。这样,deque除了具有vector的所有功能外,还支持高效的首端插入/删除操作。
2、优缺点
优点:
1) 随机访问方便,即支持[ ]操作符和vector.at()
2) 在内部方便的进行插入和删除操作
3) 可在两端进行push、pop
缺点:
1) 占用内存多
3、使用
4、实现
二、关联容器
2.0、概述
1、pair类型
pair定义于头文件utility中,主要的作用是将两个数据组合成一个数据。pair实质上是一个结构体,其主要的两个成员变量是first和second。
与容器一样,pair 也是一种模板类型。但又与之前介绍的容器不同,在创建 pair 对象时,必须提供两个类型名:pair 对象所包含的两个数据成员各自对应的类型名字,这两个类型必相同。
pair<string, string> anon; // holds two strings
pair<string, int> word_count; // holds a string and an int
pair<string, vector<int> > line; // holds string and vector<int>
如果在创建 pair 对象时不提供初始化式,则调用默认构造函数对其成员采用值初始化。于是,anon 是包含两空 string 类型成员的 pair 对象,line 则存储一个空的 string 类型对象和一个空的vector 类型对象。word_count 中的 int 成员获得 0 值,而 string 成员则初始化为空 string 对象。
2、
2.1、map
1、基本概念
map 是键-值对的集合。map 类型通常可理解为关联数组(associative array):可使用键作为下标来获取一个值,正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联,而并非通过元素在数组中的位置来获取。
2、优缺点
3、使用
//1.定义和初始化 map<int,string> map1; //空map //2.常用操作方法 map1[3] = "Saniya"; //添加元素 map1.insert(map<int,string>::value_type(2,"Diyabi"));//插入元素 map1.insert(pair<int,string>(1,"Siqinsini")); map1.insert(make_pair<int,string>(4,"V5")); string str = map1[3]; //根据key取得value,key不能修改 map<int,string>::iterator iter_map = map1.begin();//取得迭代器首地址 int key = iter_map->first; //取得eky string value = iter_map->second; //取得value map1.erase(iter_map); //删除迭代器数据 map1.erase(3); //根据key删除value map1.size(); //元素个数 map1.empty(); //判断空 map1.clear(); //清空所有元素 //3.遍历 for(map<int,string>::iterator iter = map1.begin();iter!=map1.end();iter++) { int keyk = iter->first; string valuev = iter->second; }
4、实现
2.2、set
1、基本概念
set的含义是集合,它是一个有序的容器,里面的元素都是排序好的,支持插入,删除,查找等操作,就像一个集合一样。所有的操作的都是严格在logn时间之内完成,效率非常高。
set和multiset的区别是:set插入的元素不能相同,但是multiset可以相同。Set默认自动排序。使用方法类似list。
set 不支持下标操作符,而且没有定义 mapped_type 类型。
2、优缺点
3、使用
4、实现
2.3、multimap
2.4、multiset
三、容器适配器
3.0、概述
3.1、stack
1、基本概念
它可以将任意类型的序列容器转换为一个堆栈,一般使用deque作为支持的序列容器。
元素只能后进先出(LIFO)。
不能遍历整个stack。
2、优缺点
3、使用
4、实现
3.2、queue
1、基本概念
它可以将任意类型的序列容器转换为一个队列,一般使用deque作为支持的序列容器。
元素只能先进先出(FIFO)。
不能遍历整个queue。
2、优缺点
3、使用
4、实现
3.3、priority_queue
1、基本概念
它可以将任意类型的序列容器转换为一个优先级队列,一般使用vector作为底层存储方式。
只能访问第一个元素,不能遍历整个priority_queue。
第一个元素始终是优先级最高的一个元素。
2、优缺点
3、使用
4、实现
参考:
1、http://www.360doc.com/content/14/0408/11/1317564_367203273.shtml
2、https://segmentfault.com/a/1190000000325549
3、http://blog.chinaunix.net/uid-21411227-id-1826905.html
4、http://blog.csdn.net/conanswp/article/details/23297441
转载标明出处:https://blog.evanxia.com/2016/03/274