数据结构 第4章 串.

Presentation on theme: "数据结构 第4章 串."— Presentation transcript:

1 数据结构 第4章 串

2 第4章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例

3 4.1 串类型的定义 In mathematical logic, more precisely in the theory of formal languages, and in computer science, a string is a sequence of symbols that are chosen from a set or alphabet In computer programming, a string is, essentially, a sequence of characters. A string is generally understood as a data type storing a sequence of data values, usually bytes, in which elements usually stand for characters according to a character encoding, which differentiates it from the more general array data type. In this context, the terms binary string and byte string are used to suggest strings in which the stored data does not (necessarily) represent text.

4 4.1 串类型的定义 串(string)是由零个或多个字符组成的有限序列 串中字符的数目称为串的长度
零个字符的串称为空串(null string)，其长度为0 串中任意连续的字符组成的子序列称为该串的子串 称字符在序列中的序号为该字符在串中的位置

5 4.1 串类型的定义 串的抽象数据类型的定义如下： ADT String {
数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n; n≥0 } 数据关系： R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n } ...

6 4.1 串类型的定义 基本操作： StrAssign (&T, chars) DestroyString(&S)
StrCopy (&T, S) StrLength(S) StrCompare (S, T) Concat (&T, S1, S2) StrEmpty (S)

7 4.1 串类型的定义 } ADT String SubString (&Sub, S, pos, len) ClearString (&S)
Index (S, T, pos) Replace (&S, T, V) StrInsert (&S, pos, T) StrDelete (&S, pos, len) } ADT String

8 4.1 串类型的定义 StrAssign (&T, chars) 初始条件：chars 是字符串常量。
操作结果：把 chars 赋为 T 的值。

9 4.1 串类型的定义 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。

10 4.1 串类型的定义 DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。

11 4.1 串类型的定义 StrEmpty (S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。
“”表示空串，空串的长度为零。

12 4.1 串类型的定义 StrCompare (S, T) 初始条件：串 S 和 T 存在。
操作结果： 若S > T，则返回值 > 0； 若S < T，则返回值 < 0； 若S = T，则返回值 = 0。 例如： StrCompare( “data”, “state”) < 0 StrCompare( “cat”, “case”) > 0

13 4.1 串类型的定义 StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。

14 4.1 串类型的定义 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。
例如： Concate( T, “man”, “kind”) 求得 T = “mankind”

15 4.1 串类型的定义 SubString (&Sub, S, pos, len)
初始条件：串 S 存在，1≤pos≤StrLength(S)，且0≤len≤StrLength(S)-pos+1。 操作结果：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。 例如： SubString( sub, "commander", 4, 3) 求得 sub = "man" ; SubString( sub, "commander" , 1, 9) 求得 sub = "commander" SubString( sub, "commander", 9, 1) 求得 sub = "r" SubString( sub, "commander", 4, 7) sub = ? SubString( sub, "beijing", 7, 2) sub = ? SubString("student", 5, 0) = "" 长度为 0 的子串为“合法”串

16 4.1 串类型的定义 Index (S, T, pos) 初始条件： 串S和T存在，T是非空串，1≤pos≤StrLength(S)。
操作结果： 若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置; 否则函数值为0。 “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。 假设 S = "abcaabcaaabc", T = "bca" Index(S, T, 1) = 2; Index(S, T, 3) = 6; Index(S, T, 8) = 0;

17 4.1 串类型的定义 例如：假设 S = "abcaabcaaabca", T = "bca"
Replace (&S, T, V) 初始条件： 串S, T和 V 均已存在，且 T 是非空串。 操作结果： 用V替换主串S中出现的所有与（模式串）T 相等的不重叠的子串。 例如：假设 S = "abcaabcaaabca", T = "bca" 若 V = "x", 则经置换后得到 S = "axaxaax" 若 V = "bc", 则经置换后得到 S = "abcabcaabc"

18 4.1 串类型的定义 StrInsert (&S, pos, T) 初始条件： 串S和T存在， 1≤pos≤StrLength(S)＋1。
例如： S = “chater ”，T = “rac ”， 则执行 StrInsert(S, 4, T)之后得到 S = "character "

19 4.1 串类型的定义 StrDelete (&S, pos, len)
初始条件： 串S存在 1≤pos≤StrLength(S)-len+1。 操作结果： 从串S中删除第pos个字符起长度为len的子串。

20 4.1 串类型的定义 ClearString (&S) 初始条件：串S存在。 操作结果：将S清为空串。

21 4.1 串类型的定义 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。 两个例子：
MFC 中的 CStringT stl 中的 string

22 4.1 串类型的定义 在上述抽象数据类型定义的操作中， 五种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现，
串赋值StrAssign 串比较StrCompare 求串长StrLength 串联接Concat 求子串SubString 五种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。

23 4.1 串类型的定义 i 例如，可利用串比较、求串长和求子串等操作实现定位函数Index( S, T, pos)。 算法的基本思想为：
StrCompare(SubString(S, i, StrLength(T)),T ) ? 0 i S 串 pos T 串 n-m+1 T 串

24 4.1 串类型的定义 int Index (String S, String T, int pos) {
// T为非空串。若主串S中第pos个字符之后存在与 T相等的子串 // 则返回第一个这样的子串在S中的 位置，否则返回0 if (pos > 0) { n = StrLength(S); m = StrLength(T); i = pos; while ( i <= n-m+1) { SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) ++i ; else return i ; } // while } // if return 0; // S中不存在与T相等的子串 } // Index

25 4.1 串类型的定义 又如串的置换函数 news 串 pos pos = i+m i pos S 串 sub n-pos+1 T 串 V 串

26 4.1 串类型的定义 void replace(String& S, String T, String V) {
n=StrLength(S); m=StrLength(T); pos = 1; StrAssign(news, ""); i=1; while ( pos < n-m+1 && i) { i=Index(S, T, pos); if (i!=0) { SubString(sub, S, pos, i-pos); Concat(news, news, sub, V); pos = i+m; } SubString(sub, S, pos, n-pos+1); Concat( S, news, sub );

27 4.1 串类型的定义 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别：
在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。

28 4.2 串的表示和实现 4.2.1 串的定长顺序存储表示 4.2.2 串的堆分配存储表示 4.2.3 串的块链存储表示

29 4.2.1 串的定长顺序存储表示 类似于线性表的顺序存储结构，可用一组地址连续的存储单元存储串值的字符序列。
例如C和C++语言中串不是预定义的数据类型，而是以字符数组来表示串。 如声明 char str[10]; 表明 str 是一个串变量。C语言中还规定了一个"串的结束标志 '\0'"（字符 '\0'称为空终结符），即数组中在该结束标志之前的字符是串变量的有效字符，但结束标志本身要占一个字符的空间，因此串变量 str 的值（字符序列）的实际长度可在这个定义范围内随意，但最大不能超过9。

30 4.2.1 串的定长顺序存储表示 在这种表示方法下，实现串操作的基本操作是“字符序列的复制”。 如下列算法为串的联接。
void Concat( char S1[ ], char S2[ ], char T[ ]){ 　　// 以T返回由S1和S2联接而成的新串 　　j=0; k=0; 　　while ( S1[j] != '\0') T[k++] = S1[j++]; 　　// 复制串 S1 　　j = 0; 　　while ( S2[j] != '\0') T[k++] = S2[j++]; //紧接着复制串S2 　　T[k] = '\0';　　　　　　　 // 置结果串T的结束标志 　} // Concat_Sq 实际实现时请注意 变量T存储区的准备

31 4.2.1 串的定长顺序存储表示 另外一种定长顺序存储表示： #define MAXSTRLEN 255
// 用户可在255以内定义最大串长 typedef unsigned char Sstring[MAXSTRLEN + 1]; // 0号单元存放串的长度

32 4.2.1 串的定长顺序存储表示 对应的联接操作： Status Concat(SString S1, SString S2, SString &T) { // 用T返回由S1和S2联接而成的新串。 // 若未截断, 则返回TRUE，否则FALSE。 if (S1[0]+S2[0] <= MAXSTRLEN) {// 未截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; }else if (S1[0] <MAXSTRSIZE) { // 截断 ……

33 4.2.1 串的定长顺序存储表示 对应的联接操作： …… T[1..S1[0]] = S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN－S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; }else { // 截断(仅取S1) T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; // T[0] == S1[0] == MAXSTRLEN } return uncut; } // Concat

34 4.2.2 串的堆分配存储表示 串的堆分配存储的特点是，程序中出现的所有串变量的存储空间都是在程序执行过程中动态分配而得的。堆分配存储结构的串定义如下： 　　typedef struct{ 　　　char *ch; 　　　int length; 　　} HString; 由于串仍然是以数组存储的字符序列表示，因此串的操作仍基于"字符序列的复制"实现。

35 4.2.2 串的堆分配存储表示 "插入"操作算法如下： bool StrInsert (Hstring& S, int pos, Hstring T){ // 若1≤pos≤StrLength(S)＋1,则改变串S,在串S的第pos个 // 字符之前插入串T，并返回TRUE,否则串S不变，并返回FALSE 　　if (pos < 1 || pos > S.length+1) 　　　return FALSE; 　　// 插入位置不合法 　　char S1[S.length] ; // S1 作为辅助串空间用于暂存 S.ch 　　if (T.length){ 　// T 非空，则为S重新分配空间并插入 T …… 　　} // if 　　return TRUE; 　} // StrInsert

36 4.2.2 串的堆分配存储表示 if (T.length){ // T 非空，则为S重新分配空间并插入 T p=S.ch; i=0;
　while (i < S.length) 　　S1[i++] = *(p+i); 　　　　 // 暂存串S 　S.ch = new char[S.length + T.length ]; // 为S重新分配串值存储空间 　for ( i=0, k=0; i<pos-1; i++) 　　S.ch[k++] = S1[i]; 　 　　 // 保留插入位置之前的子串 　j = 0; 　while (j<T.length) 　　S.ch[k++] = T.ch[j++]; 　　// 插入 T 　while ( i<S.length) 　　S.ch[k++] = S1[i++];　　　 // 复制插入位置之后的子串 　S.length+=T.length; 　　　 　// 置串 S 的长度 } // if

37 4.2.3 串的块链存储表示 和线性表的链式存储结构类似，也可用链表来存储串值。但由于串的结构的特殊性，即串的数据元素是一个字符，它只有8位二进制数，因此用链表存储串值时通常采用的办法是在一个结点中存放多个字符（如下图所示），因此称它为"块链"存储表示。图中的 "结点大小" CHUNKSIZE=4。

38 4.2.3 串的块链存储表示 const CHUNKSIZE = 80; // 可由用户定义的块（结点）大小
　　typedef struct Chunk {　　// 结点结构 　　　char ch[CUNKSIZE]; 　　　struct Chunk *next; 　　} Chunk; 　　typedef struct { 　　　　　// 串的链表结构 　　　Chunk *head, *tail; 　　// 串的头指针和尾指针 　　　int curlen; 　　　　　　　 // 串的当前长度 　　} LString;

39 4.3 串的模式匹配算法 在正文串中，查询有没有和一个"给定的串"相同的子串，返回这个子串的起始位置。这个操作即为串的定位操作，通常称为正文模式匹配。 若 S =“concatenation”， T =“cat”， 则称主串S中存在和模式串T相同的子串，起始位置为4，即 Index(S,T,1)=4 。

40 4.3.1 串的模式匹配的简单算法 将主串S中某个位置i起始的子串和模式串T相比较。 即从 j=0 起比较 S[i+j] 与 T[j]， 若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后探索( j逐步增1 )，直至T串中最后一个字符比较相等为止， 否则改从主串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。

41 4.3.1 串的模式匹配的简单算法 int Index_BF ( char S [ ], char T [ ], int pos ){
// 若串 S 中从第pos(1≤pos≤StrLength(S))个字符起存在和 // 串 T 相同的子串，则称匹配成功，返回第一个这样的子串 // 在串 S 中的位置，否则返回 0 　　i = pos-1; j = 0; 　　while ( S[i+j] != '\0'&& T[j] != '\0') 　　　if ( S[i+j] == T[j] ) j++; 　 　// 继续比较后一字符 　　　else { i ++; j = 0; } 　　　　　// 重新开始新的一轮匹配 　　if ( T[j] == '\0') return (i+1); 　// 匹配成功 　　else return 0; 　// 串S中(第pos个字符起)不存在和串T相同的子串 　} // Index_BF 容易看出，此算法的时间复杂度为O(m * n)，其中 m 和 n 分别为S串和T串的长度。

42 4.3.1 串的模式匹配的简单算法 int Index_BF1 ( char S [ ], char T [ ], int pos ) {
　// 若串 S 中从第pos(1≤pos≤StrLength(S))个字符起存在 　// 和串 T 相同的子串，则称匹配成功，返回第一个这样的子串 　// 在串 S 中的位置，否则返回 0 　　i = pos-1; j = 0; 　　while ( S[i] != '\0'&& T[j] != '\0') 　　　if ( S[i] == T[j] ) 　　　　{ i++; j ++; } 　　　　　　　// 继续比较后一字符 　　　else { i = i-j+1; j = 0; } 　　　// 重新开始新的一轮匹配 　　if ( T[j] == '\0') return (i-j); 　　　// 匹配成功 　　else return 0; 　 // 串S中(第pos个字符起)不存在和串T相同的子串 　} // Index_BF1

43 4.3.2 串的模式匹配的改进算法 ababcabcacbab abc a abcac
简单算法的匹配过程： 从主串ababcabcacbab 中找模式串 abcac ababcabcacbab abc a abcac

44 4.3.2 串的模式匹配的改进算法 ababcabcacbab abc abcac 改进：（KMP算法）
改进算法的匹配过程： 从主串 ababcabcacbab 中找模式串 abcac ababcabcacbab abc abcac 改进：（KMP算法） 当匹配过程中出现字符不等时，无需回溯主串指针，而是利用已经得到的部分匹配信息，将模式串向右滑动尽可能远的一段距离后，继续进行比较。

45 4.3.2 串的模式匹配的改进算法 前提是：‘p1p2…pk-1’ == ‘pj-k+1pj-k+2…pj-1’，pk!=pj
KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法 SS...SS...SSSS...SSSSS..SSSS. PP...PPP....PPPP..PPP.. PPP.....PPP..P.... 主串 i 匹配过程中的模式串 Si与Pj为首次出现的不匹配 j 1 j-k+1 k 1 主串不回溯，假设模式串可以右移到位置k处再开始比较Si=?=Pk 前提是：‘p1p2…pk-1’ == ‘pj-k+1pj-k+2…pj-1’，pk!=pj

46 4.3.2 串的模式匹配的改进算法 令 next( j )=k 为模式串中第j个与主串对应位置失配时，在模式中需要重新和主串中该字符进行比较的字符位置，它可以这样定义： next[j]==0意味着主串的下一个位置要和模式串的第一个位置开始进行比较

47 4.3.2 串的模式匹配的改进算法 int Index_KMP( SString S, SString T, int pos){
假设 next 的值已知，可以用来实现匹配算法 int Index_KMP( SString S, SString T, int pos){ i = pos; j=1; while( i<=S[0] && j<=T[0]){ if( j==0 || S[i]==T[j]) { i++; j++} else j = next[j]; } if( j>T[0]) return i-T[0]; else return 0;

48 4.3.2 串的模式匹配的改进算法 求 next 函数的过程是一个递推的过程： 首先由定义得 next[1]=0;
假设已知 next[j]=k( i.e. p1…pk-1 = pj-k+1…pj-1) 若：p[j] = p[k]，则显然有 next[j+1]=k+1； 若：p[j] !=p[k]，则令 k’ = next[k]，检查p[j]=?=p[k’] 若相等，则next[j+1] = next[k]+1 = k’+1 若不等，令k=k’，继续 j k’ k

49 4.3.2 串的模式匹配的改进算法 void get_next( SString T, int next[]) {
　　// 求模式串T的next函数值并存入数组 next。 　　i = 1; next[1] = 0; j = 0; 　　while ( i<T[0] ) { 　　 if ( j == 0 || T[i] == T[j]){ 　　　 ++i; ++j; next[i] = j; } 　　else j = next[j]; 　　} 　} // get_next

50 但是还有一种特殊情况需要考虑，　　例如： S = 'aaabaaabaaabaaabaaab' T = ‘aaaab’，next[]={0,1,2,3,4} aaaab

51 4.3.2 串的模式匹配的改进算法 S = 'aaabaaabaaabaaabaaab' T = 'aaaab'
　　此时因为T串的next函数值依次为0,1,2,3,4, 虽然匹配过程中指针 i 没有回溯，但对i=3、7、11和15重复进行了多次的'b'是否等于'a'的操作。换句话说，如果 next[j]=k，那么此时应该看一下T[j]是否等于 T[k]，如果不等，则 next[j]=k，否则next[j]就应该取值next[k]。例如上述T串的 next 函数值依次为0,0,0,0,4。由此改写求模式串的 next 函数值的算法如下。

52 4.3.2 串的模式匹配的改进算法 void get_nextval( SString T[], int nextval[]) {
　　// 求模式串T的next函数修正值并存入数组 nextval。 　　i=1; j = 0; next[1] = 0; 　　while ( i<T[0] ) { 　　　if (j == 0 || T[i] == T[j]) { 　　　　++i; ++j; 　　　　if (T[i]!=T[j]) nextval[i] = j; 　　　　else nextval[i] = nextval[j]; 　　　}else j = nextval[j]; 　　}　// while 　}　// get_nextval

53 4.3.2 串的模式匹配的改进算法 虽然简单的匹配算法的时间复杂度是O(n*m)，但一般情况下实际的执行时间近似于O(n+m)

54 KMP from wiki Worked example of the search algorithm 1 2
m: S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i:

55 KMP from wiki Worked example of the search algorithm 1 2
m: S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i:

56 KMP from wiki Worked example of the search algorithm 1 2
m: S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i:

57 KMP from wiki Worked example of the search algorithm 1 2
m: S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i:

58 KMP from wiki Worked example of the search algorithm 1 2
m: S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i:

59 KMP from wiki algorithm kmp_search: input:
an array of characters, S (the text to be searched) an array of characters, W (the word sought) output: an integer (the zero-based position in S at which W is found) define variables: an integer, m ← 0 (the beginning of the current match in S) an integer, i ← 0 (the position of the current character in W) an array of integers, T (the table, computed elsewhere) while m + i is less than the length of S, do: if W[i] = S[m + i], let i ← i + 1 if i equals the length of W, return m otherwise, let m ← m + i - T[i], if T[i] is greater than -1, let i ← T[i] else let i ← 0 (if we reach here, we have searched all of S unsuccessfully) return the length of S

60 KMP from wiki algorithm kmp_search: input:
an array of characters, S (the text to be searched) an array of characters, W (the word sought) output: an integer (the zero-based position in S at which W is found) define variables: an integer, m ← 0 (the beginning of the current match in S) an integer, i ← 0 (the position of the current character in W) an array of integers, T (the table, computed elsewhere)

61 KMP from wiki while m + i is less than the length of S, do:
if W[i] = S[m + i], let i ← i + 1 if i equals the length of W, return m otherwise, let m ← m + i - T[i], if T[i] is greater than -1, let i ← T[i] else let i ← 0 (if we reach here, we have searched all of S unsuccessfully) return the length of S

62 KMP from wiki algorithm kmp_table: input:
an array of characters, W (the word to be analyzed) an array of integers, T (the table to be filled) output: nothing (but during operation, it populates the table) define variables: an integer, pos ← 2 (the current position we are computing in T) an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring) (the first few values are fixed but different from what the algorithm might suggest) let T[0] ← -1, T[1] ← 0 while pos is less than the length of W, do: (first case: the substring continues) if W[pos - 1] = W[cnd], let T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1 (second case: it doesn't, but we can fall back) otherwise, if cnd > 0, let cnd ← T[cnd] (third case: we have run out of candidates. Note cnd = 0) otherwise, let T[pos] ← 0, pos ← pos + 1

63 KMP from wiki algorithm kmp_table: input:
an array of characters, W (the word to be analyzed) an array of integers, T (the table to be filled) output: nothing (but during operation, it populates the table) define variables: an integer, pos ← 2 (the current position we are computing in T) an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring) (the first few values are fixed but different from what the algorithm might suggest) let T[0] ← -1, T[1] ← 0

64 KMP from wiki while pos is less than the length of W, do:
(first case: the substring continues) if W[pos - 1] = W[cnd], let T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1 (second case: it doesn't, but we can fall back) otherwise, if cnd > 0, let cnd ← T[cnd] (third case: we have run out of candidates. Note cnd = 0) otherwise, let T[pos] ← 0, pos ← pos + 1

65 4.4 串操作应用举例 正文编辑程序是一个面向用户的系统服务程序，广泛用于源程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色等。正文编辑的实质是修改字符数据的形式或格式。无论是 Microsoft word 还是 WPS，其工作的基础原理都是正文编辑。虽然各种正文编辑程序的功能强弱不同，但其基本功能大致相同，一般都包括串的查找、插入、删除和修改等基本操作。

66 string in STL #include <string> String objects are a special type of container, specifically designed to operate with sequences of characters. Unlike traditional c-strings, which are mere sequences of characters in a memory array, C++ string objects belong to a class with many built-in features to operate with strings in a more intuitive way and with some additional useful features common to C++ containers. The string class is an instantiation of the basic_string class template, defined in <string> as: typedef basic_string<char> string; From:

67 string in STL A set of global functions provide some additional functionality for strings to interact either with other string objects or with objects of other types, mainly through the overloading of operators: operator+ Add strings (function) swap Swap contents of two strings (function) comparison operators String comparison operators (function, ==, !=, >, >=, <, <=)

68 string in STL The header also declares some functions that extend the functionality of streams (iostream library) to string objects: getline Get line from stream (function) operator<< Insert string into stream (function) operator>> Extract string from istream (function)

69 string in STL Member functions
(constructor) Construct string object (constructor member) operator= String assignment (public member function) Iterators: begin Return iterator to beginning (public member function) end Return iterator to end (public member function) rbegin Return reverse iterator to reverse beginning (public member function) rend Return reverse iterator to reverse end (public member function)

70 string in STL Capacity:
size Return length of string (public member function) length Return length of string (public member function) max_size Return maximum size of string (public member function) resize Resize string (public member function) capacity Return size of allocated storage (public member function) reserve Request a change in capacity (public member function) clear Clear string (public member function) empty Test if string is empty (public member function)

71 string in STL Element access:
operator[] Get character in string (public member function) at Get character in string (public member function)

72 string in STL Modifiers:
operator+= Append to string (public member function) append Append to string (public member function) push_back Append character to string (public member function) assign Assign content to string (public member function) insert Insert into string (public member function) erase Erase characters from string (public member function) replace Replace part of string (public member function) copy Copy sequence of characters from string (public member function) swap Swap contents with another string (public member function)

73 string in STL String operations:
c_str Get C string equivalent (public member function) data Get string data (public member function) get_allocator Get allocator (public member function) find Find content in string (public member function) rfind Find last occurrence of content in string (public member function) find_first_of Find character in string (public member function) find_last_of Find character in string from the end (public member function) find_first_not_of Find absence of character in string find_last_not_of Find absence of character in string from the end (public member function) substr Generate substring (public member function) compare Compare strings (public member function)