string.h

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

#ifndef STANDARD_STRING
#define STANDARD_STRING

//  This is a simplified and slimmed-down version of
//  the proposed ANSI standard C++ string class, intended for interim use
//  until our compilers catch up with the standard (and our University catches
//  up with those compiler versions!).
//
//  In essence, it is a "by hand" instantiation of the std basic_string
//  template, with all references to the Allocator and Traits classes removed.
//
//  copyright 1995, S J Zeil, Old Dominion University
//
//  Permission is granted to freely copy, modify, and distribute this file
//  as long as this copyright notice is retained in full.
//  

#include <assert.h>
#include <iostream.h>
#include <stddef.h>

#ifndef NO_REVERSE_ITERATORS
#include <iterator.h>
#endif


//#define _MEMDEBUG


class string {
public:
// types:
//  typedef traits traits_type;
  typedef char value_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef char& reference;
  typedef const char& const_reference;
  typedef char* pointer;
  typedef const char* const_pointer;
  typedef pointer iterator;
  typedef const_pointer const_iterator;

#ifndef NO_REVERSE_ITERATORS
  typedef reverse_iterator<iterator, value_type, reference, difference_type>
      reverse_iterator;
  typedef reverse_iterator<const_iterator, value_type,
                           const_reference, difference_type>
      const_reverse_iterator;
#endif


  static const size_type npos;   // stands for 1 + the index of the last 
                                 //   character in a string



    // construct an object of type string



  string();
    //post: size() == 0  [creates an empty string]


  string(const string& str);
    //pre: pos <= str.size()
    //   string s1 (s2)
    //post: s1.size() == s2.size()
    //      s1 == s2

  string(const string& str, size_type pos, size_type n = npos);
    //pre: pos <= str.size()
    //   string s1 (s2, pos, n)
    //post: s1.size() == min(n, s2.size()-pos)
    //      s1 == s2.substr(pos, s1.size())


  string(const char* s, size_type n);
    //pre: s != 0 && n < npos
    //    string s1 (s, n);
    //post: s1.size() == min(n, strlen(s))
    //      for all i = 0..s1.size()-1, s1[i] == s[i]

  string(const char* s);
    // equivalent to string(s,strlen(s))

  string(size_type n, char c);
    //      string is initialized with n occurrences of same character
    //pre:
    //   string s1 (n, c);
    //post: s1.size() == n
    //      for all i = 0..s1.size()-1, s1[i] == c

#ifdef NESTED_TEMPLATES_SUPPORTED
   template<class InputIterator>
     string(InputIterator begin, InputIterator end)
       {
	 for (InputIterator i = begin; i != end; i++)
	   append(*i);
       }
#endif


  // destroy a string (invoked automatically)
  ~string();



  // assign to a string
  string& operator=(const string& str);
  string& operator=(const char* s);
  string& operator=(char c);
  string& assign(const string& str, size_type pos = 0,
                 size_type n = npos);
  string& assign(const char* s, size_type n);
  string& assign(const char* s);
  string& assign(size_type n, char c = 0);

#ifdef NESTED_TEMPLATES_SUPPORTED
  template<class InputIterator>
    string& assign(InputIterator first, InputIterator last)
      {
	assign(0);
	for (InputIterator i = first; i != last; i++)
	  append(*i);
	return *this;
      }
#endif



  // iterators
  iterator       begin();
  const_iterator begin() const;
  iterator       end();
  const_iterator end() const;

#ifndef NO_REVERSE_ITERATORS
  reverse_iterator       rbegin();
  const_reverse_iterator rbegin() const;
  reverse_iterator       rend();
  const_reverse_iterator rend() const;
#endif
  


  // size & capacity:
  size_type size() const;
    // size is the number of characters currently in the string
  
  size_type length() const;   // same as size()
  bool empty() const;         //  equivalent to (size() == 0)

  void resize(size_type n, char c);
  //pre:
  //   s1 = s2; s2.resize(n, c)
  //post: s2.size() == n
  //      s1.substr(0, min(n, s1.size())) == s2.substr(0, min(n, s1.size()))
  //      for all i in s1.size()..n-1, s2[i] == c

  void resize(size_type n);
  // equivalent to resize(n, 0)
  
  size_type max_size() const;
  // How large can any string be?

  size_type capacity() const;
  // capacity is number of characters currently allocated to this string.
  // Any operation that causes a string to grow beyond its current capacity
  // will "automatically" cause more space to be allocated.
  
  void reserve(size_type res_arg);
  //  Because the "automatic" reallocation to higher capacity can be
  //  time-consuming, you can use this to reserve the appropriate amount of
  //  storage if you know how large the string is likely to get.
  //post: capacity() >= res_arg
        


  // element access:
  
  char     operator[](size_type pos) const;
  char& operator[](size_type pos);
  //pre: pos >= 0 && pos <= size()
  //post: if pos < size(), returns char in pos'th position
  //      if pos == size(), returns 0
  
  const_reference at(size_type n) const;
  reference       at(size_type n);
  //pre: pos >= 0 && pos < size()
  //   s.at(n)
  //post: returns s[n]
  //   [Note that the case n==size() is OK for operator[], but not for at().]

  

  // modifiers:
  
  // Add to the end of a string

  string& operator+=(const string& rhs);
  string& operator+=(const char* s);
  string& operator+=(char c);

  string& append(const string& str, size_type pos = 0,
		 size_type n = npos);
  string& append(const char* s, size_type n);
  string& append(const char* s);
  string& append(size_type n, char c);

#ifdef NESTED_TEMPLATES_SUPPORTED
  template<class InputIterator>
    basic_string& append(InputIterator first, InputIterator last)
      {
	for (InputIterator i = first; i != last; i++)
	  append(*i);
      }
#endif



  // Insert within a string, moving other characters out of the way
  string& insert(size_type pos1, const string& str);
  // equivalent to insert(pos1, str, 0, npos)

  string& insert(size_type pos1, const string& str,
		 size_type pos2, size_type n);
  //pre: pos1 >= 0 && pos1 <= size()
  //     && pos2 >= 0 && pos2 <= str.size()
  //  s0 = s1; s1.insert(pos1, s2, pos2, n)

  //post: let rlen = min(n, s2.size()-pos2)
  //      s1.size() == s0.size() + rlen
  //      for all i in 0..pos1-1, s1[i] == s0[i]
  //      for all i in pos1..pos1+rlen-1, s1[i] == s2[i-pos1+pos2]
  //      for all i in pos1+rlen..s1.size()-1, s1[i] == s0[i-rlen]

  string& insert(size_type pos, const char* s, size_type n);
    // equivalent to insert(pos, string(s), 0, n)

  string& insert(size_type pos, const char* s);
    // equivalent to insert(pos, string(s), 0, strlen(s))

  string& insert(size_type pos, size_type n, char c = 0 );
    // equivalent to insert(pos, string(1,c), 0, 1)

  iterator insert(iterator p, size_type n, char c);
  //pre: p is a valid iterator on this string
  //  s0 = s1; s1.insert(p, n, c)
  //post: s1.size() = s0.size() + n
  //      for (iterator i = s1.begin(); i != p; i++)
  //                   s1[i] == s0[s0.begin()+(i-s1.begin())]
  //      for (iterator i = p; i != p+n; i++) s1[i] == c
  //      for (iterator i = p+n; i != s1.end(); i++) 
  //                   s1[i] == s0[s0.begin()+(i-s1.begin())-n]

  iterator insert(iterator p, char c = 0);
    // equivalent to insert(p, 1, c)

#ifdef NESTED_TEMPLATES_SUPPORTED
  template<class InputIterator>
    void insert(iterator p, InputIterator first, InputIterator last)
      {
	string s = substr(0, p-begin());
	for (InputIterator i = first; i != last; i++)
	  s += *i;
	s += substr(p-begin());
	assign(s);
      }
#endif

	    

  // Remove characters from within a string.
  string& erase(size_type pos = 0, size_type n = npos);
  //pre: pos >= 0 && pos <= size()
  //  s0 = s1; s1.erase(pos, n);
  //post: let xlen = min(n, size()-pos)
  //      s1.size() == s0.size() - xlen
  //      for all i in 0..pos-1, s1[i] == s0[i]
  //      for all i in pos..s1.size()-1, s1[i] == s0[i+xlen]

  string& erase(iterator first, iterator last);
  //pre: first and last are valid iterators on this string, first<=last
  //  s0 = s1; s1.erase(first, last)
  //post: s1.size() = s0.size() + (last - first)
  //      for (iterator i = s1.begin(); i != first; i++)
  //                   s1[i] == s0[s0.begin()+(i-s1.begin())]
  //      for (iterator i = first; i != s1.end(); i++) 
  //                   s1[i] == s0[s0.begin()+(i-s1.begin())+xlen]

  string& erase(iterator position);
  //  equivalent to erase(position, position+1)

  

  // Replace part of a string with a part of another string.
  string& replace(size_type pos1, size_type n1,
		  const string& str);
  string& replace(size_type pos1, size_type n1,
		  const string& str, size_type pos2,
		  size_type n2);
  string& replace(size_type pos, size_type n1, const char* s,
		  size_type n2);
  string& replace(size_type pos, size_type n1, const char* s);
  string& replace(size_type pos, size_type n, char c);
  
  string& replace(iterator i1, iterator i2, const string& str);
  string& replace(iterator i1, iterator i2, const char* s, size_type n);
  string& replace(iterator i1, iterator i2, const char* s);
  string& replace(iterator i1, iterator i2, size_type n, char c);

#ifdef NESTED_TEMPLATES_SUPPORTED
  template<class InputIterator>
    string& replace(iterator i1, iterator i2,
			  InputIterator j1, InputIterator j2)
      {
	erase (i1, i2);
	insert (i1, j1, j2);
	return *this;
      }