SGI STL 源码阅读：仿函数与适配器如何定制算法行为

理解 unary_function、binary_function、not/bind/compose 等仿函数适配器，以及 stack、queue、priority_queue 的容器适配思想。

SGI STL Functor Adapter Algorithm

阅读地图：先抓住这篇源码的主线

flowchart LR
    A[STL Algorithm] --> B[接收策略参数]
    B --> C[Functor operator()]
    C --> D[unary_function / binary_function 暴露类型]
    D --> E[Adapter 读取 argument_type/result_type]
    E --> F[not1 / bind1st / bind2nd / compose]
    F --> G[生成新的可调用对象]
    A --> H[Container Adapter]
    H --> I[stack / queue / priority_queue]
    I --> J[复用底层 deque/vector]

SGI STL 源码阅读：仿函数与适配器如何定制算法行为的核心关系图

策略对象仿函数把算法中的比较、逻辑、运算行为参数化。

类型接口unary/binary_function 的 typedef 让适配器知道参数与返回值类型。

适配思想函数适配器改造调用方式，容器适配器改造容器接口。

SGI-STL 仿函数（Functor）与容器适配器（Container Adapter）源码解析

参考源码：SGI-STL v3.3 (stl_function.h, stl_stack.h, stl_queue.h)

---

第一部分：仿函数（Functor）

1.1 仿函数概述

什么是仿函数？

仿函数（Functor）是"仿照函数功能制造出来的对象"。在C++中，只要某个类重载了operator()，它的实例就可以像函数一样被调用。


// 一个简单的仿函数
class LessThan {
    int _threshold;
public:
    LessThan(int t) : _threshold(t) {}
    bool operator()(int x) const { return x < _threshold; }
};

LessThan lt(10);           // 创建一个仿函数对象
bool result = lt(5);        // 像函数一样调用，返回 true
bool result2 = LessThan(10)(5);  // 创建临时对象并调用

为什么要用仿函数而不是普通函数？

仿函数可以持有状态——普通函数无法保存状态，仿函数可以携带参数
模板实例化更精确——每个仿函数类型是独立的，编译器可更好优化
STL算法的策略参数——算法是通用的，仿函数提供可定制的运算逻辑

STL中仿函数的核心价值：算法是通用的，但运算逻辑是可定制的。算法接受仿函数作为策略参数，实现"同一种算法，不同的行为"。

---

1.2 仿函数的基类：unary_function 与 binary_function

STL的所有仿函数都继承自两个基类：


// 一元仿函数的基类
template <class _Arg, class _Result>
struct unary_function {
  typedef _Arg argument_type;      // 参数类型
  typedef _Result result_type;      // 返回值类型
};

// 二元仿函数的基类
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
  typedef _Arg1 first_argument_type;   // 第一个参数类型
  typedef _Arg2 second_argument_type;  // 第二个参数类型
  typedef _Result result_type;         // 返回值类型
};

这两个基类本身不提供任何运算能力，它们只是"类型标签"。

为什么要这样设计？

这些typedef的真正价值在于让仿函数适配器能够"感知"仿函数的参数类型。例如，binder1st想知道二元函数的第一个参数是什么类型，才能正确地将第一个参数绑定为常数并转换为一元函数。没有这些typedef，适配器就无法工作。

零成本抽象：这两个基类只包含typedef，没有数据成员，没有虚函数。继承它们不会带来任何运行时开销。

---

1.3 预定义仿函数分类

STL提供了完整的算术、比较、逻辑运算仿函数，可直接作为算法参数使用。

1.3.1 算术仿函数


// 加法
template <class _Tp>
struct plus : public binary_function<_Tp,_Tp,_Tp> {
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x + __y; }
};

// 减法
template <class _Tp>
struct minus : public binary_function<_Tp,_Tp,_Tp> {
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x - __y; }
};

// 乘法
template <class _Tp>
struct multiplies : public binary_function<_Tp,_Tp,_Tp> {
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x * __y; }
};

// 地板除
template <class _Tp>
struct divides : public binary_function<_Tp,_Tp,_Tp> {
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x / __y; }
};

// 模
template <class _Tp>
struct modulus : public binary_function<_Tp,_Tp,_Tp> {
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x % __y; }
};

// 相反数（一元）
template <class _Tp>
struct negate : public unary_function<_Tp,_Tp> {
  _Tp operator()(const _Tp& __x) const { return -__x; }
};

1.3.2 单位元素（identity_element）

对于plus，单位元素是0；对于multiplies，单位元素是1：


template <class _Tp> inline _Tp identity_element(plus<_Tp>) {
  return _Tp(0);
}
template <class _Tp> inline _Tp identity_element(multiplies<_Tp>) {
  return _Tp(1);
}

这是函数重载的技巧。通过传入的仿函数类型不同，编译器自动选择对应的返回值的单位元素。

1.3.3 比较仿函数


template <class _Tp>
struct equal_to : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};

template <class _Tp>
struct not_equal_to : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x != __y; }
};

template <class _Tp>
struct greater : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x > __y; }
};

template <class _Tp>
struct less : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }
};

template <class _Tp>
struct greater_equal : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x >= __y; }
};

template <class _Tp>
struct less_equal : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x <= __y; }
};

实际应用：sort()默认使用less，即从小到大排序。如果要降序排序：


sort(v.begin(), v.end(), greater<int>());

1.3.4 逻辑仿函数


template <class _Tp>
struct logical_and : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x && __y; }
};

template <class _Tp>
struct logical_or : public binary_function<_Tp,_Tp,bool> {
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x || __y; }
};

template <class _Tp>
struct logical_not : public unary_function<_Tp,bool> {
  bool operator()(const _Tp& __x) const { return !__x; }
};

---

1.4 仿函数适配器

适配器（Adapter）模式的核心思想：将一个接口转换为另一个接口。STL中的仿函数适配器将"不符合STL要求的函数对象"转换为"符合要求的函数对象"。

1.4.1 取反适配器（not1 / not2）

not1用于将一元谓词取反，not2用于将二元谓词取反：


// not1：对一元谓词取反
template <class _Predicate>
class unary_negate
  : public unary_function<typename _Predicate::argument_type, bool> {
protected:
  _Predicate _M_pred;  // 存储原始谓词
public:
  explicit unary_negate(const _Predicate& __x) : _M_pred(__x) {}
  bool operator()(const typename _Predicate::argument_type& __x) const {
    return !_M_pred(__x);  // 取反
  }
};

template <class _Predicate>
inline unary_negate<_Predicate> not1(const _Predicate& __pred) {
  return unary_negate<_Predicate>(__pred);
}

// not2：对二元谓词取反
template <class _Predicate>
class binary_negate
  : public binary_function<typename _Predicate::first_argument_type,
                           typename _Predicate::second_argument_type,
                           bool> {
protected:
  _Predicate _M_pred;
public:
  explicit binary_negate(const _Predicate& __x) : _M_pred(__x) {}
  bool operator()(const typename _Predicate::first_argument_type& __x,
                  const typename _Predicate::second_argument_type& __y) const {
    return !_M_pred(__x, __y);
  }
};

template <class _Predicate>
inline binary_negate<_Predicate> not2(const _Predicate& __pred) {
  return binary_negate<_Predicate>(__pred);
}

使用示例：


// 找出所有不大于3的元素（即 < 3 的相反）
remove_if(v.begin(), v.end(), not1(bind2nd(less<int>(), 3)));

1.4.2 绑定适配器（bind1st / bind2nd）

绑定适配器将二元函数转换为一元函数：

bind1st：将第一个参数绑定为固定值
bind2nd：将第二个参数绑定为固定值


// bind1st：将二元函数的第一个参数绑定为常数
template <class _Operation>
class binder1st
  : public unary_function<typename _Operation::second_argument_type,
                          typename _Operation::result_type> {
protected:
  _Operation op;                                    // 存储原始二元函数
  typename _Operation::first_argument_type value;   // 第一个参数被绑定的值
public:
  binder1st(const _Operation& __x,
            const typename _Operation::first_argument_type& __y)
      : op(__x), value(__y) {}
  typename _Operation::result_type
  operator()(const typename _Operation::second_argument_type& __x) const {
    return op(value, __x);  // 固定第一个参数
  }
};

template <class _Operation, class _Tp>
inline binder1st<_Operation> bind1st(const _Operation& __fn, const _Tp& __x) {
  typedef typename _Operation::first_argument_type _Arg1_type;
  return binder1st<_Operation>(__fn, _Arg1_type(__x));
}

// bind2nd：将二元函数的第二个参数绑定为常数
template <class _Operation>
class binder2nd
  : public unary_function<typename _Operation::first_argument_type,
                          typename _Operation::result_type> {
protected:
  _Operation op;
  typename _Operation::second_argument_type value;
public:
  binder2nd(const _Operation& __x,
            const typename _Operation::second_argument_type& __y)
      : op(__x), value(__y) {}
  typename _Operation::result_type
  operator()(const typename _Operation::first_argument_type& __x) const {
    return op(__x, value);  // 固定第二个参数
  }
};

template <class _Operation, class _Tp>
inline binder2nd<_Operation> bind2nd(const _Operation& __fn, const _Tp& __x) {
  typedef typename _Operation::second_argument_type _Arg2_type;
  return binder2nd<_Operation>(__fn, _Arg2_type(__x));
}

核心理解：将二元函数op(a, b)的某个参数固定为常数，只留下一个参数。

使用示例：


// 找出所有大于等于5的元素
find_if(v.begin(), v.end(), bind2nd(greater_equal<int>(), 5));
// 等价于 lambda: [](int x){ return x >= 5; }

// 将 less<int> 的第一个参数绑定为3，变成 x < 3
// 即找出所有小于3的元素
find_if(v.begin(), v.end(), bind1st(less<int>(), 3));

1.4.3 函数指针适配器（ptr_fun）

将普通函数指针转换为仿函数对象，使算法可以接受函数指针：


// 一元函数指针适配器
template <class _Arg, class _Result>
class pointer_to_unary_function : public unary_function<_Arg, _Result> {
protected:
  _Result (*_M_ptr)(_Arg);  // 存储函数指针
public:
  pointer_to_unary_function() {}
  explicit pointer_to_unary_function(_Result (*__x)(_Arg)) : _M_ptr(__x) {}
  _Result operator()(_Arg __x) const { return _M_ptr(__x); }
};

template <class _Arg, class _Result>
inline pointer_to_unary_function<_Arg, _Result>
ptr_fun(_Result (*__x)(_Arg)) {
  return pointer_to_unary_function<_Arg, _Result>(__x);
}

// 二元函数指针适配器
template <class _Arg1, class _Arg2, class _Result>
class pointer_to_binary_function :
  public binary_function<_Arg1,_Arg2,_Result> {
protected:
    _Result (*_M_ptr)(_Arg1, _Arg2);
public:
    pointer_to_binary_function() {}
    explicit pointer_to_binary_function(_Result (*__x)(_Arg1, _Arg2)) : _M_ptr(__x) {}
    _Result operator()(_Arg1 __x, _Arg2 __y) const { return _M_ptr(__x, __y); }
};

template <class _Arg1, class _Arg2, class _Result>
inline pointer_to_binary_function<_Arg1,_Arg2,_Result>
ptr_fun(_Result (*__x)(_Arg1, _Arg2)) {
  return pointer_to_binary_function<_Arg1,_Arg2,_Result>(__x);
}

使用示例：


int square(int x) { return x * x; }
transform(v.begin(), v.end(), v.begin(), ptr_fun(square));

1.4.4 成员函数适配器（mem_fun / mem_fun_ref）

这是STL中最复杂的适配器家族。设计它是为了让算法能直接作用于对象的成员函数。


// 成员函数通过指针调用，无参版本
template <class _Ret, class _Tp>
class mem_fun_t : public unary_function<_Tp*, _Ret> {
public:
  explicit mem_fun_t(_Ret (_Tp::*__pf)()) : _M_f(__pf) {}
  _Ret operator()(_Tp* __p) const { return (__p->*_M_f)(); }
private:
  _Ret (_Tp::*_M_f)();
};

// const成员函数版本
template <class _Ret, class _Tp>
class const_mem_fun_t : public unary_function<const _Tp*, _Ret> {
public:
  explicit const_mem_fun_t(_Ret (_Tp::*__pf)() const) : _M_f(__pf) {}
  _Ret operator()(const _Tp* __p) const { return (__p->*_M_f)(); }
private:
  _Ret (_Tp::*_M_f)() const;
};

// 成员函数通过引用调用
template <class _Ret, class _Tp>
class mem_fun_ref_t : public unary_function<_Tp, _Ret> {
public:
  explicit mem_fun_ref_t(_Ret (_Tp::*__pf)()) : _M_f(__pf) {}
  _Ret operator()(_Tp& __r) const { return (__r.*_M_f)(); }
private:
  _Ret (_Tp::*_M_f)();
};

// 带一个参数的成员函数
template <class _Ret, class _Tp, class _Arg>
class mem_fun1_t : public binary_function<_Tp*, _Arg, _Ret> {
public:
  explicit mem_fun1_t(_Ret (_Tp::*__pf)(_Arg)) : _M_f(__pf) {}
  _Ret operator()(_Tp* __p, _Arg __x) const { return (__p->*_M_f)(__x); }
private:
  _Ret (_Tp::*_M_f)(_Arg);
};

辅助函数：


template <class _Ret, class _Tp>
inline mem_fun_t<_Ret, _Tp> mem_fun(_Ret (_Tp::*__f)())
  { return mem_fun_t<_Ret, _Tp>(__f); }

template <class _Ret, class _Tp>
inline const_mem_fun_t<_Ret, _Tp> mem_fun(_Ret (_Tp::*__f)() const)
  { return const_mem_fun_t<_Ret, _Tp>(__f); }

template <class _Ret, class _Tp>
inline mem_fun_ref_t<_Ret, _Tp> mem_fun_ref(_Ret (_Tp::*__f)())
  { return mem_fun_ref_t<_Ret, _Tp>(__f); }

使用示例：


class Foo {
public:
  void print() const { std::cout << "Hello" << std::endl; }
};

vector<Foo*> v;
for_each(v.begin(), v.end(), mem_fun(&Foo::print));

16种变体的由来：SGI-STL注释中解释，这个家族有2^4=16种变体：

| 维度 | 选项1 | 选项2 | |------|-------|-------| | 参数个数 | 无参 | 带一个参数 | | 调用方式 | 指针 | 引用 | | 返回类型 | void | 非void | | const属性 | const成员 | 非const成员 |

1.4.5 函数组合适配器（compose1 / compose2）

注意：这是SGI-STL的扩展，不在C++标准中。

compose1将两个一元函数组合：f = f1 o f2，即f(x) = f1(f2(x))


template <class _Operation1, class _Operation2>
class unary_compose
  : public unary_function<typename _Operation2::argument_type,
                          typename _Operation1::result_type> {
protected:
  _Operation1 _M_fn1;  // 外层函数 f1
  _Operation2 _M_fn2;  // 内层函数 f2
public:
  unary_compose(const _Operation1& __x, const _Operation2& __y)
    : _M_fn1(__x), _M_fn2(__y) {}
  typename _Operation1::result_type
  operator()(const typename _Operation2::argument_type& __x) const {
    return _M_fn1(_M_fn2(__x));  // 先算f2(x)，再算f1(结果)
  }
};

template <class _Operation1, class _Operation2>
inline unary_compose<_Operation1, _Operation2>
compose1(const _Operation1& __fn1, const _Operation2& __fn2) {
  return unary_compose<_Operation1, _Operation2>(__fn1, __fn2);
}

compose2组合两个函数处理同一参数：f(x) = f1(f2(x), f3(x))


template <class _Operation1, class _Operation2, class _Operation3>
class binary_compose
  : public unary_function<typename _Operation2::argument_type,
                          typename _Operation1::result_type> {
protected:
  _Operation1 _M_fn1;
  _Operation2 _M_fn2;
  _Operation3 _M_fn3;
public:
  binary_compose(const _Operation1& __x, const _Operation2& __y,
                 const _Operation3& __z)
    : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) {}
  typename _Operation1::result_type
  operator()(const typename _Operation2::argument_type& __x) const {
    return _M_fn1(_M_fn2(__x), _M_fn3(__x));  // 同时计算f2(x)和f3(x)，传给f1
  }
};

template <class _Operation1, class _Operation2, class _Operation3>
inline binary_compose<_Operation1, _Operation2, _Operation3>
compose2(const _Operation1& __fn1, const _Operation2& __fn2,
         const _Operation3& __fn3) {
  return binary_compose<_Operation1, _Operation2, _Operation3>(__fn1, __fn2, __fn3);
}

---

1.5 辅助仿函数

1.5.1 identity（恒等仿函数）

返回输入值本身：


template <class _Tp>
struct _Identity : public unary_function<_Tp, _Tp> {
  const _Tp& operator()(const _Tp& __x) const { return __x; }
};

template <class _Tp> struct identity : public _Identity<_Tp> {};

1.5.2 select1st / select2nd（选择仿函数）

从pair中提取第一个或第二个元素：


template <class _Pair>
struct _Select1st : public unary_function<_Pair, typename _Pair::first_type> {
  const typename _Pair::first_type& operator()(const _Pair& __x) const {
    return __x.first;
  }
};

template <class _Pair>
struct _Select2nd : public unary_function<_Pair, typename _Pair::second_type> {
  const typename _Pair::second_type& operator()(const _Pair& __x) const {
    return __x.second;
  }
};

template <class _Pair> struct select1st : public _Select1st<_Pair> {};
template <class _Pair> struct select2nd : public _Select2nd<_Pair> {};

使用场景：map/multimap容器按key排序时，可用select1st提取键值。

1.5.3 project1st / project2nd（投射仿函数）


template <class _Arg1, class _Arg2>
struct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1> {
  _Arg1 operator()(const _Arg1& __x, const _Arg2&) const { return __x; }
};

template <class _Arg1, class _Arg2>
struct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2> {
  _Arg2 operator()(const _Arg1&, const _Arg2& __y) const { return __y; }
};

template <class _Arg1, class _Arg2>
struct project1st : public _Project1st<_Arg1, _Arg2> {};

template <class _Arg1, class _Arg2>
struct project2nd : public _Project2nd<_Arg1, _Arg2> {};

1.5.4 constant（常量仿函数）

返回固定常数的仿函数，有三种版本：


// 0参数常量仿函数
template <class _Result>
struct _Constant_void_fun {
  typedef _Result result_type;
  result_type _M_val;
  _Constant_void_fun(const result_type& __v) : _M_val(__v) {}
  const result_type& operator()() const { return _M_val; }
};

// 1参数常量仿函数（忽略参数）
template <class _Result, class _Argument>
struct _Constant_unary_fun {
  typedef _Argument argument_type;
  typedef _Result result_type;
  result_type _M_val;
  _Constant_unary_fun(const result_type& __v) : _M_val(__v) {}
  const result_type& operator()(const _Argument&) const { return _M_val; }
};

// 2参数常量仿函数（忽略参数）
template <class _Result, class _Arg1, class _Arg2>
struct _Constant_binary_fun {
  typedef _Arg1 first_argument_type;
  typedef _Arg2 second_argument_type;
  typedef _Result result_type;
  _Result _M_val;
  _Constant_binary_fun(const _Result& __v) : _M_val(__v) {}
  const result_type& operator()(const _Arg1&, const _Arg2&) const {
    return _M_val;
  }
};

template <class _Result>
inline constant_void_fun<_Result> constant0(const _Result& __val)
  { return constant_void_fun<_Result>(__val); }

template <class _Result>
inline constant_unary_fun<_Result, _Result> constant1(const _Result& __val)
  { return constant_unary_fun<_Result, _Result>(__val); }

template <class _Result>
inline constant_binary_fun<_Result, _Result, _Result>
constant2(const _Result& __val)
  { return constant_binary_fun<_Result, _Result, _Result>(__val); }

1.5.5 subtractive_rng（减法随机数生成器）

这是SGI-STL扩展，使用55元素的查找表生成伪随机数：


class subtractive_rng : public unary_function<unsigned int, unsigned int> {
private:
  unsigned int _M_table[55];
  size_t _M_index1;
  size_t _M_index2;
public:
  unsigned int operator()(unsigned int __limit) {
    _M_index1 = (_M_index1 + 1) % 55;
    _M_index2 = (_M_index2 + 1) % 55;
    _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2];
    return _M_table[_M_index1] % __limit;
  }
  void _M_initialize(unsigned int __seed) {
    unsigned int __k = 1;
    _M_table[54] = __seed;
    for (size_t __i = 0; __i < 54; __i++) {
        size_t __ii = (21 * (__i + 1) % 55) - 1;
        _M_table[__ii] = __k;
        __k = __seed - __k;
        __seed = _M_table[__ii];
    }
    for (int __loop = 0; __loop < 4; __loop++) {
        for (size_t __i = 0; __i < 55; __i++)
            _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55];
    }
    _M_index1 = 0;
    _M_index2 = 31;
  }
  subtractive_rng(unsigned int __seed) { _M_initialize(__seed); }
  subtractive_rng() { _M_initialize(161803398u); }
};

---

1.6 仿函数设计思想总结

1.6.1 零成本抽象

unary_function和binary_function只包含typedef，没有数据成员，没有虚函数。继承它们不会带来任何运行时开销。

1.6.2 适配器的本质

所有仿函数适配器都遵循同一模式：

持有原始仿函数
继承适当的function基类
在operator()中调用/转换原始仿函数

1.6.3 类型标签系统

STL大量使用"类型作为标签"的技巧：

迭代器category用空struct作为标签，实现重载分派
仿函数基类用typedef作为标签，让适配器能够"感知"类型

1.6.4 与现代C++的对应关系

| SGI-STL | 现代C++ | 引入版本 | |---------|---------|---------| | binder1st/bind2nd | std::bind | C++11 | | not1/not2 | std::not_fn | C++17 | | mem_fun/mem_fun_ref | std::mem_fn | C++11 | | ptr_fun | 隐式转换 | C++11 | | compose1/compose2 | std::views::compose | C++20 |

---

第二部分：容器适配器（Container Adapter）

容器适配器是将某种容器"改装"成另一种容器接口的类模板。STL提供了三种容器适配器：stack（栈）、queue（队列）、priority_queue（优先队列）。

---

2.1 stack（栈）适配器

2.1.1 设计原理

stack是对现有序列容器的封装，默认使用deque作为底层容器，也可以指定其他容器（如vector、list）。

关键设计：stack不是继承，而是委托。它内部持有一个容器对象c，所有操作都转发给这个容器。


template <class _Tp, class _Sequence>
class stack {

  // 约束检查：_Tp必须是可赋值的，_Sequence必须是支持尾插的序列容器
  __STL_CLASS_REQUIRES(_Tp, _Assignable);
  __STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);
  typedef typename _Sequence::value_type _Sequence_value_type;
  __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);

#ifdef __STL_MEMBER_TEMPLATES
  template <class _Tp1, class _Seq1>
  friend bool operator== (const stack<_Tp1, _Seq1>&,
                          const stack<_Tp1, _Seq1>&);
  template <class _Tp1, class _Seq1>
  friend bool operator< (const stack<_Tp1, _Seq1>&,
                         const stack<_Tp1, _Seq1>&);
#endif

public:
  typedef typename _Sequence::value_type      value_type;
  typedef typename _Sequence::size_type       size_type;
  typedef          _Sequence                  container_type;  // 底层容器类型
  typedef typename _Sequence::reference       reference;
  typedef typename _Sequence::const_reference const_reference;

protected:
  _Sequence c;  // 底层容器

public:
  stack() : c() {}
  explicit stack(const _Sequence& __c) : c(__c) {}

  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference top() { return c.back(); }          // 栈顶元素
  const_reference top() const { return c.back(); }
  void push(const value_type& __x) { c.push_back(__x); }  // 入栈
  void pop() { c.pop_back(); }                 // 出栈
};

2.1.2 操作接口

| 操作 | 说明 | 底层实现 | |------|------|---------| | empty() | 判断栈是否为空 | c.empty() | | size() | 返回栈大小 | c.size() | | top() | 返回栈顶元素（引用） | c.back() | | push(x) | 入栈 | c.push_back(x) | | pop() | 出栈（不返回元素） | c.pop_back() |

2.1.3 关系操作符


template <class _Tp, class _Seq>
bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) {
  return __x.c == __y.c;  // 直接比较底层容器
}

template <class _Tp, class _Seq>
bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) {
  return __x.c < __y.c;
}

其他操作符（!=、>、<=、>=）在定义了__STL_FUNCTION_TMPL_PARTIAL_ORDER时提供：


#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Tp, class _Seq>
bool operator!=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) {
  return !(__x == __y);
}
template <class _Tp, class _Seq>
bool operator>(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) {
  return __y < __x;
}
template <class _Tp, class _Seq>
bool operator<=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) {
  return !(__y < __x);
}
template <class _Tp, class _Seq>
bool operator>=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) {
  return !(__x < __y);
}
#endif

---

2.2 queue（队列）适配器

2.2.1 设计原理

queue是对序列容器的封装，默认使用deque，提供了FIFO（先进先出）的数据结构。

与stack的区别：

stack的操作发生在同一端（尾端）
queue的入队在尾端，出队在首端


template <class _Tp, class _Sequence>
class queue {

  // 约束检查：需要同时满足首插和尾插序列的要求
  __STL_CLASS_REQUIRES(_Tp, _Assignable);
  __STL_CLASS_REQUIRES(_Sequence, _FrontInsertionSequence);   // 首插
  __STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);    // 尾插
  typedef typename _Sequence::value_type _Sequence_value_type;
  __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);

public:
  typedef typename _Sequence::value_type      value_type;
  typedef typename _Sequence::size_type       size_type;
  typedef          _Sequence                  container_type;
  typedef typename _Sequence::reference       reference;
  typedef typename _Sequence::const_reference const_reference;

protected:
  _Sequence c;

public:
  queue() : c() {}
  explicit queue(const _Sequence& __c) : c(__c) {}

  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference front() { return c.front(); }     // 队首元素
  const_reference front() const { return c.front(); }
  reference back() { return c.back(); }      // 队尾元素
  const_reference back() const { return c.back(); }
  void push(const value_type& __x) { c.push_back(__x); }   // 入队
  void pop() { c.pop_front(); }              // 出队
};

2.2.2 操作接口

| 操作 | 说明 | 底层实现 | |------|------|---------| | empty() | 判断队列是否为空 | c.empty() | | size() | 返回队列大小 | c.size() | | front() | 返回队首元素（引用） | c.front() | | back() | 返回队尾元素（引用） | c.back() | | push(x) | 入队（队尾） | c.push_back(x) | | pop() | 出队（队首） | c.pop_front() |

注意：queue要求底层容器同时满足FrontInsertionSequence和BackInsertionSequence，因此不能使用vector作为底层容器。

---

2.3 priority_queue（优先队列）适配器

2.3.1 设计原理

priority_queue是一个堆（heap）结构的队列，每次出队的元素是当前队列中优先级最高的（默认是数值最大的元素）。


template <class _Tp,
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),
          class _Compare
          __STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>) >
class priority_queue {

  // 约束检查
  __STL_CLASS_REQUIRES(_Tp, _Assignable);
  __STL_CLASS_REQUIRES(_Sequence, _Sequence);
  __STL_CLASS_REQUIRES(_Sequence, _RandomAccessContainer);  // 需要随机访问
  typedef typename _Sequence::value_type _Sequence_value_type;
  __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
  __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);  // 比较函数检查

public:
  typedef typename _Sequence::value_type      value_type;
  typedef typename _Sequence::size_type       size_type;
  typedef          _Sequence                  container_type;
  typedef typename _Sequence::reference       reference;
  typedef typename _Sequence::const_reference const_reference;

protected:
  _Sequence c;      // 底层容器（默认是vector）
  _Compare comp;   // 比较函数（默认是less，即最大值优先）

public:
  priority_queue() : c() {}
  explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}

  // 用已有序列初始化，并将其调整为堆结构
  priority_queue(const _Compare& __x, const _Sequence& __s)
    : c(__s), comp(__x)
    { make_heap(c.begin(), c.end(), comp); }

  // 用迭代器范围初始化
  template <class _InputIterator>
  priority_queue(_InputIterator __first, _InputIterator __last)
    : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }

  template <class _InputIterator>
  priority_queue(_InputIterator __first, _InputIterator __last,
                 const _Compare& __x)
    : c(__first, __last), comp(__x)
    { make_heap(c.begin(), c.end(), comp); }

  template <class _InputIterator>
  priority_queue(_InputIterator __first, _InputIterator __last,
                 const _Compare& __x, const _Sequence& __s)
  : c(__s), comp(__x)
  {
    c.insert(c.end(), __first, __last);
    make_heap(c.begin(), c.end(), comp);
  }

  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  const_reference top() const { return c.front(); }  // 堆顶是最大/最小元素

  void push(const value_type& __x) {
    __STL_TRY {
      c.push_back(__x);
      push_heap(c.begin(), c.end(), comp);  // 入堆
    }
    __STL_UNWIND(c.clear());
  }

  void pop() {
    __STL_TRY {
      pop_heap(c.begin(), c.end(), comp);  // 出堆
      c.pop_back();
    }
    __STL_UNWIND(c.clear());
  }
};

2.3.2 priority_queue的特点

底层容器：默认使用vector（需要随机访问迭代器）
比较函数：默认是less<T>，即最大值优先（大顶堆）
堆操作：使用make_heap、push_heap、pop_heap算法维护堆结构
无迭代器访问：priority_queue不提供遍历接口，只能访问堆顶

2.3.3 操作接口

| 操作 | 说明 | 底层实现 | |------|------|---------| | empty() | 判断是否为空 | c.empty() | | size() | 返回大小 | c.size() | | top() | 返回堆顶元素 | c.front() | | push(x) | 入队并调整堆 | push_back + push_heap | | pop() | 出队并调整堆 | pop_heap + pop_back |

---

2.4 容器适配器设计思想总结

2.4.1 "adapter"模式的本质

容器适配器采用委托而非继承的方式：

委托：持有底层容器对象，将操作转发
不继承：避免继承带来的耦合和复杂性

2.4.2 适配器的约束条件

| 适配器 | 底层容器要求 | 关键操作 | |--------|-------------|---------| | stack | BackInsertionSequence | push_back, pop_back, back | | queue | FrontInsertionSequence + BackInsertionSequence | push_back, pop_front, front, back | | priority_queue | RandomAccessContainer | 堆操作 |

2.4.3 默认容器选择

| 适配器 | 默认容器 | 选择原因 | |--------|---------|---------| | stack | deque | 两端操作效率高 | | queue | deque | 两端操作效率高 | | priority_queue | vector | 需要随机访问，堆操作需要连续内存 |

---

附录：典型使用场景

A.1 算法中的自定义比较


// 按字符串长度排序
sort(v.begin(), v.end(),
     [](const string& a, const string& b) { return a.size() < b.size(); });

// SGI-STL风格
struct StringLenLess : public binary_function<string, string, bool> {
  bool operator()(const string& a, const string& b) const {
    return a.size() < b.size();
  }
};
sort(v.begin(), v.end(), StringLenLess());

A.2 remove_if与条件删除


// 删除所有偶数
v.erase(remove_if(v.begin(), v.end(),
                  [](int x) { return x % 2 == 0; }), v.end());

// SGI-STL风格
v.erase(remove_if(v.begin(), v.end(),
                  bind2nd(modulus<int>(), 2)), v.end());

A.3 使用stack进行括号匹配


bool isValid(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
                return false;
        }
    }
    return st.empty();
}

A.4 使用priority_queue实现Top-K


// 找前K大的元素
priority_queue<int> pq;
for (int i = 0; i < n; ++i) {
    pq.push(arr[i]);
    if (pq.size() > k) pq.pop();
}

---

本文档参考SGI-STL v3.3源码及侯捷《STL源码剖析》