当前位置导航:炫浪网>>网络学院>>编程开发>>C++教程>>C++基础入门教程

C/C++字符串处理(3):String ADT

    String ADT - 字符串只是抽象数据类型

    概要

    字符串是什么?我们认为,与其说它是一个类,不如说它只是一个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>是各种比较的算符,如==、!=、<、<=、>、>=等等。 

 

共2页 首页 上一页 1 2 下一页 尾页 跳转到
相关内容
赞助商链接