C/C++字符串处理(3):String ADT 字符串只是抽象数据类型

C/C++字符串处理(3):String ADT - 字符串只是抽象数据类型



许式伟
2008-3-26

概要

字符串是什么?我们认为,与其说它是一个类,不如说它只是一个ADT(抽象数据类型)。

目前C++中的字符串类

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

如何理解字符串只是ADT?

我们知道,基于值的容器主要有:

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);
};

当然,一个具体的字符串实现,会有其特殊支持的一些方法。这方面的详细资料,请参阅:

 
更多相关文章
  • 一. JS: https://github.com/hacke2/hacke2.github.io/issues/11 霸天 月刊   1.基础知识: http://www.zhihu.com/question/20979831 有哪些经常被误用的 HTML.JavaScript.CSS 的元素.方 ...
  • 什么是恶意软件? 本指南将术语"恶意软件"用作一个集合名词,来指代故意在计算机系统上执行恶意任务的病毒.蠕虫和特洛伊木马. 那么,计算机病毒或蠕虫的确切含义是什么?它们和特洛伊木马之间有哪些不同之处?防病毒应用程序是仅对蠕虫和特洛伊木马有效,还是仅对病毒有效? 所有这些问题都起源 ...
  • 关于百度定位 这是官方定位的解释:geolocation 地图插件配置 我在问答里面找到了这位童鞋的百度定位,地址变更提醒*** 不过,童鞋倒是给具体的示例啊,木有~~~~(>_<)~~~~ 官方的插件配置也看的懵懵懂懂,一塌糊涂 ok,自己搞,搞了大半天基本上弄清楚了,下面就总结一下自 ...
  • 由前一篇文章 http://www.cnblogs.com/darktime/p/3407980.html 我就配置了一个环境包,免安装的,只需要运行一个.bat的文件文件就算安装成功了 如果你需要用zend加密 配置zend guard loder 那么正好可以使用, 不用再管什么非线程安全 不用 ...
  • 以下是在iOS中最简单的界面切换示例.使用了多个Controller,并演示Controller之间在切换界面时的代码处理. 实现的应用界面: 首先,创建一个window-based application,即: 使用window-base application的目的是,尽量从最基本的情况下说明程 ...
  • uBuntu VirtualBox安装XP系统上网.共享文件以及U盘问题   uBuntu系统版本:12.10,其他版本方法雷同.   一.解决上网问题 在打开VirtualBox还没进入到XP时,设置NetWork: 网络类型:bridge(桥接) 驱动类型选择:Intel PRO/1000 T ...
一周排行
  • 输入子系统模型: 输入子系统由设备驱动层(input device driver),核心层(input core)和事件驱动层(event driver)三部份组成. 任何一次输入事件, 如鼠标移动, 按键按下, 都 ...
  • 1若a为int类型,且其值为3,则执行完表达式a+=a-=a*a后,a的 值是(). A.9 B.-12 C.6 D.-3 2 用下列语句定义a,b,c,然后执行b=a.c='b'+b,则b,c的值是(). long ...
  • Nexus 7预订页面 比特网(ChinaByte)7月15日消息 据外电消息报道,谷歌在上月的I/O大会上揭晓了第一款由自己主导设计的平板电脑Nexus 7,日前谷歌已经开始向预定用户发货.不过,至于在美国零售店全 ...
  •  前言 对于Android平台来说,系统内置了丰富的API来供开发人员操作SQLite,我们可以轻松的完成对数据的存取.下面就向大家介绍一下SQLite常用的操作方法.本篇文章主要用到SQLiteDatabase的一 ...
  • 第一章 入门介绍 关于本教程   在本教程中,我们将讨论如何使用一个 XML 解析器来:  处理一个 XML 文档  创建一个 XML 文档  操作一个 XML 文档  我们也将讨论一些有用而不为众人所知的 XML  ...
  • 我们经常给网站设计人员和开发人员分享有用的网站,工具和插件.今天的文章中,我们为大家带来了最近发布的 jQuery 插件,对于你即将到来的项目可能是真正有用的.这是10款最新流行的 jQuery 插件,值得你收藏. ...
  • 侠客风云传青城派邪教位置在哪里_侠客风云传青城派邪教位置介绍.一起跟随小编过来看看吧 <侠客风云传>青城派邪教位置 青城派邪教位置在哪:许多玩家不知道侠客风云传当中青城派邪教位置在哪,接下来小编就为大家带 ...
  •   Q2:机器上原来安装了oracle9i的客户端,并配置了两个远程连接,但是由于远程数据库没有准备测试环境,所以又在本地装了10g的数据库服务器,在将监听服务器配置成功,并且使用telnet工具可以监听到数据库的情 ...
  • assert的初步认识 assert宏指令是用来诊断程序是否有误的,函数原型如下 void assert(int expression)      那为什么我们要使用assert而不用printf呢?因为assert ...
  •     Lua中的函数是一阶类型值(first-class value),定义函数就象创建普通类型值一样(只不过函数类型值的数据主要是一条条指令而已),所以在函数体中仍然可以定义函数.假设函数f2定义在函数f1中,那 ...