stl_deque.h

gcc-you can use this code to learn something about gcc, and inquire further into linux,

  
    // iterators
    /**
     *  Returns a read/write iterator that points to the first element in the
     *  %deque.  Iteration is done in ordinary element order.
    */
    iterator
    begin() { return _M_start; }
  
    /**
     *  Returns a read-only (constant) iterator that points to the first element
     *  in the %deque.  Iteration is done in ordinary element order.
    */
    const_iterator
    begin() const { return _M_start; }
  
    /**
     *  Returns a read/write iterator that points one past the last element in
     *  the %deque.  Iteration is done in ordinary element order.
    */
    iterator
    end() { return _M_finish; }
  
    /**
     *  Returns a read-only (constant) iterator that points one past the last
     *  element in the %deque.  Iteration is done in ordinary element order.
    */
    const_iterator
    end() const { return _M_finish; }
  
    /**
     *  Returns a read/write reverse iterator that points to the last element in
     *  the %deque.  Iteration is done in reverse element order.
    */
    reverse_iterator
    rbegin() { return reverse_iterator(_M_finish); }
  
    /**
     *  Returns a read-only (constant) reverse iterator that points to the last
     *  element in the %deque.  Iteration is done in reverse element order.
    */
    const_reverse_iterator
    rbegin() const { return const_reverse_iterator(_M_finish); }
  
    /**
     *  Returns a read/write reverse iterator that points to one before the
     *  first element in the %deque.  Iteration is done in reverse element
     *  order.
    */
    reverse_iterator
    rend() { return reverse_iterator(_M_start); }
  
    /**
     *  Returns a read-only (constant) reverse iterator that points to one
     *  before the first element in the %deque.  Iteration is done in reverse
     *  element order.
    */
    const_reverse_iterator
    rend() const { return const_reverse_iterator(_M_start); }
  
    // [23.2.1.2] capacity
    /**  Returns the number of elements in the %deque.  */
    size_type
    size() const { return _M_finish - _M_start; }
  
    /**  Returns the size() of the largest possible %deque.  */
    size_type
    max_size() const { return size_type(-1); }
  
    /**
     *  @brief  Resizes the %deque to the specified number of elements.
     *  @param  new_size  Number of elements the %deque should contain.
     *  @param  x  Data with which new elements should be populated.
     *
     *  This function will %resize the %deque to the specified number of
     *  elements.  If the number is smaller than the %deque's current size the
     *  %deque is truncated, otherwise the %deque is extended and new elements
     *  are populated with given data.
    */
    void
    resize(size_type __new_size, const value_type& __x)
    {
      const size_type __len = size();
      if (__new_size < __len) 
        erase(_M_start + __new_size, _M_finish);
      else
        insert(_M_finish, __new_size - __len, __x);
    }
  
    /**
     *  @brief  Resizes the %deque to the specified number of elements.
     *  @param  new_size  Number of elements the %deque should contain.
     *
     *  This function will resize the %deque to the specified number of
     *  elements.  If the number is smaller than the %deque's current size the
     *  %deque is truncated, otherwise the %deque is extended and new elements
     *  are default-constructed.
    */
    void
    resize(size_type new_size) { resize(new_size, value_type()); }
  
    /**
     *  Returns true if the %deque is empty.  (Thus begin() would equal end().)
    */
    bool empty() const { return _M_finish == _M_start; }
  
    // element access
    /**
     *  @brief  Subscript access to the data contained in the %deque.
     *  @param  n  The index of the element for which data should be accessed.
     *  @return  Read/write reference to data.
     *
     *  This operator allows for easy, array-style, data access.
     *  Note that data access with this operator is unchecked and out_of_range
     *  lookups are not defined. (For checked lookups see at().)
    */
    reference
    operator[](size_type __n) { return _M_start[difference_type(__n)]; }
  
    /**
     *  @brief  Subscript access to the data contained in the %deque.
     *  @param  n  The index of the element for which data should be accessed.
     *  @return  Read-only (constant) reference to data.
     *
     *  This operator allows for easy, array-style, data access.
     *  Note that data access with this operator is unchecked and out_of_range
     *  lookups are not defined. (For checked lookups see at().)
    */
    const_reference
    operator[](size_type __n) const { return _M_start[difference_type(__n)]; }
  
  protected:
    /// @if maint Safety check used only from at().  @endif
    void
    _M_range_check(size_type __n) const
    {
      if (__n >= this->size())
        __throw_out_of_range("deque [] access out of range");
    }
  
  public:
    /**
     *  @brief  Provides access to the data contained in the %deque.
     *  @param  n  The index of the element for which data should be accessed.
     *  @return  Read/write reference to data.
     *  @throw  std::out_of_range  If @a n is an invalid index.
     *
     *  This function provides for safer data access.  The parameter is first
     *  checked that it is in the range of the deque.  The function throws
     *  out_of_range if the check fails.
    */
    reference
    at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
  
    /**
     *  @brief  Provides access to the data contained in the %deque.
     *  @param  n  The index of the element for which data should be accessed.
     *  @return  Read-only (constant) reference to data.
     *  @throw  std::out_of_range  If @a n is an invalid index.
     *
     *  This function provides for safer data access.  The parameter is first
     *  checked that it is in the range of the deque.  The function throws
     *  out_of_range if the check fails.
    */
    const_reference
    at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
  
    /**
     *  Returns a read/write reference to the data at the first element of the
     *  %deque.
    */
    reference
    front() { return *_M_start; }
  
    /**
     *  Returns a read-only (constant) reference to the data at the first
     *  element of the %deque.
    */
    const_reference
    front() const { return *_M_start; }
  
    /**
     *  Returns a read/write reference to the data at the last element of the
     *  %deque.
    */
    reference
    back()
    {
      iterator __tmp = _M_finish;
      --__tmp;
      return *__tmp;
    }
  
    /**
     *  Returns a read-only (constant) reference to the data at the last
     *  element of the %deque.
    */
    const_reference
    back() const
    {
      const_iterator __tmp = _M_finish;
      --__tmp;
      return *__tmp;
    }
  
    // [23.2.1.2] modifiers
    /**
     *  @brief  Add data to the front of the %deque.
     *  @param  x  Data to be added.
     *
     *  This is a typical stack operation.  The function creates an element at
     *  the front of the %deque and assigns the given data to it.  Due to the
     *  nature of a %deque this operation can be done in constant time.
    */
    void
    push_front(const value_type& __x) 
    {
      if (_M_start._M_cur != _M_start._M_first) {
        _Construct(_M_start._M_cur - 1, __x);
        --_M_start._M_cur;
      }
      else
        _M_push_front_aux(__x);
    }
  
  #ifdef _GLIBCPP_DEPRECATED
    /**
     *  @brief  Add data to the front of the %deque.
     *
     *  This is a typical stack operation.  The function creates a
     *  default-constructed element at the front of the %deque.  Due to the
     *  nature of a %deque this operation can be done in constant time.  You
     *  should consider using push_front(value_type()) instead.
     *
     *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
     *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
     *        c++config.h.
    */
    void
    push_front()
    {
      if (_M_start._M_cur != _M_start._M_first) {
        _Construct(_M_start._M_cur - 1);
        --_M_start._M_cur;
      }
      else
        _M_push_front_aux();
    }
  #endif
  
    /**
     *  @brief  Add data to the end of the %deque.
     *  @param  x  Data to be added.
     *
     *  This is a typical stack operation.  The function creates an element at
     *  the end of the %deque and assigns the given data to it.  Due to the
     *  nature of a %deque this operation can be done in constant time.
    */
    void
    push_back(const value_type& __x)
    {
      if (_M_finish._M_cur != _M_finish._M_last - 1) {
        _Construct(_M_finish._M_cur, __x);
        ++_M_finish._M_cur;
      }
      else
        _M_push_back_aux(__x);
    }
  
  #ifdef _GLIBCPP_DEPRECATED
    /**
     *  @brief  Add data to the end of the %deque.
     *
     *  This is a typical stack operation.  The function creates a
     *  default-constructed element at the end of the %deque.  Due to the nature
     *  of a %deque this operation can be done in constant time.  You should
     *  consider using push_back(value_type()) instead.
     *
     *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
     *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
     *        c++config.h.
    */
    void
    push_back()
    {
      if (_M_finish._M_cur != _M_finish._M_last - 1) {
        _Construct(_M_finish._M_cur);
        ++_M_finish._M_cur;
      }
      else
        _M_push_back_aux();
    }
  #endif
  
    /**
     *  @brief  Removes first element.
     *
     *  This is a typical stack operation.  It shrinks the %deque by one.
     *
     *  Note that no data is returned, and if the first element's data is
     *  needed, it should be retrieved before pop_front() is called.
    */
    void
    pop_front()
    {
      if (_M_start._M_cur != _M_start._M_last - 1) {
        _Destroy(_M_start._M_cur);
        ++_M_start._M_cur;
      }
      else 
        _M_pop_front_aux();
    }
  
    /**
     *  @brief  Removes last element.
     *
     *  This is a typical stack operation.  It shrinks the %deque by one.
     *
     *  Note that no data is returned, and if the last element's data is
     *  needed, it should be retrieved before pop_back() is called.
    */
    void
    pop_back()
    {
      if (_M_finish._M_cur != _M_finish._M_first) {
        --_M_finish._M_cur;
        _Destroy(_M_finish._M_cur);
      }
      else
        _M_pop_back_aux();
    }
  
    /**
     *  @brief  Inserts given value into %deque before specified iterator.
     *  @param  position  An iterator into the %deque.
     *  @param  x  Data to be inserted.
     *  @return  An iterator that points to the inserted data.
     *
     *  This function will insert a copy of the given value before the specified
     *  location.
    */
    iterator
    insert(iterator position, const value_type& __x);
  
  #ifdef _GLIBCPP_DEPRECATED
    /**
     *  @brief  Inserts an element into the %deque.
     *  @param  position  An iterator into the %deque.
     *  @return  An iterator that points to the inserted element.
     *
     *  This function will insert a default-constructed element before the
     *  specified location.  You should consider using
     *  insert(position,value_type()) instead.
     *
     *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
     *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
     *        c++config.h.
    */
    iterator
    insert(iterator __position)
    { return insert(__position, value_type()); }
  #endif
  
    /**
     *  @brief  Inserts a number of copies of given data into the %deque.
     *  @param  position  An iterator into the %deque.
     *  @param  n  Number of elements to be inserted.
     *  @param  x  Data to be inserted.
     *
     *  This function will insert a specified number of copies of the given data
     *  before the location specified by @a position.
    */
    void
    insert(iterator __position, size_type __n, const value_type& __x)
    { _M_fill_insert(__position, __n, __x); }
  
    /**
     *  @brief  Inserts a range into the %deque.
     *  @param  pos  An iterator into the %deque.
     *  @param  first  An input iterator.
     *  @param  last   An input iterator.
     *
     *  This function will insert copies of the data in the range [first,last)
     *  into the %deque before the location specified by @a pos.  This is
     *  known as "range insert."
    */
    template<typename _InputIterator>
      void
      insert(iterator __pos, _InputIterator __first, _InputIterator __last)
      {
        // Check whether it's an integral type.  If so, it's not an iterator.
        typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
        _M_insert_dispatch(__pos, __first, __last, _Integral());
      }
  
    /**
     *  @brief  Remove element at given position.
     *  @param  position  Iterator pointing to element to be erased.
     *  @return  An iterator pointing to the next element (or end()).
     *
     *  This function will erase the element at the given position and thus