C_stl_notes2

**侯捷老师的C++笔记2--STL**

Deque && Queue && Stack

deque: 双向queue

avatar

  • 模拟连续空间, 实际是多个连续空间拼接
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    // bufsiz: 每个buffer所容纳的元素个数
    template <class T, class Alloc = alloc, size_t BufSize = 0>
    class deque {
    public
    typedef T value_type;
    typedef __deque_iterator<T,T&,T*,BufSize> iterator;
    protected:
    typedef pointer* map_pointer; // T**
    protected:
    iterator start;
    iterator finish;
    map_pointer map;
    size_type map_size;
    public:
    iterator begin() {return start;}
    iterator end() {return finish;}
    size_type size() const {return finish - start;}
    };
    // deque<T>::insert() ---> 会根据pos的位置判断从前面插入还是后边插入
    iterator insert(iterator position, const value_type& x) {
    if (position.cur == start.cur) {
    push_front(x); // deque最前端
    return start;
    }
    else if (position.cur == finish.cur) {
    push_back(x); // deque最尾端
    iterator tmp = finish;
    --tmp;
    return tmp;
    }
    else {
    return insert_aux(position, x);
    }
    }
    template <class T, class Alloc, size_t BufSize>
    typename deque<T, Alloc, BufSize>::__deque_iterator
    deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {
    difference_type index = pos - start;
    value_type x_copy = x;
    if (index < size() / 2) {
    push_front(front()); // 给insert的元素挪出一个位置
    ...
    copy(front2, pos1, front1); // move element
    }
    else {
    push_back(back()); // 同上
    ...
    copy_backward(pos, back2, back1);
    }
    *pos = x_copy; // insert x at position
    return pos;
    }
    // iterator 如何模拟连续空间
    difference_type operator-(const self& x) const
    {
    // 两个ite之间buffer的总长度 + itr到buffer末尾的长度 + x到buffer起始的长度
    return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
    }
    // ++
    self& operator++() {
    ++ cur;
    if (cur == last) {
    set_node(node + 1);
    cur = first;
    }
    return *this;
    }
    self operator++(int) {
    self tmp = *this;
    ++*this;
    return tmp;
    }
    void set_node(map_pointer new_node)
    {
    node = new_node;
    first = *new_node;
    last = first + difference_type(buffer_size());
    }
    // +=
    self& operator+=(difference_type n) {
    difference_type offset = n + (cur - first);
    if (offset > 0 && offset < difference_type(buffer_size()))
    // 目标位置在同一个buffer上
    cur += n;
    else {
    // -= 通用此函数
    difference_type node_offset =
    offset > 0 ? offset / difference_type(buffer_size()) :
    -difference_type((-offset - 1) / buffer_size() - 1);
    // 切到目标所在的buffer
    set_node(node + node_offset);
    cur = first + (offset - node_offset * difference_type(buffer_size()));
    }
    retrun *this;
    }
    self operator+(differnce_type n) const {
    self tmp = *this;
    return tmp += n; // 调用+=
    }
    self& operator-=(differnce_type n)
    {return *this += n;}

    queue:

    • 只有push_backpop_front
    • 不允许遍历,不提供iterator
    • 也可以选择list作为底层容器,不能选择vector, set, map
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      template<class T, class Sequence=deque<T>>
      class queue {
      ...
      public:
      typedef typename Sequence::value_type value_type;
      ...size_type, reference, const_reference
      protected:
      Sequence c; // 底层容器,默认为deque
      public:
      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();}
      };

      stack

    • 只有push_backpop_back
    • 不允许遍历,不提供iterator
    • 也可以选择list or vector作为底层容器,不能选择set, map
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      template<class T, class Sequence=deque<T>>
      class stack {
      ...
      public:
      typedef typename Sequence::value_type value_type;
      ...size_type, reference, const_reference
      protected:
      Sequence c; // 底层容器,默认为deque
      public:
      bool empty() const {return c.empty();}
      size_type size() const { return c.size();}
      reference top() {return c.top();}
      const_reference top() const {return c.top();}
      void push(const value_type& x) {c.push_back(x);}
      void pop() {c.pop_back();}
      };
0%