stl_rope.h

TSP问题的一个类库 有源代码和stl

        if (0 != _M_buf_ptr && (__next = _M_buf_ptr + 1) < _M_buf_end) {
            _M_buf_ptr = __next;
            ++_M_current_pos;
        } else {
            _M_incr(1);
        }
        return *this;
    }
    _Rope_const_iterator& operator+=(ptrdiff_t __n) {
        if (__n >= 0) {
            _M_incr(__n);
        } else {
            _M_decr(-__n);
        }
        return *this;
    }
    _Rope_const_iterator& operator--() {
        _M_decr(1);
        return *this;
    }
    _Rope_const_iterator& operator-=(ptrdiff_t __n) {
        if (__n >= 0) {
            _M_decr(__n);
        } else {
            _M_incr(-__n);
        }
        return *this;
    }
    _Rope_const_iterator operator++(int) {
        size_t __old_pos = _M_current_pos;
        _M_incr(1);
        return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos);
        // This makes a subsequent dereference expensive.
        // Perhaps we should instead copy the iterator
        // if it has a valid cache?
    }
    _Rope_const_iterator operator--(int) {
        size_t __old_pos = _M_current_pos;
        _M_decr(1);
        return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos);
    }
#if defined(__STL_MEMBER_TEMPLATES) && defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
    template<class _CharT2, class _Alloc2>
    friend _Rope_const_iterator<_CharT2,_Alloc2> operator-
        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
         ptrdiff_t __n);
    template<class _CharT2, class _Alloc2>
    friend _Rope_const_iterator<_CharT2,_Alloc2> operator+
        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
         ptrdiff_t __n);
    template<class _CharT2, class _Alloc2>
    friend _Rope_const_iterator<_CharT2,_Alloc2> operator+
        (ptrdiff_t __n,
         const _Rope_const_iterator<_CharT2,_Alloc2>& __x);
#else
    friend _Rope_const_iterator<_CharT,_Alloc> operator- __STL_NULL_TMPL_ARGS
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         ptrdiff_t __n);
    friend _Rope_const_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         ptrdiff_t __n);
    friend _Rope_const_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
        (ptrdiff_t __n,
         const _Rope_const_iterator<_CharT,_Alloc>& __x);
#endif

    reference operator[](size_t __n) {
        return rope<_CharT,_Alloc>::_S_fetch(_M_root, _M_current_pos + __n);
    }

#if defined(__STL_MEMBER_TEMPLATES) && defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
    template<class _CharT2, class _Alloc2>
    friend bool operator==
        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
         const _Rope_const_iterator<_CharT2,_Alloc2>& __y);
    template<class _CharT2, class _Alloc2>
    friend bool operator< 
        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
         const _Rope_const_iterator<_CharT2,_Alloc2>& __y);
    template<class _CharT2, class _Alloc2>
    friend ptrdiff_t operator-
        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
         const _Rope_const_iterator<_CharT2,_Alloc2>& __y);
#else
    friend bool operator== __STL_NULL_TMPL_ARGS
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         const _Rope_const_iterator<_CharT,_Alloc>& __y);
    friend bool operator< __STL_NULL_TMPL_ARGS
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         const _Rope_const_iterator<_CharT,_Alloc>& __y);
    friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         const _Rope_const_iterator<_CharT,_Alloc>& __y);
#endif
};

template<class _CharT, class _Alloc>
class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> {
    friend class rope<_CharT,_Alloc>;
  protected:
    rope<_CharT,_Alloc>* _M_root_rope;
        // root is treated as a cached version of this,
        // and is used to detect changes to the underlying
        // rope.
        // Root is included in the reference count.
        // This is necessary so that we can detect changes reliably.
        // Unfortunately, it requires careful bookkeeping for the
        // nonGC case.
    _Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos)
      : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr, __pos),
        _M_root_rope(__r) 
      { _RopeRep::_S_ref(_M_root); }

    void _M_check();
  public:
    typedef _Rope_char_ref_proxy<_CharT,_Alloc>  reference;
    typedef _Rope_char_ref_proxy<_CharT,_Alloc>* pointer;

  public:
    rope<_CharT,_Alloc>& container() { return *_M_root_rope; }
    _Rope_iterator() {
        _M_root = 0;  // Needed for reference counting.
    };
    _Rope_iterator(const _Rope_iterator& __x) :
        _Rope_iterator_base<_CharT,_Alloc>(__x) {
        _M_root_rope = __x._M_root_rope;
        _RopeRep::_S_ref(_M_root);
    }
    _Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos);
    ~_Rope_iterator() {
        _RopeRep::_S_unref(_M_root);
    }
    _Rope_iterator& operator= (const _Rope_iterator& __x) {
        _RopeRep* __old = _M_root;

        _RopeRep::_S_ref(__x._M_root);
        if (0 != __x._M_buf_ptr) {
            _M_root_rope = __x._M_root_rope;
            *(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x;
        } else {
            _M_current_pos = __x._M_current_pos;
            _M_root = __x._M_root;
            _M_root_rope = __x._M_root_rope;
            _M_buf_ptr = 0;
        }
        _RopeRep::_S_unref(__old);
        return(*this);
    }
    reference operator*() {
        _M_check();
        if (0 == _M_buf_ptr) {
            return _Rope_char_ref_proxy<_CharT,_Alloc>(
               _M_root_rope, _M_current_pos);
        } else {
            return _Rope_char_ref_proxy<_CharT,_Alloc>(
               _M_root_rope, _M_current_pos, *_M_buf_ptr);
        }
    }
    _Rope_iterator& operator++() {
        _M_incr(1);
        return *this;
    }
    _Rope_iterator& operator+=(ptrdiff_t __n) {
        if (__n >= 0) {
            _M_incr(__n);
        } else {
            _M_decr(-__n);
        }
        return *this;
    }
    _Rope_iterator& operator--() {
        _M_decr(1);
        return *this;
    }
    _Rope_iterator& operator-=(ptrdiff_t __n) {
        if (__n >= 0) {
            _M_decr(__n);
        } else {
            _M_incr(-__n);
        }
        return *this;
    }
    _Rope_iterator operator++(int) {
        size_t __old_pos = _M_current_pos;
        _M_incr(1);
        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
    }
    _Rope_iterator operator--(int) {
        size_t __old_pos = _M_current_pos;
        _M_decr(1);
        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
    }
    reference operator[](ptrdiff_t __n) {
        return _Rope_char_ref_proxy<_CharT,_Alloc>(
          _M_root_rope, _M_current_pos + __n);
    }

#if defined(__STL_MEMBER_TEMPLATES) && defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
    template<class _CharT2, class _Alloc2>
    friend bool operator==
        (const _Rope_iterator<_CharT2,_Alloc2>& __x,
         const _Rope_iterator<_CharT2,_Alloc2>& __y);
    template<class _CharT2, class _Alloc2>
    friend bool operator<
        (const _Rope_iterator<_CharT2,_Alloc2>& __x,
         const _Rope_iterator<_CharT2,_Alloc2>& __y);
    template<class _CharT2, class _Alloc2>
    friend ptrdiff_t operator-
        (const _Rope_iterator<_CharT2,_Alloc2>& __x,
         const _Rope_iterator<_CharT2,_Alloc2>& __y);
    template<class _CharT2, class _Alloc2>
    friend _Rope_iterator<_CharT2,_Alloc2> operator-
        (const _Rope_iterator<_CharT2,_Alloc2>& __x,
         ptrdiff_t __n);
    template<class _CharT2, class _Alloc2>
    friend _Rope_iterator<_CharT2,_Alloc2> operator+
        (const _Rope_iterator<_CharT2,_Alloc2>& __x,
         ptrdiff_t __n);
    template<class _CharT2, class _Alloc2>
    friend _Rope_iterator<_CharT2,_Alloc2> operator+
        (ptrdiff_t __n,
         const _Rope_iterator<_CharT2,_Alloc2>& __x);
#else
    friend bool operator== __STL_NULL_TMPL_ARGS
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         const _Rope_iterator<_CharT,_Alloc>& __y);
    friend bool operator< __STL_NULL_TMPL_ARGS
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         const _Rope_iterator<_CharT,_Alloc>& __y);
    friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         const _Rope_iterator<_CharT,_Alloc>& __y);
    friend _Rope_iterator<_CharT,_Alloc> operator- __STL_NULL_TMPL_ARGS
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         ptrdiff_t __n);
    friend _Rope_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         ptrdiff_t __n);
    friend _Rope_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
        (ptrdiff_t __n,
         const _Rope_iterator<_CharT,_Alloc>& __x);
#endif
};

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1375
#endif

//  The rope base class encapsulates
//  the differences between SGI-style allocators and standard-conforming
//  allocators.

#ifdef __STL_USE_STD_ALLOCATORS

// Base class for ordinary allocators.
template <class _CharT, class _Allocator, bool _IsStatic>
class _Rope_alloc_base {
public:
  typedef _Rope_RopeRep<_CharT,_Allocator> _RopeRep;
  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return _M_data_allocator; }
  _Rope_alloc_base(_RopeRep *__t, const allocator_type& __a)
        : _M_tree_ptr(__t), _M_data_allocator(__a) {}
  _Rope_alloc_base(const allocator_type& __a)
        : _M_data_allocator(__a) {}
  
protected:
  // The only data members of a rope:
    allocator_type _M_data_allocator;
    _RopeRep* _M_tree_ptr;

# define __ROPE_DEFINE_ALLOC(_Tp, __name) \
        typedef typename \
          _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
        _Tp* __name##_allocate(size_t __n) const \
          { return __name##Allocator(_M_data_allocator).allocate(__n); } \
        void __name##_deallocate(_Tp *__p, size_t __n) const \
                { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
  __ROPE_DEFINE_ALLOCS(_Allocator)
# undef __ROPE_DEFINE_ALLOC
};

// Specialization for allocators that have the property that we don't
//  actually have to store an allocator object.  
template <class _CharT, class _Allocator>
class _Rope_alloc_base<_CharT,_Allocator,true> {
public:
  typedef _Rope_RopeRep<_CharT,_Allocator> _RopeRep;
  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }
  _Rope_alloc_base(_RopeRep *__t, const allocator_type&)
                : _M_tree_ptr(__t) {}
  _Rope_alloc_base(const allocator_type&) {}
  
protected:
  // The only data member of a rope:
    _RopeRep *_M_tree_ptr;

# define __ROPE_DEFINE_ALLOC(_Tp, __name) \
        typedef typename \
          _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
        typedef typename \
          _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
        static _Tp* __name##_allocate(size_t __n) \
          { return __name##Alloc::allocate(__n); } \
        static void __name##_deallocate(_Tp *__p, size_t __n) \
          { __name##Alloc::deallocate(__p, __n); }
  __ROPE_DEFINE_ALLOCS(_Allocator)
# undef __ROPE_DEFINE_ALLOC
};

template <class _CharT, class _Alloc>
struct _Rope_base 
  : public _Rope_alloc_base<_CharT,_Alloc,
                            _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
{
  typedef _Rope_alloc_base<_CharT,_Alloc,
                            _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
          _Base;
  typedef typename _Base::allocator_type allocator_type;
  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
	// The one in _Base may not be visible due to template rules.
  _Rope_base(_RopeRep* __t, const allocator_type& __a) : _Base(__t, __a) {}
  _Rope_base(const allocator_type& __a) : _Base(__a) {}
};    

#else /* !__STL_USE_STD_ALLOCATORS */

template <class _CharT, class _Alloc> 
class _Rope_base {
public:
  typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;