basic_string.h

c++编程宝典源码及Quincy99编译器 是《标准C++编程宝典》电子工业出版社的光盘

// Components for manipulating sequences of characters -*- C++ -*-

// Copyright (C) 1997-1999 Cygnus Solutions
//
// 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.

//
// ISO C++ 14882: 21 Strings library
//

#ifndef _CPP_BITS_STRING_H
#define _CPP_BITS_STRING_H	1

namespace std {

#if _GLIBCPP_USE_EXCEPTIONS
  // Internal functions for string implementation.
  extern void __out_of_range(const char *__str);
  extern void __length_error(const char *__str);
  
# define __OUTOFRANGE(__cond) \
  do { if (__cond) __out_of_range(#__cond); } while (0)
# define __LENGTHERROR(__cond) \
  do { if (__cond) __length_error(#__cond); } while (0)
#else
# include <bits/std_cassert.h>
# define __OUTOFRANGE(__cond) assert(!(__cond))
# define __LENGTHERROR(__cond) assert(!(__cond))
#endif

  // Documentation?  What's that? 
  // Nathan Myers <[e-mail]>.
  //
  // A string looks like this:
  //
  //                               	[_Rep]
  //                               	_M_length
  //  [basic_string<char_type>]		_M_capacity
  //  _M_dataplus                	_M_state
  //  _M_p ---------------->   		unnamed array of char_type
  
  // Where the _M_p points to the first character in the string, and
  // you cast it to a pointer-to-_Rep and subtract 1 to get a
  // pointer to the header.
  
  // This approach has the enormous advantage that a string object
  // requires only one allocation.  All the ugliness is confined
  // within a single pair of inline functions, which each compile to
  // a single "add" instruction: _Rep::_M_data(), and
  // string::_M_rep(); and the allocation function which gets a
  // block of raw bytes and with room enough and constructs a _Rep
  // object at the front.
  
  // The reason you want _M_data pointing to the character array and
  // not the _Rep is so that the debugger can see the string
  // contents. (Probably we should add a non-inline member to get
  // the _Rep for the debugger to use, so users can check the actual
  // string length.)
  
  // Note that the _Rep object is a POD so that you can have a
  // static "empty string" _Rep object already "constructed" before
  // static constructors have run.  The reference-count encoding is
  // chosen so that a 0 indicates one reference, so you never try to
  // destroy the empty-string _Rep object.
  
  // All but the last paragraph is considered pretty conventional
  // for a C++ string implementation.
  
  // 21.3  Template class basic_string
  template<typename _CharT, typename _Traits, typename _Alloc>
    class basic_string
    {
      // Types:
      typedef _Traits 					    traits_type;
      typedef typename _Traits::char_type 		    value_type;
      typedef _Alloc 					    allocator_type;
      typedef typename _Alloc::size_type 		    size_type;
      typedef typename _Alloc::difference_type 		    difference_type;
      typedef typename _Alloc::reference 		    reference;
      typedef typename _Alloc::const_reference 		    const_reference;
      typedef typename _Alloc::pointer 			    pointer;
      typedef typename _Alloc::const_pointer 	   	    const_pointer;
      typedef __normal_iterator<pointer, basic_string> 	    iterator;
      typedef __normal_iterator<const_pointer, basic_string> const_iterator;
      typedef reverse_iterator<const_iterator> 	const_reverse_iterator;
      typedef reverse_iterator<iterator> 		    reverse_iterator;
    
    public:
      // (Public) Data Members:

      // NB: This is an unsigned type, and thus represents the maximum
      // size that the allocator can hold.
      static const size_type npos = static_cast<size_type>(-1);

    private:
      // _Rep: string representation
      //   Invariants:
      //   1. String really contains _M_length + 1 characters; last is set
      //      to 0 only on call to c_str().  We avoid instantiating
      //      _CharT() where the interface does not require it.
      //   2. _M_capacity >= _M_length
      //      Allocated memory is always _M_capacity + (1 * sizeof(_CharT)).
      //   3. _M_state has three states:
      //      -1: leaked, one reference, no ref-copies allowed, non-const.
      //       0: one reference, non-const.
      //     n>0: n + 1 references, operations require a lock, const.
      //   4. All fields==0 is an empty string, given the extra storage
      //      beyond-the-end for a null terminator; thus, the shared
      //      empty string representation needs no constructor.

      struct _Rep
      {
	// Types:
	typedef typename _Alloc::rebind<char>::other _Raw_bytes_alloc;

	// (Public) Data members: 

	// The maximum number of individual char_type elements of an
	// individual string is determined by _S_max_size. This is the
	// value that will be returned by max_size().  (Whereas npos
	// is the maximum number of bytes the allocator can allocate.)
	// If one was to divvy up the theoretical largest size string,
	// with a terminating character and m _CharT elements, it'd
	// look like this: 
	// npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
	// Solving for m:
	// m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1 
	// In addition, this implementation quarters this ammount.
	static size_type 	_S_max_size;
	static _CharT 		_S_terminal;
	size_type 		_M_length;
	size_type 		_M_capacity;
	int 			_M_state;
	
	_CharT* 
	_M_refdata() throw()
	{ return reinterpret_cast<_CharT*> (this + 1); }

	_CharT& 
	operator[](size_t __s) throw()
	{ return _M_refdata() [__s]; }

	_CharT* 
	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
	{ return (_M_state >= 0 && __alloc1 == __alloc2) ?
	    _M_refcopy() : _M_clone(__alloc1);  }

	// Create & Destroy
	static _Rep* 
	_S_create(size_t, const _Alloc&);

	void 
	_M_dispose(const _Alloc& __a)
	{ 
	  if (_M_state-- <= 0)  
	    _M_destroy(__a); 
	}  // XXX MT

	void 
	_M_destroy(const _Alloc&) throw();

	_CharT* 
	_M_refcopy() throw()
	{ 
	  ++_M_state; 
	  return _M_refdata(); 
	}  // XXX MT

	_CharT* 
	_M_clone(const _Alloc&, size_type __res = 0);

#if _GLIBCPP_ALLOC_CONTROL
	// These function pointers allow you to modify the allocation
	// policy used by the string classes.  By default they expand by
	// powers of two, but this may be excessive for space-critical
	// applications.
	
	// Returns true if ALLOCATED is too much larger than LENGTH
	static bool (*_S_excess_slop) (size_t __length, size_t __allocated);

	inline static bool 
	__default_excess(size_t, size_t);
#else
	inline static bool 
	_S_excess_slop(size_t, size_t);
#endif
      };

      // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
      struct _Alloc_hider : _Alloc
      {
	_Alloc_hider(_CharT* __dat, const _Alloc& __a)
	: _Alloc(__a), _M_p(__dat) { }

	_CharT* _M_p; // The actual data.
      };

      mutable _Alloc_hider _M_dataplus;

      _CharT* 
      _M_data() const 
      { return  _M_dataplus._M_p; }

      _CharT* 
      _M_data(_CharT* __p) 
      { return (_M_dataplus._M_p = __p); }

      _Rep* 
      _M_rep() const
      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

      // For the internal use we have functions similar to `begin'/`end'
      // but they do not call _M_leak.
      iterator 
      _M_ibegin() const { return iterator(_M_data()); }

      iterator 
      _M_iend() const { return iterator(_M_data() + this->size()); }

      void 
      _M_leak()    // for use in begin() & non-const op[]
      { 
	if (_M_rep()->_M_state >= 0) 
	  _M_leak_hard(); 
      }

      iterator 
      _M_check(size_type __pos) const
      { 
	__OUTOFRANGE(__pos > this->size()); 
	return _M_ibegin() + __pos; 
      }

      // NB: _M_fold doesn't check for a bad __pos1 value.
      iterator 
      _M_fold(size_type __pos, size_type __off) const
      { 
	bool __testoff =  __off < this->size() - __pos;
	size_type __newoff = __testoff ? __off : this->size() - __pos;
	return (_M_ibegin() + __pos + __newoff);
      }

      // _S_copy_chars is a separate template to permit specialization
      // to optimize for the common case of pointers as iterators.
      template<class _Iterator>
        static void
        _S_copy_chars(_CharT* __p, _Iterator __j1, _Iterator __j2)
        { 
	  for (; __j1 != __j2; ++__j1, ++__p) 
	    traits_type::assign(*__p, *__j1); //these types are off
	}

      static void
      _S_copy_chars(_CharT* __p, iterator __j1, iterator __j2)
      { _S_copy_chars(__p, __j1.base(), __j2.base()); }

      static void
      _S_copy_chars(_CharT* __p, const_iterator __j1, const_iterator __j2)
      { _S_copy_chars(__p, __j1.base(), __j2.base()); }
 
      static void
      _S_copy_chars(_CharT* __p, _CharT* __j1, _CharT* __j2)
      { traits_type::copy(__p, __j1, __j2 - __j1); }

      static void
      _S_copy_chars(_CharT* __p, const _CharT* __j1, const _CharT* __j2)
      { traits_type::copy(__p, __j1, __j2 - __j1); }

      void 
      _M_mutate(size_type __pos, size_type __len1, size_type __len2);

      void 
      _M_leak_hard();

      // The following storage is init'd to 0 by the linker, resulting
      // (carefully) in an empty string with one reference.
      static size_type _S_empty_rep_storage[
      (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type)-1)/sizeof(size_type)];

      static _Rep& 
      _S_empty_rep()
      { return *reinterpret_cast<_Rep*> (&_S_empty_rep_storage); }

    public:
      // Construct/copy/destroy:
      // NB: We overload ctors in some cases instead of using default
      // arguments, per 17.4.4.4 para. 2 item 2.

      inline 
      basic_string();

      explicit 
      basic_string(const _Alloc& __a);

      // NB: per LWG issue 42, semantics different from IS:
      basic_string(const basic_string& __str);
      basic_string(const basic_string& __str, size_type __pos,
		   size_type __n = npos);
      basic_string(const basic_string& __str, size_type __pos,
		   size_type __n, const _Alloc& __a);

      basic_string(const _CharT* __s, size_type __n,
		   const _Alloc& __a = _Alloc());
      basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
      basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());

      template<class _InputIterator>
        basic_string(_InputIterator __begin, _InputIterator __end,
		     const _Alloc& __a = _Alloc());

      ~basic_string() 
      { _M_rep()->_M_dispose(this->get_allocator()); }

      basic_string& 
      operator=(const basic_string& __str) { return this->assign(__str); }

      basic_string& 
      operator=(const _CharT* __s) { return this->assign(__s); }

      basic_string& 
      operator=(_CharT __c) { return this->assign(1, __c); }

      // Iterators:
      iterator 
      begin() 
      { 
	_M_leak(); 
	return iterator(_M_data());
      }

      const_iterator 
      begin() const