Boolan微专业-STL与泛型编程（Week01）

STL与泛型编程

主要内容：

介绍了 STL 的体系结构，六大部件和主要的容器。并利用测试程序介绍了容器的使用方法。

目标

• Level 0: 使用 C++ 标准库
• Level 1: 深入认识 C++ 标准库（胸中自由丘壑）
• Level 2: 良好使用 C++ 标准库
• Level 3: 扩充 C++ 标准库

参考网站

• www.cplusplus.com
• en.cppreference.com
• gcc.gnu.org

推荐书籍

• C++ 标准库
• STL 源码剖析

使用一个东西，却不明白它的道理，不高明。--林语堂

---

一、STL 体系结构

1. 概述

• 六大部件
  • 容器(Containers)：存放数据。
  • 分配器(Allocators)：支持容器分配内存。
  • 算法(Algorithms)：排序，查找... 利用迭代器处理容器的数据
  • 迭代器(Iterators)：一种泛化的指针。
  • 适配器(Adapters)：可以转换容器、泛函数、迭代器
  • 仿函数(Functors)：函数功能的类
• 使用
  • 用到哪个容器，就要引用哪个头文件。
  • 在使用容器和算法时要根据使用场景，考虑复杂度。
  • vector<int,allocator<int>> vi(ia,ia+6); cout_if(vi.begin(), vi.end(), not1(bind2nd(less<int(), 40 )));

2. 容器-结构与分类

• 顺序容器
  • array-无法扩展，元素数量在定时时就确定了
  • vector-单项扩展，每次增大一倍容量
  • deque-分段连续，双向扩展
  • list-双向链表
  • forward_list / slist-单项链表
• 关联容器
  • set/multiset-内部利用红黑树实现，Key==Value
  • map/multimap-内部利用红黑树实现，存放 Key 与 Value 的键值对 Pair<Key,Value>
• 无序容器（c++11）
  • unordered set/multiset-利用hash table separeta chining 实现
  • unordered map/multimap-利用hash table separeta chining 实现

3. 容器-使用示例

1. array
   • array.size(), array.front(), array.back(), array.data() (返回array首元素的地址
2. vector
   • capacity() 容量每次扩展是上次的二倍, size(), data(), front(), back(), push_back()
   • push_back()，内存不够时会抛出异常 std::bad_alloc， 需要 abort() 退出程序。
3. list
   • max_size(), list.sort()
   • list自己提供了sort()，用容器自己提供sort比用::sort()要好，效率更高。
4. forward_list
   • 本身也有sort(), 没有size() 和 back().
5. slist 单向链表，是非标准库中的，gnc中的。
   • include<ext\slist>
6. deque
   • max_size()
   • 排序只能用::sort().
   • 双向队列，分段连续（由一个个段组成，每段是连续的内存空间。用一个map存放每个段的指针）
7. stack & queue是
   • 技术上属于容器适配器，是利用deque实现的。
   • stack先进后出。queue先进先出。push(), pop().
8. set/multiset
   • insert(), size(), max_size().
   • 容器自己提供 find()
9. map/multimap
   • insert(), find()
   • map可以用[]赋值，multimap不能使用[].
10. unordered_set / unordered_multiset
    • insert(),size(),max_size(),bucket_count()(篮子一定比元素要多，因为有些篮子可能是空的)
    • bucket_size(i)（第i个篮子中元素的数量）当元素数量和篮子数量一致时，会分配原有的篮子数量的二倍的空间，之后重新分配元素的放置位置。
    • load_factor(), max_load_factor(), max_bucket_count()。
    • 容器自己提供 find()
11. unordered_map / unordered_multimap
12. hash_set, hash_map,hash_multiset,hash_multimap
    • unordered的旧版本。