C++ STL

发表于 更新于 分类于 阅读次数：

…

六大部件

容器：占用内存，存放数据

分配器：为容器分配内存，管理内存

算法：关于容器的通用算法

迭代器：算法访问容器的桥梁

适配器：迭代器，容器，仿函数适配器，对他们做转换

仿函数：给自定义类准备的基本方法

基本使用

1
2
3
4
5
6
7
vector<int> vec{1,2,3};
vector<int>::iterator iter = vec.begin();
// vec.end() 指向最后一个元素的下一个位置
for(auto item : vec){}
for(auto& item : vec){}
for(auto item : {1, 2, 3}){}

OOP vs GP

OOP，面向对象编程，将数据和相应方法捆绑在一起。
GP，将数据和方法尽量分开。

容器分类

序列容器

Array 不可扩充的数组

Vector 单向扩充数组

Deque 双向扩充数组

List 双向循环链表

Forward-List 单链表

Slist 非标准 等同于FList <ext\slist>

Priority Queue 优先队列，底层是堆

Heap 堆

Stack 栈

Queue 队列

关联容器

Set 、Multiset 集合

Map 、Multimap 映射

二者都是红黑树，适用于大量查找。

无序容器

Unordered Set 集合

Unordered Map 映射

使用哈希表实现。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
std::array<int, 5> arr{1, 2};
std::vector<int> vec{1, 2};
std::list<int> li{1, 2};
__gnu_cxx::slist<int> sl{1, 2};
std::deque<int>;
std::stack<int>;
std::queue<int>;
std::multiset<string>;
std::multimap<string, string>;
std::unordered_multiset<string>;
std::unordered_multimap<string, string>;
std::set<string>;
std::map<string, string>;
std::hash_set;
std::hash_set;
std::hash_multiset;
std::hash_multimap;

容器

Array

没有构造和析构函数。没有用malloc。模拟了原生的数组。

1
2
3
4
5
array<int, ARRAY_SIZE> arr;
arr.size();
arr.front();
arr.back();
arr.data();  // 数组内存地址

Vector

不能原地扩充，必须复制。
容量不足时，将2倍扩充。
包含3个指针：数据开始，数据结尾，存储空间结尾。
由于扩充时进行了拷贝，因此会大量调用拷贝构造函数和析构函数。

1
2
3
4
5
6
7
vector<int> vec;
vec.size();
vec.front();
vec.back();
vec.data();
vec.capacity();  // 扩充前容量
vec.push_back();

List

使用双向链表迭代器，底层是双向链表。双向链表中有一个空结点（end指向）。
GNU2.9中，内部包含一个结点指针，结点中包含前后结点的指针。
GNU4.9中，改为更复杂的机制，List基类包含2个指针，子类继承后加入结点数据。

1
2
3
4
5
6
list<int> li;
li.size();
li.max_size();
li.front();
li.back();
li.sort();  // 自己有sort，就用自己的

Deque

每次扩充一个buffer，存在map中。

1
2
3
4
5
deque<int> deq;
deq.size();
deq.max_size();
deq.front();
deq.back();

Forward-List

含有头节点。

1
2
3
4
5
6
forward_list<int> fl;
// fl.size();  // 没有
fl.max_size();
fl.front();
fl.push_front();  // 没有push_back
// fl.back();   // 没有

SList

等同于forward-list，是非标准库结构，但是被编译器实现。

1
2
#include <ext/slist>
slist<int> sl;

Stack

底层是 deque

1
2
3
4
5
stack<int> st;
st.size();
st.top();
st.pop();
st.push();

Queue

底层是 deque

1
2
3
4
5
6
queue<int> que;
que.size();
que.front();
que.back();
que.pop();
que.push();

Multiset

1
2
3
4
5
multiset<int> ms;
ms.size();
ms.max_size();
ms.insert();
ms.find();

Multimap

1
2
3
4
5
multimap<string, int> mm;
mm.size();
mm.max_size();
mm.insert(pair<string, int>("1", 1));
auto pItem = mm.find(); // 迭代器

Unordered Multiset C++11

底层为哈希表，篮子数比元素多

1
2
3
4
5
6
7
8
9
10
unordered_multiset<int> ums;
ums.size();
ums.max_size();
ums.bucket_count();  // 哈希表篮子数
ums.bucket_size(int i);  // 哈希表篮子链表节点数
ums.load_factor();   // 载荷因子
ums.max_bucket_count();
ums.max_load_factor();
ums.insert();
ums.find();

Unordered Multimap C++11

底层为哈希表

1
2
3
4
5
unordered_multimap<string, int> umm;
umm.size();
umm.max_size();
umm.insert(pair<string, int>("1", 1));
umm.find(); // 迭代器

Set

Map

1
2
3
map<string, int> mp;
mp["key"]=val;
mp.insert(pair<string, int>("key", val));

Unordered Set

Unordered Map

Exception

1
2
3
4
5
// 包含于 stdexcept
try{}
catch(exception &e){e.what();}
// 包含于 stdlib
abort()

分配器 Allocator

基本用法

头文件

1
2
3
4
5
6
7
8
9
10
#include <memory>  // 标准分配器 std::allocator
#include <ext\array_allocator.h>
#include <ext\mt_allocator.h>    // 多线程 分配器
#include <ext\debug_allocator.h>
#include <ext\pool_allocator.h>  // 内存池 分配器
#include <ext\bitmap_allocator.h>
#include <ext\malloc_allocator.h>
#include <ext\new_allocator.h>

list<string, __gnu_cxx::__pool_alloc<string>> c;

每个容器都有默认分配器，也可以自定义分配器。

1
2
3
4
5
6
7
8
vector<int, allocator<string>> vec;  // 默认分配器 在 <memory>
vector<int, __gnu_cxx::malloc_allocator<string>> vec; // <ext\...>  <ext\malloc_allocator.h>
vector<int, __gnu_cxx::new_allocator<string>> vec;  
vector<int, __gnu_cxx::bitmap_allocator<string>> vec;  
vector<int, __gnu_cxx::array_allocator<string>> vec;  
vector<int, __gnu_cxx::debug_allocator<string>> vec;  
vector<int, __gnu_cxx::__pool_alloc<string>> vec;  // 内存池
vector<int, __gnu_cxx::__mt_alloc<string>> vec;  // 多线程

使用分配器

1
2
3
4
int *p;
allocator<int> ac;
p = ac.allocate(1); // 分配内存 1个int
ac.deallocate(p, 1); // 释放内存

New 与 Malloc

allocate 底层调用 operator new。
deallocate 底层调用 delete。
new 底层调用 malloc。
delete 底层调用 free。
malloc 不只分配了需要的内存，还有Debug信息，填充字节，上下边界符号等。
在VC6+，BC5中，allocator 中只使用new和delete，没有其他特殊设计。也就是，分配的只有指针，外部开销巨大（每个指针还要malloc，而每个malloc自带信息就已经远大于指针的大小了）。
在GNU2.9中，并未使用STL标准规定的分配器（<defalloc.h>没有特殊设计），而使用的是alloc分配器<stl_alloc.h>。这种优势在于，外部开销小（malloc次数很少）。容器的元素大小会被调整到8的倍数，然后malloc一大块内存，再进行切分。
在GNU4.9中，使用了__gnu_cxx::new_allocator，也就是VC6+一样的分配器。而原来的分配器改为__pool_alloc。

1
2
int* p = allocator<int>().allocate(512, (int*)0);
allocator<int>().deallocate(p, 512);

迭代器

迭代器遵循的原则（为算法提供的属性）：

  • 分类
  • 距离
  • 值
  • 引用（未使用）
  • 指针（未使用）

算法为了了解使用的迭代器的功能，需要通过 Iterator Trais 来获取迭代器的五种属性。

1
typename iterator_trais<RandomAccessIterator>::iterator_category(); // 获取迭代器所属分类

迭代器分类：随机访问迭代器，双向链表迭代器

RandomAccessIterator 可加减乘除运算
List 不用 RandomAccessIterator 而是 ListIterator

1
2
3
4
5
list<int>::iterator ite;
(*ite).method();
ite->method();
ite++; ++ite;
ite--; --ite;

注：Trais 分6类：type，iterator，char，allocator，pointer，array。

算法

比较大小

1
2
3
4
5
6
equal_to<T>();
not_equal_to<T>();
greater<T>();
greater_equal<T>();
less<T>();
less_equal<T>();

排序

1
2
3
4
5
6
7
8
9
bool compare_function(int a, int b) {return a<b;}

sort(a.begin(), a.end());  // 使用RandomAccessIterator迭代器排序
sort(a.begin(), a.end(), compare_function);  // 自定义排序函数
stable_sort(); 
is_sorted();
partition(); // 符合条件的元素放在前面
stable_partition();
qsort(&a[0], 20, sizeof(a[0]), compare_function); // 使用指针排序