BluetoothKiBluetoothKi08-22 02:01

C++STL

STL中容器的常用用法https://blog.csdn.net/weixin_41162823/article/details/79759081

特此感谢侯捷大大(男神)

0、标准库定义在namespace中,因此在使用时需要将库利用include引入当前project中,并用using namespace std表明使用此命名空间的中的函数(目的是防止其和其他空间中的同名函数在使用时冲突)(其中namespace为逻辑上的#include为物理上的因此均需要说明)

https://blog.csdn.net/u013719339/article/details/80221899

1、命名空间:将我们所写函数、类和模板进行再次封装到一个新的命名空间中防止与其他内容冲突。c++标准库存储在命名空间std中。

2、标准库重要网站:CPlusPlus.com CppReference.com gcc.gnu.org 。

3、STL六大部件:容器、分配器、算法、迭代器、适配器、仿函式。//设计方式有别于OO

(1)容器解决内存的事情

(2)分配器用于支持容器

(3)算法:为容器中独立出来的函数

(4)迭代器为一种泛化的指针

(5)仿函数作用类似于函数

(6)迭代器适配器

4、vector<int,allocator<int>> vi(ia,ia+6);//int 为vector中的类型,allocator用于分配内存,分配的类型为int

bind2nd(less<int>(),40)//其中less<int>()为一个仿函数,作用为判断A,B中的最小值,bind2nd的作用为强行将第二参数绑定为40.其目的为判断此数是否小于40.其中bind2nd为适配器。

5、前闭后开区间中c.begin()表示容器中的第一个元素,c.end()表示容器中最后一个元素的后一个元素。

c.end()禁止解引用

6、

Container<T> c;//声明容器
。。。
Container<T>::iterator ite = c.begin();//初始化迭代器
for(;ite != c.end(); ++ite)
  ...

7、c++11中

其中auto elem : vec为利用elem去遍历容器vec中的每一个元素(或者理解为取出每一个元素)

当auto& elem : vec为利用elem取出容器中每一个元素的引用。auto根据等号的的右手边去推倒出元素的类型(除等号右手边外也可是程序的上边)

8、容器类别

(1)循序式:Array(内存固定,不可扩充),Vector(尾部可扩充),Deque(收尾均可扩充),Listt(双向链表),Forward-List((单向链表)

(2)Key—Value:Set与Map(底部由红黑树实现)。Map(每个节点有key与value)Multimap(key可以重复),Set(key与value一致)Multiset(key可以重复)

(3)不定序:HashTable:

注:将测试程序用namespace包裹起来,在每个namespace上重新引入一遍头文件,在定义变量的行不进行缩进

注:abort()//当程序出现异常时,终止程序

一、循序式容器

9、Vector

(1)Vector在进行空间扩展时是成倍增长的。(增长时找到另外一块二倍的空间并把当前空间中的数据移动过去)

(2)其中v.size()为容器中元素的个数

(3)v.capacity()为容器的容量

(4)v.data()为容器的起始地址的值;

10、List

(1)容器本身自带sort()//排序函数;

11、Forward_List

(1)不提供back()、size()函数;

(2)c++11中的规定;

12、deque(其特点为分段连续)

(1)deque采用的分段连续中的不同段之间利用指针连接,且段间的++功能的实现方式为运算符重载;

13、其中queue与stack底部支撑由deque完成(在技术称之为容器适配器,也可以称之为容器)

(1)不提供iterator(防止其破坏容器结构特点)

二、Key_Value式容器(其底层由红黑树组成)

1、multiset(key-value一致)(其底层由红黑树组成)

(1)安插元素的函数为insert()

(2)自带find()

2、multimap(其底层由红黑树组成)

(1)key-value不一致

(2)其他与multiset相似

(3)插入元素的函数为insert(pair<key的类型,value的类型>(i,buf));

(4)不可以利用下标进行元素的插入;

3、Unordered_multiset

(1)底层结构为hashtable :

4、unordered_multimap(与unordered_multiset相似)

5、set(key独一无二)

6、map(key独一无二)

(1)可以通过下标进行元素插入,例如:c[i] = string(buf);

三、分配器(allocator)

四、STL采用模板的思想进行编写(而模板是采用GP(不同于OOP)的思想)

1、OOP企图将datas与methods关联在一起

2、GP(Generic Programming)却是将datas和methods分开来

3、运算符重载:其中"::", ".", ".*", "?:"不可以被重载。

4、模板(类与结构体的区别单(需要单独查找))

(1)类模板

a.类模板的定义及使用

b.函数模板的定义及使用

(2)特化

(3)偏特化

a.若模板定义两个参数时,对其中一个进行特化则成为偏特化。

b.若模板中定义的1个或若干个参数时,对其中的所有T的指针形式进行特化仍然属于偏特化的一种。

五、分配器

(VC与BC编译器中)operator new() 和 malloc();

(1)allocator函数中allocate和deallocate调用operator new()与operator delete(),而operator new()与operator delete()中调用mlloc()与free()来进行内存的分配。

(2)类名+()表示该类的临时对象例如allocator<int>(),

(3)malloc()进行内存分配时会返回一个指针,并在此内存的头尾位置记录内存的大小

六、容器

利用缩进的方式表达基层与衍生的关系。

侧面淡蓝色的部分表示在每个容器对象所占内存的大小。

七、list(双向)

(1) 上方的圆圈处需要注意的为:*this为拷贝构造函数的参数其*表示指针的意思,而非是调用operator* ()(解引用的运算符重载)

(2)下方的圆圈处表示list`s iterator对i++与++i 的运算符重载模仿的是int类型。因此++i 的运算符重载函数中返回值为引用

而i++运算符重载函数返回值为同类型的一个拷贝的数值,因为在int型中++(++i)正确,而(i++)++错误。

(3)为区分++i与i++的操作符重载函数则operator++()为i++,operator++(int)为++i,++操作符重载函数里的参数无具体意义。

(4)list结构如下图其范围为前闭后开(灰色部分为end())

(5)G4.9版的list对象的大小为8,其大小为其+父类大小

八、Iterator需要遵循的原则

1、iterator必须列出五种相关类型

(1)iterator_category(迭代器的类别)

(2)value_type(iterator指向的值)

(3)pointer

(4)reference

(5)difference_type(两个iterator间的长度)

2、利用若算法中传入的是非class 的指针时利用trains回答上诉五个问题(下方的I为某类iterator或者指针)

九、Array

十、容器deque(几乎所有的容器均维护两个指针begin()和end())

1、注(iterator中的first指的缓存中的第一个元素的地址,last指的是缓存中最后一个元素的下一个地址)

deque中的insert(),当要插入的位置既不是投也不是尾的时候,insert的辅助函数会判断这个位置是靠前还是靠后,如果靠前这移动前面的元素进行元素插入,如果靠后则移动后面的位置进行元素插入。

2、如何模拟连续空间

(1)deque iterator中的“-”操作符的重载

(2)+=、+操作符重载

(3)queue和stack底层可以选用list或者deque。

十一、容器rb_tree(红黑树)

(1)其中insert_unique()表示插入的key不允许重复,insert_equal()表示key允许重复。

(2)size_type是一种表示字符或者容器容量大小的一种类型。

注意:复习:is-a

红黑书中的关机的五个数据:key,value,keyofvalue(如何从value中获取key,(由于key和打data构成了value)),campare(比较大小的方式),Alloc(分配器)。

十二、容器set,multiset(区别为key是否可以重复),map,multimap(区别同set)

1、set

(1)、排序的依据key的大小。

(2)、set容器的底层结构为红黑树

(3)set的所有操作,都呼叫底层的t(类型为红黑树)的操作因此set也可看做container adapter(容器适配器)。

2、map的底层结构

(1) 注:mutimap不可用[]做insertion。

(2)map,独特的operator[](其作用为如果map中存在中括号中要找的元素则返回正确元素,如果没有则在相应的位置插入默认值并返回)

十三、hashtable(散列表)

1、当元素个数比篮子的个数多时,需要将这一列打撒。

2、通常采用素数作为篮子的个数,当需要扩充时一般扩充为当前篮子个数的两倍附近的素数

3、

HashFcn表示如何将要存入容器中的object转化数字(key),ExtractKey表示如何将存储在容器的一包东西中抽取出key,例如从pair中找到其first,EqualKey表示如何比较两个对象之间的大小。上诉三个可能为函数,类或者其结构体,其对象的大小理论上为0(由于其中不存放具体数据只是对对数据进行处理),实际上为1(实际上不可能为0(c++规定空类的大小不为0,深度探索c++对象模型中是这样说的:
那是被编译器插进去的一个char ,使得这个class的不同实体(object)在内存中配置独一无二的地址。
也就是说这个char是用来标识类的不同对象的)).

4、hashtable中的node

上图中的cur(上图中cur标线出现了错误)指向数据在单个篮子中的具体位置,ht指向其在哪个篮子。

5、

6、标准库中的HashFunc

里面不提供std::string的偏特化

6、hashcode(一般方法为key%n)

注意:

1、c++11以前称为hash_set,hash_multiset,hash_map,hash_multimap,c++11将其变更为unordered_set,unordered_multiset,unordered_map,unordered_multimap。

2、当元素个数大于篮子的个数时,将篮子进行扩充。

十四、算法

从语言层面算法为

1、算法、容器、迭代器间的关系

(1)Algorithms看不见Containers,对其一无所知;所以,它所需要的一切信息都必须从Iterators取得,而Iterators(Containers供应)必须能够回答Algorithm的所有提问,才能够搭配该Aglorithm的所有操作。

(2)类型()表示产生一个临时对象,例如array<int,10>::iterator() //其中array<int,10>::iterator为一个类型(因为iterator时array容器中的一个成员变量的类型,因此其整体也表示一个类型)。

(3)各个容器的iterators的iterator_category(迭代器根据iterator_category进行分类)

2、容器iterator中iterator_category的实现方式为:

线框处为公有继承。

3、iterator_category对算法的影响

(1)不同类型的迭代器对两个迭代器间距离的计算

(2)不同类型的迭代器对迭代器前进的计算

(3)迭代器的分类对底层copy()效率的影响

注意:复习拷贝赋值和拷贝构造

(4)迭代器的分类对底层__unique_copy()效率的影响

注意区分OutputIterator与ForwardIterator

(5)具体算法accumulate,意义为累计运算

(6)replace //目的为在一定范围查找与输入的旧值相同的元素,将其替换为新值。

(7)count, //统计数字

(8)find//查找元素

(9)sort//查找

注意:sort()中要求迭代器为random的,而list与forward_list无法实现random,因此对其排序时应调用list与forward_list的自带成员函数sort()。

(10)关于rbegin(),rend()

(11)binary_search //使用前数据应该是已经排好序的

十五、仿函数

1、仿函数为一个class进行小括号的操作符重载

十六、函数适配器

注:typename:由下图可知operation为模板参数,然而在编译阶段编译器尚且不知道operation为何物,因此typename 的作用为告知编译器operation为一个类。

2、not1

3、新型适配器bind

(1)std::bind可以绑定function,function objects(仿函数),member functions(_1必须是某个object地址),data members(_1必须是某个object地址)。

(2)

(3)reverse_iterator

注:对现有的东西进行二次加工或者包装

(4)迭代器适配器 inserter

利用对“=”的操作符重载

(5)ostream_iterator(补充输入输出流的知识)

(6)istream_iterator

在istream_iterator创建的是时候就已经开始读取第一个数了

十七、tuple

十八、

1、注意:查看拷贝构造函数、辅助构造函数方面的知识,C++11

(什么情况下会引起拷贝构造函数呢https://zhidao.baidu.com/question/2117421138756067467.html

拷贝构造函数为:深拷贝(不仅拷贝指针还拷贝指针所指向的内容)。

moveable(移动构造函数):创建新的指针指向要拷贝的内容,并且删除指向此内容的原指针

2、moveable 测试

如何在实际使用stl是调用string中的moveable

程序之家二维码

000
评论