Elvis · 个人站
文章 分类 标签 关于
Elvis · 个人站

目录

STL源码剖析

   约 3835 字   预计阅读 8 分钟  收录于 C++

STL

  • 泛型编程 –> 模板 –> STL几乎全是模板
  • <cstdio>与<stdio.h>的不同在于cstdio将函数放在了命名空间std中，而stdio.h放在了全局命名空间中。(命名空间：避免命名冲突)
  • STL六大部件：容器、算法、迭代器、分配器、仿函数、适配器。容器由分配器来分配和管理内存，迭代器充当容器和算法之间的桥梁。仿函数(又称函数对象)，是重载了()运算符的类，在STL中一般配合算法使用。

/images/stl/components.png

容器

  1. 序列式容器
    1. array
    2. vector
    3. deque/queue/priority_queue
    4. list/forward_list
  2. 关联式容器
    1. set/multiset/unordered_{set,multiset} 红黑树
    2. map/multimap/unordered_{map, multimap} 散列表

c++分配内存用new, 而new使用operator new(),而前者使用malloc()，malloc使用系统提供的内存分配系统调用
释放内存用delete,其调用operator delete(),前者使用free()

array

array<int,10> : size,empty,front,back,data(数组地址)

/images/stl/contain.png

vector

三个指针：start,finish,end_of_storage
无空间后成两倍扩充

push_back(),pop_back(),erase(),insert(),front(),back()

deque

成员：vector、两个迭代器(每个迭代器含有4个元素)
特点：内部分段连续，对外呈现连续空间，可随机访问;插入一个元素时，判断插入的位置距离头部近还是距离尾部近，若距离头部近，则移动到头部之间的元素，之后再插入，反之则移动到尾部之间的元素
函数：下标访问[]、front、back、push_back、push_front、pop_front、pop_back

/images/stl/deque.png

stack && queue

用deque或list实现，另外stack还可选择vector来实现
stack:push、pop、top
queue:push、pop、front、back

list & forward_list

都只有一个指针(指向节点)

map/multimap set/multiset

红黑树

是一种二叉查找树，黑节点平衡树，平衡二叉树(AVL)也是一种二叉查找树，但其平衡条件更严格(左右子树高度差不大于1)
特点：

  1. 每个节点要么是黑色，要么是红色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL）是黑色。
  4. 每个红色结点的两个子结点一定都是黑色。
  5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

set、map: insert、erase、find、count、lower_bound、upper_bound、equal_range、begin、end、size、empty
其中只有map可使用下标运算符[]

  1. 优先使用容器自己的算法，如map.find而不是find
  2. map中即使没有插入元素，但只要访问不存在的元素如if (mp[3] == 1)，则便会自动插入mp[3] = 0
  3. map中的元素是自动按key升序排序，所以unordered_map才叫未排序map
  4. multimap没有[]运算符，所以插入应使用mp.insert(make_pair(key,value))，访问应该先判断是否有元素和有几个，然后再访问
mp.count(key)
auto begin = mp.lower_bound(key) //指向k的第一个元素，若不存在则指向第一个大于k的元素或end
auto end = mp.upper_bound(key)   //指向k的最后元素的下一个元素或end
for (auto it = begin; it != end; it++) {
    cout << it.first <<it.second << endl;
}

unordered_map/unordered_multimap unordered_set/unordered_multiset

哈希表

/images/stl/hashtab.png

容器初始大小53,当元素个数超过容器容量就扩容，扩容后的容量为前一个素数两倍大小附近的素数，其中素数是从硬编码的素数表中查找的，而不是实时计算
STL中的hash算法：对于int、char等整数类型，直接返回其数值；对于字符串则为res = 5*res + c insert、erase、find、count

string

就是字符类型的vector，支持迭代器，但更多地是使用下标来操作

substr、find、insert、erase、replace、push_back、pop_back、c_str、find_first_of、find_last_of、find_first_not_of、find_last_not_of
下标访问[]、string::npos
stoi,stol,stoll,stof,stod,to_string()

find、find_first_of区别：对于字符的查找两者没有区别，但对于字符串的查找则不同

  • find(s): 查找第一次出现字符串s的位置
  • find_first_of(s): 查找字符串s中任意一个字符第一次出现的位置，故find_first_of是查找字符的

迭代器

输入、输出、前向、双向、随机

模板

  1. 特化

    template<>
class Test<int> {
    //...
}

  2. 偏特化 偏特化有两种形式，一种是在个数上，一种是在范围上

    //1 个数上
template<typename T>
class Test<int, T> {
    //...
}

//2 范围上
template<typename T>
class Test<T*> {
    //...
}
在上述第二中形式即在范围上偏特化时，不等于如下形式，因为typename只是一个字符串符号，即T*只是一个整体标记
typename<typename T*>
class Test {
    //...
}

traits

原因：因STL中算法与容器相分类，所以算法在处理数据时需要根据传入的迭代器知道容器中元素的类型等信息。
这时分两种情况：

  1. 迭代器是类类型
  2. 迭代器是普通指针

类类型简单，直接在类中定义typedef就行，如下图： /images/stl/traits1.png
但当传入的迭代器是个普通指针时，就不能像上述方法那样确定类型了，此时就需要traits了
实现：通过新设计一个iterator_traits模板类进行辅助确认,用到了模板的偏特化
/images/stl/traits2.png
所以，当迭代器是类和指针都可以按以下方式进行类型确认了
/images/stl/traits3.png

算法

读：
find(begin,end,val)、count(begin,end,val)、count_if(begin, end, 条件)、accumulate(begin,end,初始值sum)、equal(v1.begin,v1.end,v2.begin)、min_element(begin,end)返回迭代器

写：
fill(begin,end,val)、replace(begin,end,oldval,newval)
unique(begin,end)把多余的重复元素放在末尾，返回指向不重复区域后一个的位置

sort(words.begin(),words.end());
auto end_unique = unique(words.begin(),words.end());
words.erase(end_unique,words.end());

对于算法中的条件函数优先使用lambda

杂记

函数

普通函数、lambda表达式、重载了()的类

前++和后++运算符重载

int& operator++() //前++ int operator++(int) //后++ 因为前++返回引用，所以可以++++i，相当于++(++i);而后++返回值，所以i++++出错

#if与#ifdef与#if defined()区别

#if defined()是更为强大的#ifdef，主要体现在多条件选择的情况下，但在条件判断下无区别

//#if defined()对多条件进行判断
#if defined(xx1)
...
#elif defined(xx2)
...
#elif defined(xx3)
...
#endif

//#ifdef最多只能对两个条件进行判断
#ifdef xx1
...
#else
...
#endif

#ifdef只关心宏是否定义，而不管值的真假，而#if则兼顾两者

#define XXX 0

// 第一段条件编译
#ifdef XXX
逻辑1
#else
逻辑2
#endif

// 第二段条件编译
#if XXX
逻辑1
#else
逻辑2
#endif

第一段条件编译：逻辑1会被编译进去,第二段条件编译：逻辑2会被编译进去

auto关键字、lambda表达式、for_each()

auto可以在声明变量时根据变量初始值的类型自动为此变量选择匹配的类型，一般用于lambda表达式和较为复杂的数据类型(如迭代器))
lambda表达式：

// 指明返回类型
auto add = [](int a, int b) -> int { return a + b; };
// 函数体只有一条return语句才能自动推断返回类型
auto multiply = [](int a, int b) { return a * b; };

int sum = add(2, 5);   // 输出：7
int product = multiply(2, 5);  // 输出：10

//若想对外部变量进行操作需将外部变量通过[]传入lambda表达式中
//传入方式可通过值传递或引用传递
auto print = [sum](){cout << sum;};  //值传递
auto print = [&sum](){cout << sum;};  //引用传递
auto print = [=](){cout << sum;};     //将外部变量全部按值传入
auto print = [&](){cout << sum;};     //将外部变量全部按引用传入
auto add = [](int a, int b) -> int { return a + b;};  //不访问外部变量
注意：捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和它所在函数之外声明的名字  

 在定义lambda表达式时，本质上是定义了一个重载了()的类，即仿函数。值捕获方式会在类中对应定义一个const成员(对外不影响，在内不能改变)，而引用捕获方式会在类中定义一个引用成员(对内和外有着同步影响)，而加了mutable修饰的值捕获方式会定义一个普通成员(对外不影响，在内能改变)
int val = 1;
auto f = [val]()mutable{return ++val;};
cout << f();  //2
cout << f();  //3
cout << val;  //1

for_each:

vector<int> nums{3, 4, 2, 8, 15, 267};
//遍历访问元素，对元素的操作以后面的函数表示
for_each(nums.begin(), nums.end(), [](int &n){ n++; });
对容器写操作
for_each(vec2.begin(), vec2.end(), [](auto& e) -> int& {return ++e;});
对容器读操作
for_each(vec2.begin(), vec2.end(),[](const auto& e){cout << " " << e;});

for (const auto& e : vec)

应使用引用来避免调用每个元素时的拷贝构造函数和析构函数，从而避免非必要拷贝和临时对象,下面的move函数也是这个作用

explicit关键字

禁止函数的隐式转换

move()函数

move(a) 将a转换为右值引用，进行内存转移，从而避免了临时对象

例如：
map.insert(move(i++)) ， i++是右值，但是注意i是左值

右值引用的两个特点：

  1. 右值引用的对象，是临时的，即将被销毁
  2. 右值引用的对象，不会在其它地方使用

左值是存在于创建的对象中的，而右值是临时产生的，比如：

int a = 1;  //a为左值，存在于int类型的对象a中
a = a+1;    //a+1是右值，因为其值为2，但是没有对象来存储它，是个临时变量

noexcept

告诉编译器函数不抛出异常，从而在生成代码时可不进行异常种类判断来处理错误，进而优化代码
但是如果一但发生异常，就会终止程序，所以在使用之前一定要确保函数的确不会抛出异常

推荐使用noexcept的情况：

  1. move constructor/assignment operator 如果不会抛出异常，一定用noexcept。
  2. destructor一定用noexcept

mutable

字面意思：可变的

用来修饰变量，然而变量天生可变，所以这里用来修饰的变量是位于const修饰的函数内的或按值传递的lambda表达式中的

shared_ptr & unique_ptr & week_ptr

智能指针：自动释放资源，一定程度上避免了内存泄漏

  1. shared_ptr

参考
shared_ptr<string> p(new string("hello"))
shared_ptr在栈中，当其中程序运行完销毁栈中元素时，shared_ptr为0即指向对象的个数为0时就会自动销毁对象释放空间

错误使用：循环指向

  1. unique_ptr

  2. week_ptr

允许“共享但不拥有”某对象

更新于 2019-10-27
 Tags
返回 | 主页