C++字符串处理之String ADT - 字符串只是抽象数据类型

C/C++字符串处理之String ADT - 字符串只是抽象数据类型2013-02-05 csdn 许式伟概要

字符串是什么？我们认为，与其说它是一个类，不如说它只是一个ADT（抽象数据类型）。

目前C++中的字符串类

目前广泛采用的C++字符串类有二：std::string（basic_string，由STL提供）、CString（由MFC或者WTL提供）。它们的实现非常类似，都是带引用计数的、基于线性数据结构的字符串。不过SGI STL的Rope打破了这个规矩。它采用了一种基于树结构的组织方式来实现字符串。

如何理解字符串只是ADT？

我们知道，基于值的容器主要有：

动态数组（std::vector）

双向链表（std::list）

单向链表（std::slist，非STL标准）

双向队列（std::deque）

std::deque其实是分段连续的、介于数组和链表之间的数据结构。这里不进行详细介绍，关于 std::deque的介绍，请参见这里。

这些容器都可以成为实现字符串的基础容器。例如，我们的StringBuilder基于 std::vector实现；我们的TextPool基于std::deque实现。

也许你有疑问：是的，基于std::vector或者std::deque可以理解，但是，这世上有基于链表的字符串吗？然而世界之大，确实无奇不有。据“不完全”统计，多数函数式语言（如Erlang）确实采用单向链表实现字符串。

无论采用什么具体的实现，最后我们都会尽力去提供一个一致的字符串操作界面。所以，从这个意义上说，字符串只是一个ADT（抽象数据类型），它可以有多种实现，使用者按照具体的需求选择一种最合适自己用况的字符串类。

字符串操作界面

在StdExt库中，字符串这个ADT的规格定义如下：

常字符串

不可变的字符串类，应该至少包含以下方法：

template <class _E>
concept  ConstString
{
public:
  typename value_type;
  typename size_type,  difference_type;
  typename reference, const_reference;
  typename iterator,  const_iterator;

public:
  iterator begin（） const;
  iterator end（） const;

  reverse_iterator rbegin（） const;
  reverse_iterator rend（） const;

   const_reference at（size_type i） const;
  const_reference operator[]（size_type i） const;

  size_type size（） const;
  bool empty（） const;

  basic_string<_E> stl_str（）  const; // 转为STL string

public:
  // 取字符串的字串

  template <class  AllocT>
  BasicString<_E> substr（
    AllocT& alloc, size_type from = 0,  size_type count = （size_type）-1） const;

public:
  // 在字符串中查找子串（正向查找）。

  iterator find（const TempString<_E> pattern, iterator from = begin（）） const;
   iterator find（const _E* pattern, size_type len, iterator from = begin（）） const;

public:
  // 在字符串中查找子串（反向查找）。

  iterator rfind（const TempString<_E> pattern,  iterator from = begin（）） const;
  iterator rfind（const _E* pattern, size_type len, iterator  from = begin（）） const;

public:
  // 查找某个集合中的字符在字符串中第一次出现的位置（正向查 找）。

  iterator find_first_of（
    const TempString<_E> pattern, iterator  from = begin（）） const;

  iterator find_first_of（
    const _E* pattern, size_type  len, iterator from = begin（）） const;

public:
  // 查找某个集合中的字符在字符串中第一次出 现的位置（反向查找）。

  reverse_iterator find_last_of（
    const TempString<_E>  pattern, reverse_iterator from = rbegin（）） const;

  reverse_iterator find_last_of（
     const _E* pattern, size_type len, reverse_iterator from = rbegin（）） const;

public:
  // 在字符串中查找不在集合中出现的第一个字符的位置（正向查找）。

  iterator find_first_not_of （
    const TempString<_E> pattern, iterator from = begin（）） const;

   iterator find_first_not_of（
    const _E* pattern, size_type len, iterator from = begin（））  const;

public:
  // 在字符串中查找不在集合中出现的第一个字符的位置（反向查找）。

  reverse_iterator find_last_not_of（
    const TempString<_E> pattern, reverse_iterator  from = rbegin（）） const;

  reverse_iterator find_last_not_of（
    const _E* pattern,  size_type len, reverse_iterator from = rbegin（）） const;

public:
  // 比较两个字符串。 

  int compare（const TempString<_E> b） const;
  int compare（const _E* b,  size_type blen） const;
  int compare（size_type from, size_type count, const TempString<_E>  b） const;
  int compare（size_type from, size_type count, const _E* b, size_type blen）  const;

public:
  // 比较两个字符串（传入单字符的比较函数）。

  template  <class _Compr>
  int compare_by（const TempString<_E> b, _Compr cmp） const;

  template <class _Compr>
  int compare_by（const _E* b, size_type blen, _Compr cmp）  const;

public:
  // 比较两个字符串（忽略大小写）。

  int icompare（const  TempString<_E> b） const;
  int icompare（const _E* b, size_type blen） const;

public:
  // 判断是否包含指定的串。

  bool contains（const TempString<_E> b）  const;
  bool contains（const _E* b, size_type blen） const;

public:
  template  <class LogT>
  void trace（LogT& log） const; // 在log中显示该字符串。

public:
  // 交换两个字符串

  void swap（ConstString& b）;
}

template  <class _E> // 比较两个字符串
bool operator<cmp>（const ConstString<_E>& a,  const ConstString<_E>& b）;
// 这里<cmp>是各种比较的算符，如==、！=、<、<=、>、 >=等等。