C++学习（2）STL八股文

标签：容器八股文函数迭代 STL C++ 算法 vector

1、STL实现原理及其实现

STL提供了六⼤组件，彼此之间可以组合套⽤，这六⼤组件分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器。

STL六⼤组件的交互关系：
a. 容器通过空间配置器取得数据存储空间；
b. 算法通过迭代器存储容器中的内容；
c. 仿函数可以协助算法完成不同的ᒽ略的变化；
d. 适配器可以修饰仿函数。

1.1 六⼤组件

1.1.1 容器

各种数据结构，如vector、list、deque、set、map等，⽤来存放数据，从实实现角度来看，STL容器是⼀种class template。

1.1.2 算法

各种常⽤的算法，如sort、find、copy、for_each。从实现的᥯度来看，STL算法是⼀种function tempalte。

1.1.3 迭代器

扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是⼀种将operator* , operator-> , operator++ , operator– 等指针相关操作予以以重载的class template。所有STL容器都附带有⾃⼰专属的迭代器，只有容器的设计者才知道如何遍历⾃⼰的元素。原⽣指针(native pointer)也是⼀种迭代器。

1.1.4 仿函数

⾏为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是⼀种重载了operator()的class 或者class template

1.1.5 适配器

⼀种⽤来修饰容器或者仿函数或迭代器接⼝的东西。STL提供的queue 和 stack，虽然然看似容器，但其实只能算是⼀种容器配接器，因为它们的底部完全借助deque，所有操作都由底层的deque供应。

1.1.6 空间配置器

负责空间的配置与管理。从实现角度看，配置器是⼀个实现了动态空间配置、空间管理、空间释放的class tempalte。⼀般的分配器的std:alloctor都含有两个函数allocate与deallocte，这两个函数分别调⽤operator new()与delete()，这两个函数的底层⼜分别是malloc()和 free();但是每次malloc会带来格外开销（因为每次malloc⼀个元素都要带有附加信息）

1.2 STL的优点

STL 具有⾼可重⽤性，⾼性能，⾼移植性，跨平台的优点。

1.2.1 ⾼可重⽤性

STL 中几乎所有的代码都采⽤了模板类和模版函数的⽅式实现，这相⽐于传统的由函数和类组成的库来说提供了更好的代码重⽤机会。

1.2.2 ⾼性能

如 map 可以⾼效地从⼗万条记录⾥⾯查找出指定的记录，因为 map 是采⽤红黑树的变体实
现的。

1.2.3 ⾼移植性

如在项⽬ A 上⽤ STL 编写的模块，可以直接移植到项⽬ B 上。

STL 的⼀个重要特性是将数据和操作分离
数据由容器类别加以管理，操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”,以使算法可以和容器交互运作。

2、pair容器

保存两个数据成员，⽤来⽣成特定类型的模板。
使⽤： pair<T1, T2>p;
数据成员是public，分别是first和second,可以直接访问；其中map的元素是pair，pair<const key_type，mapped_type>，可以⽤来遍历关联容器；

map<string,int>p;
auto map1 = p.cbegin();
while(map1 != p.cend())
{
 cout<<map1->first<<map1->second<<endl;
 ++map1;
}

对map进⾏插⼊，元素类型是pair：

p.insert({word, 1});
p.insert(pair<string, int>(word, 1));

insert对不包含重复关键字的容器，插⼊成功返回pair<迭代器，bool>迭代器指向给定关键字
元素，bool指出插⼊是否成功。

vector<pair<char, int>>result(val.begin(), val.end());
sort(result.begin(), result.end(),[](auto &a, auto &b){
 return a.second > b.second;
});

2、vector容器

2.1 底层实现

Vector在堆中分配了⼀段连续的内存空间来存储元素

a. 三个迭代器

first ：指向的是vector中对象的起始字节位置
last ：指向当前最后⼀个元素的末尾字节
end ：指向整个vector容器所占⽤内存空间的末尾字节

template <class T>
class vector
{
public:
    ~vector()
    {
        delete first;
        first = last = end = nullptr;
    }
private:
    T* first;         //顺序表的头
    T* last;        //顺序表有效长度位置
    T* end; //顺序表末尾
};

b. 三个迭代器

如果集合已满，在新增数据的时候，就要分配⼀块更⼤的内存，将原来的数据复制过来，释放之前的内存，在插⼊新增的元素所以对vector的任何操作，⼀旦引起空间重新配置，指向原vector的所有迭代器都会失效。

标签：容器,八股文,函数,迭代,STL,C++,算法,vector
From： https://www.cnblogs.com/xingyuchen/p/17148099.html