C/C++字符串处理惩罚之String ADT – 字符串只是抽象数据范例
副标题#e#
提要
字符串是什么？我们认为，与其说它是一个类，不如说它只是一个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>是各类较量的算符，如==、!=、<、<=、>、 >=等等。
#p#副标题#e#
关于这些要领的更具体说明，请参阅：
TempString
String
可变字符串（字 符串操纵类）
#p#分页标题#e#
可变的字符串（字符串操纵类）包括以上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);
};
虽然，一个详细的字符串实现，会有其非凡支持的一些要领。这 方面的具体资料，请参阅：
StringBuilder：
http://cpp.winxgui.com/cn:stringbuilder
TextPool：
http://cpp.winxgui.com/cn:textpool
