C++中STL各容器详解
一、STL中六大组件:1)容器(Container),是一种数据结构,如list,vector,和deques ,以模板类的方法提供。为了访问容器中的数据,可以使用由容器类输出的迭代器;2)迭代器(Iterator),提供了访问容器中对象的方法。例如,可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。但是,迭代器也可以...
一、STL中六大组件:
1)容器(Container),是一种数据结构,如list,vector,和deques ,以模板类的方法提供。为了访问容器中的数据,可以使用由容器类输出的迭代器;
2)迭代器(Iterator),提供了访问容器中对象的方法。例如,可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。但是,迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象。迭代器实际上也是一种将operator*、operator->、operator++、operator--等指针相关操作予以重载的class template
3)算法(Algorithm),是用来操作容器中的数据的模板函数。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象,函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用;
4)仿函数(Function object) ,行为类似函数,可作为算法的某种策略。从实现角度看,仿函数是一种重载了operator()的class或class template。一般函数指针可视为狭义的仿函数。
5)迭代适配器(Adaptor),一种用来修饰容器、仿函数、迭代器接口的东西。STL提供的的queue和stack,虽然看似容器,其实只能算是一种容器配接器,因为他们的弟弟不完全借助deque,所有操作都由底层deque提供。
6)配置器(allocator),负责空间配置与管理。实现了动态空间配置,空间管理,空间释放的class template。
7)六大组件的交互关系:容器通过空间配置器取得数据存储空间,算法通过迭代器取得容器的内容,仿函数可以协助空间配置器完成不同的策略变化,适配器可以修饰或套接仿函数。
二、底层数据结构的实现
1.vector 底层数据结构为数组 ,支持快速随机访问。
2.list 底层数据结构为双向链表,支持快速增删。
3.deque 底层数据结构为一个中央控制器和多个缓冲区,支持首尾(中间不能)快速增删,也支持随机访问,看起来像是list和vector的结合品。
4.stack 底层一般用list或deque实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时。
5.queue 底层一般用list或deque实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时。
(stack和queue其实是适配器,而不叫容器,因为是对容器的再封装)
6.priority_queue 底层数据结构一般为vector为底层容器,堆heap为处理规则来管理底层容器实现。
7.set 底层数据结构为红黑树,有序,不重复
8.multiset 底层数据结构为红黑树,有序,可重复
9.map 底层数据结构为红黑树,有序,不重复
10.multimap 底层数据结构为红黑树,有序,可重复
11.hash_set 底层数据结构为hash表,无序,不重复
12.hash_multiset 底层数据结构为hash表,无序,可重复
13.hash_map 底层数据结构为hash表,无序,不重复
14.hash_multimap 底层数据结构为hash表,无序,可重复
三、容器(Container)
1、STL的容器种类
(1)序列式容器(Sequence container), 这是- .种有序(ordered) 集合,其内每个元素均有确凿的位置一-取决 于插人时机和地点,与元素值无关。如果你以追加方式对一.个集合置人6个元素,它们的排列次序将和置人次序- -致。STL 提供了5个定义好的序列式容器: array. vector、 deque、 list 和forward_ list。
(2)关联式容器(Associative container),这是-种已排序(sorted) 集合,元素位置取决于其value (或key---如 果元素是个key/value pair)和给定的某个排序准则。如果将6个元素置入这样的集合中,它们的值将决定它们的次序,和插入次序无关。STL 提供了4个关联式容器: set、 multiset、 map和multimap。
(3)无序容器(Unordered (associative) container), 这是一 种无序集合(unordered collec-tion),其内每个元素的位置无关紧要,唯一重要的是某特定元素是否位于此集合内。元素值或其安插顺序,都不影响。
2、容器类的共通操作
c1 = move(c2) //赋值,c2赋给c1
元素访问:
a、简单访问
for(auto& elem : coll){
cout<<elem;
}
b、指定位置操作的访问
for(auto pos=coll.begin(); pos!=coll.end; ++pos){
*pos = ...;
}
c、使用迭代器访问
for(iterator pos=coll.begin(); pos!=coll.end(); ++pos){
cout<<*pos;
}
3、容器提供的类型
4、序列式容器
(1)Array(其class名为array)
a、类似数组,固定大小,随机访问。
例:
array<string,5> coll = {“hello”, “world”}; //初始化
for(int i = 0; i<coll.size(); i++){
cout<<coll[i]<,endl;
}
b、Class array<>的构造函数
c、Class array<>的赋值操作
d、Class array<>元素直接访问
注:只有at()执行范围检查
e、Class array<>迭代器的相关操作
f、把array当成C-Style Array
array<char 10> a;
strcpy(&a[0], “hello”);
printf(“%s\n”, &a[0]);
//可使用data访问array的元素
strcpy(a.data(), “hello”);
printf(“%s\n”, a.data());
(2)Vector
a、类似尾部可伸缩的组数,随机访问,尾部增删方便,其他地方增删较为耗时
例:
vector<int> coll;
for(int i = 1; i<=5; i++){
coll.push_back(i);
}
for(int i=0; i<coll.size(); i++){
cout<<coll[i]<<endl;
}
注:可使用c.data()访问vector中的元素
b、容量
操作大小除了size()、empty()、max_size()外还有容量capacity()。
- 一旦内存重新分配,vector元素相关的所有reference、pointer、iterator都会失效
- 内存重新分配很耗时
法一:使用reserve()保留适当容量,避免重新分配内存。不能缩减vector的长度。
vector<int> v;
v.reserve(80);
另:shrink_to_fit可缩减容量以符合当前元素个数,但会使得reference、pointer、iterator失效
v.shrink_to_fit();
法二:初始化期间向构造函数传递额外实参,构建足够空间
vector<T> v(5);
c、构造和析构函数
d、操作
e、赋值
f、元素访问
g、迭代器
h、vector的安插和移除
i、vecto<bool>的特殊操作
例:移除与某值相等的第一个元素
vector<Elem> col;
...
vector<Elem>::iterator pos;
pos = find(coll.begin(), coll.end(), val);
if(pos != coll.end()){
coll.erase(pos);
}
例:vector的应用
#include<iostream>
#include<vector>
#include<iterator>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
vector<string> sentence;
sentence.reserve(5); //5个元素
sentence.push_back("Hello,");
sentence.insert(sentence.end(), { " how", " are", " you", " ?" });
//输出元素和空格
copy(sentence.cbegin(), sentence.cend(), ostream_iterator<string>(cout, " "));
cout << endl;
cout << "max_size: " << sentence.max_size() << endl;
cout << "size: " << sentence.size() << endl;
cout << "capaticy: " << sentence.capacity() << endl;
swap(sentence[1], sentence[3]);
//找到“ ?”插入“ always”
sentence.insert( find(sentence.begin(), sentence.end(), " ?"), " always");
sentence.back() = "!";
copy(sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
cout << endl;
//删除后两个元素
sentence.pop_back();
sentence.pop_back();
sentence.shrink_to_fit();
cout << "size: " << sentence.size() << endl;
cout << "capaticy: " << sentence.capacity() << endl;
system("pause");
return 0;
}
输出:
(3)Deque
a、类似首尾均可安插元素的数组,在首尾安插元素方便,中间安插元素则比较费时
例:
deque<float> coll;
for(int i =1; i <= 6; ++i){
coll.push_front(i*1.1); //每个元素都安插在上一个元素的前面
}
for(int i = 0 ;i < coll.size(); ++i){
cout<<coll[i]<<endl;
}
b、deque的内部结构
c、deque构造函数和析构函数
d、deque的操作函数
注: Deque的各项操作只有以下两点和vector不同:
- Deque 不提供容量操作(capacity() 和reserve())。
- Deque 直接提供函数完成头部元素的安插和删除(push_ front ()和pop_ front())。其他操作都相同,所以这里不重复。
请注意,C++11添 加了shrink. .to. fit(),那是个不具强制力(nonbinding) 的函数,负责缩小内部内存以匹配元素个数。你可能会认为shrink to_ fit()对deque没意义,因为deque本就会释放不再用到的区块内存。然而,deque 内部用来存放“指向独立区块”的所有pointer的空间,通常不会被缩小,如果用了这个函数就有可能真的被缩小。
deque的非易型操作
deque的更易型操作
e、deque和vector的区别
1)Deque与vector相比,功能上的差异如下:
●两端都能快速安插元素和移除元素(vector 只在尾端逞威风)。这些操作可以在摊提的常量时间(amortized constant time)内完成。
●访问元素时deque内部结构会多一个间接过程,所以元素的访问和迭代器的动作会稍稍 慢一些。
●迭代器 需要在不同区块间跳转,所以必须是个smart pointer,不能是寻常pointer。
●在内存区块大小有限制的系统中(例如PC系统), deque可以内含更多元素,因为它使用不止一块内存。因此deque的max_ size()可能更大。
●Deque不支持对容量和内存重新分配时机的控制。特别要注意的是,除了头尾两端,在任何地点安插或删除元素都将导致指向deque元素的任何pointer, reference 和iterator失效。不过,deque 的内存重分配优于vector,因为其内部结构显示,deque 不必在内存重新分配时复制所有元素。
●Deque会释放不再使用的内存区块。Deque 的内存大小是可缩减的,但要不要这么做,
以及如何做,由实现决定。
2)Deque的以下特性跟Vector差不多:
●在中段安插、移除元素的速度相对较慢,因为所有元素都需移动以腾出或填补空间。
●迭代器属于random-access iterator (随机访向迭代器)。
3)总之,以下情形最好采用deque:
●你需要在两端安插和移除元素(这是deque的拿手好戏)。
●无须指向(referto) 容器内的元素。
●要求“不再使用的元素必须释放”(不过C++ standard 对此无任何保证)。
Vector 和deque的接口儿乎一样,所以如果你不需要什么特殊性质,两者都可试试。
(4)List
a、类似双向链表,非随机访问,插入和删除迅速。
b、list的构造函数和析构函数
c、list的操作
list的非易型操作
list的赋值操作
d、list的访问
除front()和back()能直接访问,还可以使用range-based-for循环来访问元素。
注:range-based-for循环(C++11)
list<char> coll;
for (char c = 'a'; c <= 'z'; ++c) {
coll.push_back(c);
}
for (auto elem : coll) { //auto为自动匹配类型
cout << elem << ' ';
}
e、迭代器的相关函数
f、list的安插、移除、操作函数
g、list的特殊更易型操作
h、list异常发发生时提供的特殊保证
例:
#include<iostream>
#include<list>
#include<iterator>
#include<algorithm>
using namespace std;
void printList(const list<int> l1, const list<int> l2)
{
cout << "list1: ";
copy(l1.cbegin(), l1.cend(), ostream_iterator<int>(cout, " "));
cout << endl << "list2: ";
copy(l2.cbegin(), l2.cend(), ostream_iterator<int>(cout, " "));
cout << endl <<endl;
}
int main()
{
list<int> list1,list2;
for (int i = 0; i < 6; i++) {
list1.push_back(i);
list2.push_front(i);
}
printList(list1, list2);
//在list2中第一次找到3,再把list1转移到第一次找到的3之前
list2.splice(find(list2.begin(), list2.end(), 3), list1);
printList(list1, list2);
//将list2中的第一个元素转移到最后
list2.splice(list2.end(), list2, list2.begin());
printList(list1, list2);
list2.sort(); //排序
list1 = list2;
list2.unique(); //去相邻重复
printList(list1, list2);
//在list和list2有序的情况下,把list2转移到list1,并保证转移后还是有序
list1.merge(list2);
printList(list1, list2);
system("pause");
return 0;
}
输出:
(5)Fordward-List(C++11)
a、类似单向链表,相对list的优点是内存用来少,行动也略快。非随机访问
例:
forward_list<int> coll = { 2, 5, 6, 8, 5, 9, 4 };
coll.resize(9); //9个元素,不够补0
coll.resize(11, 99); //11个元素,(第9个后开始)不够补99
b、forward_list的约束
- 只有前向迭代器
- 不提供成员函数size()
- 没有指向最末元素的锚点,没有push_back()、pop_back()
- 增加和删除元素必须传递前一元素的位置,例如用insert_after代替insert
c、forward_list的构造函数和析构函数
d、forward_list的操作
forward_list的非更易型操作
e、forward_list赋值
f、forward_list元素访问
使用range-based for循环访问各个元素,或者使用迭代器访问
g、迭代器的相关函数
注:before_begin()和cbefore_begin()并不代表forward_list的一个合法位置,除赋值和赋值动作,对before_begin()返回值的合法操作只有++、==和!=
h、元素的安插和移除
注:如果要找出某元素并替换该元素则需要找到该元素的前一个位置,再用insert_after()插入。或者使用next()函数。
i、forward_list提供的特殊更易型操作
5、关联式容器
关联式容器由二叉树实现,在二叉树中,每个元素都有一个父节点和两个子节点,左子树的所有元素都比自己小,右子树的所有元素都比自己大。
(1)set和multiset
set:依据value自动排列,每个元素只能出现一次,不允许重复。
multiset:与set的区别:元素可以重复。
a、排序准则
- 1.必须是非对称的(antisymmetric)。
对operator <而言,如果x < y为true, 则y < x为false.
对判断式(predicate) op()而言, 如果op(x,y) 为true,则op(y ,x)为false。
- 2.必须是可传递的(transitive)。
对operator <而言,如果x < y为truey< z为true, 则x < z为true。
对判断式op()而言,如果op(x ,y)为true H.op(y ,z)为true,则op(x,z) 为true。
- 3.必须是非自反的(ireflexive)。
对operator <而言,x < x永远为false。
对判断式op()而言,op(x,x) 永远为false。
- 4.必须有等效传递性(transitivity of equivalence)。
大体意义是:如果a等Fb且_b等于c,那么a必然等于c。
这意味着对于操作符<,若!(a<b) && ! (b<a)为truel!(b<c) & !(c<b) 为true,那么!(a<c) && !(c<a) 亦为true。
这也意味着对于判断式op(),若op(a,b). op(b,a)、 op(b,c) 和op(c ,b)都为false,那么op(a,c)和op(c,a)为false。
注意,这意味着你必须区分less 和equal,一个像operator <=这样的准则并不满足这个条件。
根据这些性质,排序准则也被用来检查等效性(equivalence)。 也就是说, 两个元素如果没有任何一个小于另一个(或如果op(x,y)和op(y,x)都取得false),则它们被视为重复。
Multiset的等效元素的次序是随机但稳定的(random but stable)。因此C++11保证安插和抹除(erasure) 动作都会保存等效元素的相对次序。
注:排序准则也被用来检验元素相等性:
if(! (elem1<elem2 || elem2<elem1))
b、set和multiset的构造函数和析构函数
其中的set可为下列形式
c、set和multiset的非更易型操作
d、set和multiset的查找操作函数
e、赋值
f、set和multiset的迭代器相关操作
g、set和multiset的安插和移除
注:inset()和emplace()的返回值不同;
set:
pair<iterator,bool> insert(const value_type& val);
iterator insert (const_ iterator posHint, const value_ type& val) ;
template <typename... Args> pair<iterator, bool> emplace (Args&&... args);
template <typename... Args> iterator emplace_ ,hint (const_ iterator posHint,
Args&... args);
multiset:
iterator insert (const value_ type& val) ;
iterator insert (const_ iterator posHint, const value_ type& val) ;
template <typename... Args> iterator emplace (Args&... args);
template <typename... Args> iterator emplace_ hint (const_ iterator posHint,
Args&... args);
(2)map和multimap
map:每个元素都是key/value pair(键值对),其中key是排序准则的基准。每个key只能出现一次,不允许重复。map可被视为一种关联式数组,即”索引可为任意类型”的数组。
multimap:与map的区别:元素可以重复,即multimap允许有相同的key。multimap可被当做字典使用。
注:可将set视为一种特殊的map:元素的value等同于key。
a、map和multimap构造函数和析构函数
注:其中map可为下列形式
b、map和 multimap的非更易型操作
c、map和 multimap的特殊查找操作
d、map和multimap的赋值
e、map和multimap的迭代器相关操作
f、map和multimap的元素的安插和移除
h、将value传入map和multimap内:
1)运用value_type。
value_type是容器本身提供的类型定义
std::map<std:: string , float> coll;
...
coll.insert(std::map<std::string, float>::value_type(“ott”, 66.2) );
或
coll.insert(decltype(coll)::value_type(“ott”, 66.2));
2)运用pair<>
std::map<std:: string , float> coll;
coll.insert(std::pair<std::string, float> (“ddd”, 2225.5));
3)运用make_pair()
std::map<std:: string , float> coll;
...
coll.insert(std::make_pair(“dd”, 22.2));
h、map的直接元素访问操作
6、无序容器
无序容器常以hash table实现出来,内部结构是一个有linked list组成的array。通过某个hash函数的运算确定元素落于这个array的位置,hash函数运算的目标是:让每个元素的落点(位置)有助于用户快速访问。
(1)STL中无序容器
1)unordered set:无序元素的集合,每个元素只允许出现一次。
2)unordered multiset:与unordered set的区别就是允许元素重复。
3)unordered map:元素都是key/value pair。每个key只可出现一次,可作为关联式数组。
注:关联式数组:key/value pair中“索引并非整数”的array。
4)unordered multimap:和unordered map的区别是允许key重复。
(2)无序容器的构造函数和析构函数
(3)无序容器unord的所有可能类型
(4)布局操作
(5)无序容器的非更易型操作
(6)无序容器的特殊查找操作
(7)无序容器的赋值操作
(8)无序容器的迭代器操作
(9)无序容器的安插和移除操作
(10)bucket(桶)接口
(11)各容器的使用时机
●默认情况下应该使用vector, Vector的内部结构最简单,并允许随机访问,所以数据的访问十分方便灵话,数据的处理也够快。
●如果经常要在序列头部和尾部安插和移除元素,应该采用deque。 如果你希望元素被移 除时,容器能够自动缩减内部内存用量,那么也该采用deque。此外,由于vector通常采用一个内存区块来存放元素,而deque采用多个区块,所以后者可内含更多元素。
●如果需要经常 在容器中段执行元素的安插、移除和移动,可考虑使用list.。List 提供特殊
的成员函数,可以在常量时间内将元素从A容器转移到B容器。但由于list不支持随机访问,所以如果只知道list的头部却要造访list的中段元素,效能会大打折扣。
和所有“以节点为基础”的容器相似,只要元素仍是容器的一部分,list 就不会令指向那些元素的迭代器失效。Vector 则不然,一旦超过其容量,它的所有iterator,pointer和reference都会失效:执行安插或移除动作时,也会令一部分iterator. pointer和reference失效。至于deque,当它的大小改变,所有iterator. pointer 和reference都会失效。
●如果你要的容器对异常的处理使得“每次操作若不成功便无任何作用”,那么应该选用list (但是不调用其assignment操作符和sort(),而且如果元素比较过程中会抛出异常,就不要调用merge()、remove(). remove. .if() 和unique(),或选用associative/unordered容器(但是不调用多元素安插动作,而iL如果比较准则(comparison criterion]的复制赋值动作可能抛出异常,就不要调用swap()或erase())。
●如果你经常需要根据某个准则查找元素,应当使用“依据该准则进行hash”的unordered
set或muliset,然而,hash 容器内是无序的,所以如果你必项依赖元素的次序(order),应该使用set或multiset,它们根据查找准则(search criterion)对元素排序。
●如果想处理 key/value pair,请采用unordered (multimap)。如果元素次序很重要,可采用
(multi)map。
●如果需要关联式数组(associaive array),应采用unordered map。如果元素次序很重要,
可采用map。
●如果需要字典结构,应采用unordered mulimap, 如果元素次序很重要,可采用mul-
Timap。
(12)STL容器能力一览表
更多推荐
所有评论(0)