stl_vector.h

Go to the documentation of this file.

// Vector implementation -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this  software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

#ifndef _VECTOR_H
#define _VECTOR_H 1

#include <bits/stl_iterator_base_funcs.h>
#include <bits/functexcept.h>
#include <bits/concept_check.h>

namespace _GLIBCXX_STD
{
  template<typename _Tp, typename _Alloc>
    struct _Vector_base
    {
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

      struct _Vector_impl 
      : public _Tp_alloc_type
      {
    _Tp*           _M_start;
    _Tp*           _M_finish;
    _Tp*           _M_end_of_storage;
    _Vector_impl(_Tp_alloc_type const& __a)
    : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
    { }
      };
      
    public:
      typedef _Alloc allocator_type;

      _Tp_alloc_type&
      _M_get_Tp_allocator()
      { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }

      const _Tp_alloc_type&
      _M_get_Tp_allocator() const
      { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }

      allocator_type
      get_allocator() const
      { return _M_get_Tp_allocator(); }

      _Vector_base(const allocator_type& __a)
      : _M_impl(__a)
      { }

      _Vector_base(size_t __n, const allocator_type& __a)
      : _M_impl(__a)
      {
    this->_M_impl._M_start = this->_M_allocate(__n);
    this->_M_impl._M_finish = this->_M_impl._M_start;
    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
      }

      ~_Vector_base()
      { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
              - this->_M_impl._M_start); }

    public:
      _Vector_impl _M_impl;

      _Tp*
      _M_allocate(size_t __n)
      { return _M_impl.allocate(__n); }

      void
      _M_deallocate(_Tp* __p, size_t __n)
      {
    if (__p)
      _M_impl.deallocate(__p, __n);
      }
    };


  template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>
    {
      // Concept requirements.
      typedef typename _Alloc::value_type                _Alloc_value_type;
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
      
      typedef _Vector_base<_Tp, _Alloc>          _Base;
      typedef vector<_Tp, _Alloc>            vector_type;
      typedef typename _Base::_Tp_alloc_type         _Tp_alloc_type;

    public:
      typedef _Tp                    value_type;
      typedef typename _Tp_alloc_type::pointer           pointer;
      typedef typename _Tp_alloc_type::const_pointer     const_pointer;
      typedef typename _Tp_alloc_type::reference         reference;
      typedef typename _Tp_alloc_type::const_reference   const_reference;
      typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
      typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
      const_iterator;
      typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
      typedef std::reverse_iterator<iterator>        reverse_iterator;
      typedef size_t                     size_type;
      typedef ptrdiff_t                  difference_type;
      typedef _Alloc                                 allocator_type;

    protected:
      using _Base::_M_allocate;
      using _Base::_M_deallocate;
      using _Base::_M_impl;
      using _Base::_M_get_Tp_allocator;

    public:
      // [23.2.4.1] construct/copy/destroy
      // (assign() and get_allocator() are also listed in this section)
      explicit
      vector(const allocator_type& __a = allocator_type())
      : _Base(__a)
      { }

      explicit
      vector(size_type __n, const value_type& __value = value_type(),
         const allocator_type& __a = allocator_type())
      : _Base(__n, __a)
      {
    std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
                      _M_get_Tp_allocator());
    this->_M_impl._M_finish = this->_M_impl._M_start + __n;
      }

      vector(const vector& __x)
      : _Base(__x.size(), __x.get_allocator())
      { this->_M_impl._M_finish =
      std::__uninitialized_copy_a(__x.begin(), __x.end(),
                      this->_M_impl._M_start,
                      _M_get_Tp_allocator());
      }

      template<typename _InputIterator>
        vector(_InputIterator __first, _InputIterator __last,
           const allocator_type& __a = allocator_type())
    : _Base(__a)
        {
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_initialize_dispatch(__first, __last, _Integral());
    }

      ~vector()
      { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
              _M_get_Tp_allocator());
      }

      vector&
      operator=(const vector& __x);

      void
      assign(size_type __n, const value_type& __val)
      { _M_fill_assign(__n, __val); }

      template<typename _InputIterator>
        void
        assign(_InputIterator __first, _InputIterator __last)
        {
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_assign_dispatch(__first, __last, _Integral());
    }

      using _Base::get_allocator;

      // iterators
      iterator
      begin()
      { return iterator (this->_M_impl._M_start); }

      const_iterator
      begin() const
      { return const_iterator (this->_M_impl._M_start); }

      iterator
      end()
      { return iterator (this->_M_impl._M_finish); }

      const_iterator
      end() const
      { return const_iterator (this->_M_impl._M_finish); }

      reverse_iterator
      rbegin()
      { return reverse_iterator(end()); }

      const_reverse_iterator
      rbegin() const
      { return const_reverse_iterator(end()); }

      reverse_iterator
      rend()
      { return reverse_iterator(begin()); }

      const_reverse_iterator
      rend() const
      { return const_reverse_iterator(begin()); }

      // [23.2.4.2] capacity
      size_type
      size() const
      { return size_type(end() - begin()); }

      size_type
      max_size() const
      { return size_type(-1) / sizeof(value_type); }

      void
      resize(size_type __new_size, value_type __x = value_type())
      {
    if (__new_size < size())
      erase(begin() + __new_size, end());
    else
      insert(end(), __new_size - size(), __x);
      }

      size_type
      capacity() const
      { return size_type(const_iterator(this->_M_impl._M_end_of_storage)
             - begin()); }

      bool
      empty() const
      { return begin() == end(); }

      void
      reserve(size_type __n);

      // element access
      reference
      operator[](size_type __n)
      { return *(begin() + __n); }

      const_reference
      operator[](size_type __n) const
      { return *(begin() + __n); }

    protected:
      void
      _M_range_check(size_type __n) const
      {
    if (__n >= this->size())
      __throw_out_of_range(__N("vector::_M_range_check"));
      }

    public:
      reference
      at(size_type __n)
      {
    _M_range_check(__n);
    return (*this)[__n]; 
      }

      const_reference
      at(size_type __n) const
      {
    _M_range_check(__n);
    return (*this)[__n];
      }

      reference
      front()
      { return *begin(); }

      const_reference
      front() const
      { return *begin(); }

      reference
      back()
      { return *(end() - 1); }
      
      const_reference
      back() const
      { return *(end() - 1); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // DR 464. Suggestion for new member functions in standard containers.
      // data access
      pointer
      data()
      { return pointer(this->_M_impl._M_start); }

      const_pointer
      data() const
      { return const_pointer(this->_M_impl._M_start); }

      // [23.2.4.3] modifiers
      void
      push_back(const value_type& __x)
      {
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
      {
        this->_M_impl.construct(this->_M_impl._M_finish, __x);
        ++this->_M_impl._M_finish;
      }
    else
      _M_insert_aux(end(), __x);
      }

      void
      pop_back()
      {
    --this->_M_impl._M_finish;
    this->_M_impl.destroy(this->_M_impl._M_finish);
      }

      iterator
      insert(iterator __position, const value_type& __x);

      void
      insert(iterator __position, size_type __n, const value_type& __x)
      { _M_fill_insert(__position, __n, __x); }

      template<typename _InputIterator>
        void
        insert(iterator __position, _InputIterator __first,
           _InputIterator __last)
        {
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_insert_dispatch(__position, __first, __last, _Integral());
    }

      iterator
      erase(iterator __position);

      iterator
      erase(iterator __first, iterator __last);

      void
      swap(vector& __x)
      {
    std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
    std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
    std::swap(this->_M_impl._M_end_of_storage,
          __x._M_impl._M_end_of_storage);
      }

      void
      clear()
      {
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
              _M_get_Tp_allocator());
    this->_M_impl._M_finish = this->_M_impl._M_start;
      }

    protected:
      template<typename _ForwardIterator>
        pointer
        _M_allocate_and_copy(size_type __n,
                 _ForwardIterator __first, _ForwardIterator __last)
        {
      pointer __result = this->_M_allocate(__n);
      try
        {
          std::__uninitialized_copy_a(__first, __last, __result,
                      _M_get_Tp_allocator());
          return __result;
        }
      catch(...)
        {
          _M_deallocate(__result, __n);
          __throw_exception_again;
        }
    }


      // Internal constructor functions follow.

      // Called by the range constructor to implement [23.1.1]/9
      template<typename _Integer>
        void
        _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
        {
      this->_M_impl._M_start = _M_allocate(__n);
      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
      std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
                    _M_get_Tp_allocator());
      this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
    }

      // Called by the range constructor to implement [23.1.1]/9
      template<typename _InputIterator>
        void
        _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
                   __false_type)
        {
      typedef typename std::iterator_traits<_InputIterator>::
	    iterator_category _IterCategory;
      _M_range_initialize(__first, __last, _IterCategory());
    }

      // Called by the second initialize_dispatch above
      template<typename _InputIterator>
        void
        _M_range_initialize(_InputIterator __first,
                _InputIterator __last, std::input_iterator_tag)
        {
      for (; __first != __last; ++__first)
        push_back(*__first);
    }

      // Called by the second initialize_dispatch above
      template<typename _ForwardIterator>
        void
        _M_range_initialize(_ForwardIterator __first,
                _ForwardIterator __last, std::forward_iterator_tag)
        {
      const size_type __n = std::distance(__first, __last);
      this->_M_impl._M_start = this->_M_allocate(__n);
      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
      this->_M_impl._M_finish =
        std::__uninitialized_copy_a(__first, __last,
                    this->_M_impl._M_start,
                    _M_get_Tp_allocator());
    }


      // Internal assign functions follow.  The *_aux functions do the actual
      // assignment work for the range versions.

      // Called by the range assign to implement [23.1.1]/9
      template<typename _Integer>
        void
        _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
        {
      _M_fill_assign(static_cast<size_type>(__n),
             static_cast<value_type>(__val));
    }

      // Called by the range assign to implement [23.1.1]/9
      template<typename _InputIterator>
        void
        _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
               __false_type)
        {
      typedef typename std::iterator_traits<_InputIterator>::
	    iterator_category _IterCategory;
      _M_assign_aux(__first, __last, _IterCategory());
    }

      // Called by the second assign_dispatch above
      template<typename _InputIterator>
        void
        _M_assign_aux(_InputIterator __first, _InputIterator __last,
              std::input_iterator_tag);

      // Called by the second assign_dispatch above
      template<typename _ForwardIterator>
        void
        _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
              std::forward_iterator_tag);

      // Called by assign(n,t), and the range assign when it turns out
      // to be the same thing.
      void
      _M_fill_assign(size_type __n, const value_type& __val);


      // Internal insert functions follow.

      // Called by the range insert to implement [23.1.1]/9
      template<typename _Integer>
        void
        _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
               __true_type)
        {
      _M_fill_insert(__pos, static_cast<size_type>(__n),
             static_cast<value_type>(__val));
    }

      // Called by the range insert to implement [23.1.1]/9
      template<typename _InputIterator>
        void
        _M_insert_dispatch(iterator __pos, _InputIterator __first,
               _InputIterator __last, __false_type)
        {
      typedef typename std::iterator_traits<_InputIterator>::
	    iterator_category _IterCategory;
      _M_range_insert(__pos, __first, __last, _IterCategory());
    }

      // Called by the second insert_dispatch above
      template<typename _InputIterator>
        void
        _M_range_insert(iterator __pos, _InputIterator __first,
            _InputIterator __last, std::input_iterator_tag);

      // Called by the second insert_dispatch above
      template<typename _ForwardIterator>
        void
        _M_range_insert(iterator __pos, _ForwardIterator __first,
            _ForwardIterator __last, std::forward_iterator_tag);

      // Called by insert(p,n,x), and the range insert when it turns out to be
      // the same thing.
      void
      _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);

      // Called by insert(p,x)
      void
      _M_insert_aux(iterator __position, const value_type& __x);
    };


  template<typename _Tp, typename _Alloc>
    inline bool
    operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return (__x.size() == __y.size()
          && std::equal(__x.begin(), __x.end(), __y.begin())); }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return std::lexicographical_compare(__x.begin(), __x.end(),
                      __y.begin(), __y.end()); }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return !(__x == __y); }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return __y < __x; }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return !(__y < __x); }

  template<typename _Tp, typename _Alloc>
    inline bool
    operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return !(__x < __y); }

  template<typename _Tp, typename _Alloc>
    inline void
    swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
    { __x.swap(__y); }
} // namespace std

#endif /* _VECTOR_H */

---