本文共 3988 字，大约阅读时间需要 13 分钟。
极客班 C++ STL （容器算法）第二周笔记
标签（空格分隔）： C++
1. 容器（下）
1.1 Stack
a. 概述
Stack 是一种先进先后出（First In Last Out）的数据结构，只有一个出口。 特点：
- 支持的操作有
- 只能访问顶端元素，不允许便利
- 要使用Stack，必须引入<stack> 头文件（标准库）
#include int main(){ std::stack s; //必须提供泛化参数 s.push(1); //将1压栈 s.pop(); //弹出栈顶元素 s.size(); //获取栈大小 return 0; }
b. Stack的底层数据结构(1)
查看标准库头文件，我们可以知道，STL stack是以deque作为默认底层结构的：
// TEMPLATE CLASS stacktemplate > class stack { // LIFO queue implemented with a container //... }
联系我们在C++ OOP面向对象设计接触到的方法，这种设计就是一种对既有接口的包装，适配，即采用了adapter模式。该模式在这里是包装了deque，并给出了push/pop/top等栈特有的接口。
由于stack不允许遍历，所以没有iterator。
c. Stack的底层数据结构(2)
在 1.1小节中，我们看到了stack的底层定义，发现在模板参数里的容器选项中，是传入了一个deque<_Ty>作为默认参数。 所以，我们除了deque<T>，list<T>其实也是可以拿来作为底层的数据结构的。
//e.g.std::stack
> s;s.push(1);s.pop();s.top();s.size();
1.2 Queue
a. 概述
Queue呢，就是一种先进先出的数据结构， 有两个出口。 - 支持四种操作：push（增加元素），移除元素（pop），获取最前面的元素（front），获取最后面的元素（back） - 只能访问最前或者最后的元素 - 需要引入标准库<queue>才可以使用
#include int main(){ std::queue q;//初始化一个存放int型别的队列 q.push(1); //插入元素 q.pop(); //移除元素 q.back(); //获取最后一个元素 q.front(); //获取最前面的元素}
b. queue的底层数据结构(1)
查看标准库，我们可知，与stack一样，queue也是包装了deque<T>
// TEMPLATE CLASS queuetemplate > class queue { // FIFO queue implemented with a container //... }
有了这一层的认识，我们可以知道，由于不允许遍历，和stack一样所以queue也没有迭代器(iterator)。
c. queue的底层数据结构(2)
跟stack类似，queue也是可以以list作为底层数据结构的。具体示例暂时不给出了（接口不变，只是换了底层实现)。
1.3 Map and Multimap
1.3.1 Map 概述
Map的特性
- 是一种关联容器，存储的是key/value pair
- 不允许key重复
- map存储的对象必须是具有可排序性的
// TEMPLATE CLASS maptemplate , class _Alloc = allocator > > class map : public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> > { // ordered red-black tree of {key, mapped} values, unique keys //... }
其中，
_Kty 就是对应的键key_Ty 就是对应的值value_Pr 对应的排序算法，默认是less<T>算法，即按_Kty排序，那么，_Kty必须要实现比较操作符operator < _Alloc 内存分配算法（针对这个键值对的）
1.3.2 例子
//STL_test.h//map valuestruct Employee { Employee(){} Employee(const std::wstring& wszName):Name(wszName){} std::wstring Name; void print() const { std::wcout << Name << "\n"; }};//仿函数，定义比较大小struct ReversId :public std::binary_function { bool operator()(const int& key1, const int &key2) { return (key1 <= key2) ? false : true; }};//for_each 打印struct FunctorPrintMapValue{ void operator()(const std::pair pair) { pair.second.print(); }}; //STL_test.cppint main(){ const int size = 3; std::pair items[size] = { std::make_pair(1, Employee(L"Tom")), std::make_pair(2, Employee(L"Jerry")), std::make_pair(3, Employee(L"Alice")) }; std::map m(items, items + size); std::for_each(m.begin(), m.end(), FunctorPrintMapValue()); system("pause"); return 0;} 结果：
我们可以看出，按照自定义的less算法，确实实现了按key倒排序。
1.4 Set and Multset
set 跟map略有不一样，感觉上像是map的特殊版本，因为，在set中，
- 存储的对象本身，既是
key，又是value。 - 不允许有重复的
key set存储的对象，必须是具有可排序性 - 要达到这个目标，那么存储的对象必须实现了
operator <操作符 - 支持自定义排序行为（通过仿函数实现）
- 必须是引入<set>标准库，通过std::set 访问
下面是一个示例，接着Employee示例来：
//STL_test.h//set 按名字比较排序仿函数struct FunctorEmployeeNameComparer:public std::binary_function { bool operator()(const Employee& EmpLeft, const Employee& EmpRight) { return EmpLeft.getName() < EmpRight.getName(); }};//for_each 打印setstruct FunctorPrintSetValue{ void operator()(const Employee& emp) { emp.print(); }};
//STL_test.cpp //2. set const int nSize = 4; Employee person[] = { Employee(L"Tom"), Employee(L"Jerry"), Employee(L"Alice"), Employee(L"Tony") }; std::set epSet(person, person + nSize); std::for_each(epSet.begin(), epSet.end(), FunctorPrintSetValue()); 结果：
2. STL整体结构，仿函数（仿函数适配器），binder1st
3. binder2nd, mem_fun, mem_fun_ref,一些注意的问题
4. 泛型算法_非变异算法
