概要
字符串是什么?我们认为,与其说它是一个类,不如说它只是一个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>是各种比较的算符,如==、!=、<、<=、>、>=等等。
关于这些方法的更详细说明,请参阅:
可变字符串(字符串操作类)
可变的字符串(字符串操作类)包含以上ConstString提供的所有方法,另外额外提供一些字符串修改相关的操作。一般来讲,可变的字符串至少满足以下规格:
template <class _E> concept MutableString : public ConstString<_E> { public: // 清空字符串 void clear(); public: // 赋值操作(这里进行了真正的复制) MutableString& assign(const TempString<_E> b); MutableString& assign(const value_type* pszVal, size_type cch); MutableString& assign(size_type count, value_type ch); template <class Iterator> MutableString& assign(Iterator first, Iterator last); MutableString& operator=(const TempString<_E> s); public: // 字符串连接 template <class Iterator> MutableString& append(Iterator first, Iterator last); MutableString& append(const TempString<_E> s); MutableString& append(const _E* s, size_type cch); MutableString& append(size_type cch, _E ch); MutableString& operator+=(const TempString<_E> s); public: // 插入 template <class Iterator> void insert(iterator it, Iterator first, Iterator last); void insert(iterator it, const TempString<_E> s); void insert(iterator it, const _E* s, size_type cch); void insert(iterator it, size_type cch, _E ch); public: // 替换 template <class Iterator> MutableString& replace( iterator first, iterator last, Iterator bfirst, Iterator blast); template <class _RandIterator> MutableString& replace( iterator first, iterator last, size_type count, _E ch); MutableString& replace( iterator first, iterator last, const _E* s, size_type cch); MutableString& replace( iterator first, iterator last, const TempString<_E> s); };
当然,一个具体的字符串实现,会有其特殊支持的一些方法。这方面的详细资料,请参阅: