Geekband C++ 第六周

概述

• Container
• Stack，Queue，Map和Set
• STL中的仿函数，适配器
• 泛型算法之非变易算法

容器

Stack

• 一种先进后出的数据结构
• 支持push，pop和top操作，只能访问顶层元素，不允许遍历
• 以deque作为默认的底层结构
• （因为不支持遍历）没有iterator

Queue

• 先进先出的数据结构
• 支持push，pop，front，back操作，不允许遍历
• 以deque作为默认底层结构
• （因为不支持遍历）没有iterator

Map

• 一种关联容器，存储对象是key/value pair
• 不允许有重复的key
• map存储的对象必须能够排序，默认采用less（仿函数）定义排序行为，可以自定义排序函数
• 支持
  • 插入元素：insert
  • 删除元素：erase
  • 取元素：[]

Set

• 一种关联容器，存储对象本身是key又是value
• 不允许有重复的key
• 存储的对象必须可以排序
• 默认用less排序，可以定义排序行为
• 支持
  • 插入：insert
  • 删除：erase
  • 并：set_union
  • 交：set_intersection
  • 差：set_difference
• 通过iterator改变set的成员
  • const_cast<Person&>(*it).SetName(L"Bill Gates")
  • 其中Person是一set

STL的整体结构

• 容器通过内存分配器分配空间
• 容器和算法通过迭代器联系
• 仿函数协助算法完成不同的策略
• 适配器套接仿函数

仿函数（Functor）

• 类重载()，作用相当于一个函数指针
• 可以用于模板实参，用于定义对象的行为
• binder1st/binder2nd
  • 解决需要两个参数的Functor用于泛型算法的问题，binder1st将一“常数”绑定到左操作数，作用相当于只接收一个参数的Functor
  • binder2nd将“常数”绑定在第二个操作数上
• mem_fun

  • 支持在算法中使用类的成员函数，否则只能使用全局函数

    
    mem_fun
• mem_fun_ref
  • 某一容器中存放的是对象

  • 遍历容器的算法时，支持使用类的成员函数

    
    mem_fun_ref

注意

• 单线程下涉及对字符串的操作使用
• string和wstring
• 多线程下对字符串的操作使用
• vector<char>和vector<wchar_t>
• new出的对象放入容器时，在销毁容器前，delete那些对象
• 尽量用算法代替手写循环
• 通过swap为容器“缩水”
• 在有对象继承的情况下，建立指针的容器而不是对象的容器

非变易算法

• 一系列模板函数，在不改变操作对象的前提下对元素进行处理
• for_each
• find
• find_if
• adjacent_find
• find_first_of
• count
• count_if
• mismatch
• equal
• search