STL

hash_map、hash_set

• 底层实现是hash_table(vector + linklist)

• SGI hashtable使用开链法解决hash冲突、SGI hashtable无法处理处理除以下几个类型外的元素：

  • char、int、long
  • 欲处理除以上类型的元素，像是直接处理string会出错。需要用户自己自定义hash funciton

• 现在已经不建议使用，转而使用unordered_map、unordered_set

仿函数

• 一个“行为类似函数”的对象，其类别定义(可以定义函数中使用的变量、即成员变量)中必须自定义（或者重载）funciton call运算子(operator())，拥有了这样的运算子后，我们就可以在仿函数对象后面加上一对小括号，以此调用仿函数所定义的operator()

迭代器

在STL中，迭代器主要分为5类。各自是：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机訪问迭代器。

    输入迭代器：仅仅读。支持++、==、！=；

    输出迭代器：仅仅写，支持++；

    前向迭代器：读写，支持++、==、！=。

    双向迭代器：读写，支持++、--。C++的全部标准库容器都至少在双向迭代器的层次上。；

    随机訪问迭代器：读写，支持++、--、[n]、-n、<、<=、>、>=。