stl_vector.h

Go to the documentation of this file.

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

// Copyright (C) 2001, 2002, 2003 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// 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
    {
      struct _Vector_impl 
    : public _Alloc {
    _Tp*           _M_start;
    _Tp*           _M_finish;
    _Tp*           _M_end_of_storage;
    _Vector_impl (_Alloc const& __a)
      : _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
    { }
      };
      
    public:
      typedef _Alloc allocator_type;

      allocator_type
      get_allocator() const { return *static_cast<const _Alloc*>(&this->_M_impl); }

      _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 = allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>
    {
      // Concept requirements.
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)

      typedef _Vector_base<_Tp, _Alloc>         _Base;
      typedef vector<_Tp, _Alloc>           vector_type;

    public:
      typedef _Tp                    value_type;
      typedef typename _Alloc::pointer                   pointer;
      typedef typename _Alloc::const_pointer             const_pointer;
      typedef typename _Alloc::reference                 reference;
      typedef typename _Alloc::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 typename _Base::allocator_type         allocator_type;

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

    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) { }

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

      explicit
      vector(size_type __n)
      : _Base(__n, allocator_type())
      { this->_M_impl._M_finish = std::uninitialized_fill_n(this->_M_impl._M_start,
                            __n, value_type()); }

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

      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 _Is_integer<_InputIterator>::_Integral _Integral;
      _M_initialize_dispatch(__first, __last, _Integral());
    }

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

      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 _Is_integer<_InputIterator>::_Integral _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, const value_type& __x)
      {
    if (__new_size < size())
      erase(begin() + __new_size, end());
    else
      insert(end(), __new_size - size(), __x);
      }

      void
      resize(size_type __new_size) { resize(__new_size, value_type()); }

      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); }

      // [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)
      {
        std::_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;
    std::_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 _Is_integer<_InputIterator>::_Integral _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() { erase(begin(), end()); }

    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(__first, __last, __result);
          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;
      this->_M_impl._M_finish = std::uninitialized_fill_n(this->_M_impl._M_start,
                              __n, __value);
    }

      // 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 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, 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, forward_iterator_tag)
        {
      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(__first, __last,
                            this->_M_impl._M_start);
    }


      // 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 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,
              input_iterator_tag);

      // Called by the second assign_dispatch above
      template<typename _ForwardIterator>
        void
        _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
              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 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, input_iterator_tag);

      // Called by the second insert_dispatch above
      template<typename _ForwardIterator>
        void
        _M_range_insert(iterator __pos, _ForwardIterator __first,
            _ForwardIterator __last, 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 */

---