[数据结构与算法]常见C++函数

容器

顺序容器类型:

容器操作

| 类型别名                              |                                                           |
| :------------------------------------ | --------------------------------------------------------- |
| iterator                              | 此容器类型的迭代器类型                                    |
| const_iterator                        | 可以读取元素，但不能修改元素的迭代器类型                  |
| size_type                             | 无符号整数类型，足够保存此种容器类型最大可能容器的大小    |
| difference_type                       | 带符号整数类型，足够保存两个迭代器之间的距离              |
| value_type                            | 元素类型                                                  |
| reference                             | 元素的左值类型;与value_type&含义相同                      |
| const_reference                       | 元素的const左值类型（即，const value_type&)               |
| 构造函数                              |                                                           |
| C c;                                  | 默认构造函数，构造空容器(array，参见第301页)              |
| c c1(c2);                             | 构造c2的铂贝c1                                            |
| C c(b,e);                             | 构造c，将迭代器b和e指定的范围内的元素拷贝到c(array不支持) |
| C c{a,b,c...};                        | 列表初始化c                                               |
| 赋值与swap                            |                                                           |
| c1 = c2                               | 将c1中的元素替换为c2中元素                                |
| c1= {a,b,c...}                        | 将c1中的元素替换为列表中元素（不适用于array)              |
| a.swap(b)                             | 交换a和b的元素                                            |
| swap(a,b)                             | 与a.swap(b)等价                                           |
| 大小                                  |                                                           |
| c.size()                              | c中元素的数目（不支持forward_list)                        |
| c.max_size()                          | c可保存的最大元素数目                                     |
| c.empty()                             | 若c中存储了元素，返回false，否则返回true                  |
| 添加/删除元素（不适用于array)         |                                                           |
| 注:在不同容器中，这些操作的接口都不同 |                                                           |
| c.insert (args)                       | 将args中的元素拷贝进c                                     |
| c.emplace (inits)                     | 使用inits构造c中的一个元素                                |
| c.erase (args)                        | 删除args指定的元素                                        |
| c.clear ()                            | 删除c中的所有元素，返回void                               |
| 关系运算符                            |                                                           |
| ==，!=                                | 所有容器都支持相等（不等）运算符                          |
| <，<=,>,>=                            | 关系运算符（无序关联容器不支持)                           |
| 获取迭代器                            |                                                           |
| c.begin () , c.end ()                 | 返回指向c的首元素和尾元素之后位置的迭代器                 |
| c.cbegin (), c.cend ()                | 返回const_iterator                                        |

容器定义和初始化

C c;         // 默认构造函数。如果c是一个array,则c中元素按默认方式初始化;否则c为空
C c1(c2)     // c1初始化为 c2的拷贝。c1和c2必须是相同类型（即，它们必须是
C c1=c2      // 相同的容器类型,且保存的是相同的元素类型;对于array类型，两者还必须具有相同大小)
C c{a, b,c...} // c初始化为初始化列表中元素的拷贝。列表中元素的类型必须与C的
C c={a,b,c...) // 元素类型相容。对于array类型，列表中元素数目必须等于或小于array的大小，任何遗漏的元素都进行值初始化（参见3.3.1节，第88页)
C c(b, e)      // c初始化为迭代器b和e指定范围中的元素的拷贝。范围中元素的类型必须与c的元素类型相容（array不适用)
只有顺序容器（不包括array）的构造函数才能接受大小参数
C seq(n)       // seq包含n个元素，这些元素进行了值初始化;此构造函数是explicit的（参见7.5.4节，第265页)。(string不适用)
c seq(n,t)    // seq包含n个初始化为值t的元素

容器赋值运算

c1=c2             // 将c1中的元素替换为c2中元素的拷贝。c1和c2必须具有相同的类型
c={a,b,c. . . )   // 将c1中元素替换为初始化列表中元素的拷贝（array不适用)
swap(c1,c2)       // 交换c1和 c2中的元素。c1和 c2必须具有相同的类型。swap通常
c1.swap(c2)       // 比从c2向c1拷贝元素快得多
assign 操作不适用于关联容器和array
seq.assign (b,e) // 将seq中的元素替换为迭代器b和 e所表示的范围中的元素。迭代器b和e不能指向seg中的元素
seq.assign (il)  // 将seq中的元素替换为初始化列表il中的元素
seq.assign (n, t) // 将seq中的元素替换为n个值为t的元素

// 注意：赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而swap操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效(容器类型为array和string的情况除外)。

向顺序容器添加元素的操作

这些操作会改变容器的大小;array不支持这些操作。
forward_list   // 有自己专有版本的insert和emplace;参见9.3.4节（第312页 )。
forward_list   // 不支持push_back和emplace_back。
vector和string  // 不支持push_front和emplace_front。
c.push_back (t) // 在c的尾部创建一个值为t或由args创建的元素。返回void
c.emplace_back (args) 
c.push_front (t)  // 在c的头部创建一个值为t或由args创建的元素。返回void
c.emplace_front (args)
c.insert(p,t)       // 在迭代器p指向的元素之前创建一个值为t或由 args创建的元
c.emplace(p , args) // 素。返回指向新添加的元素的迭代器
c.insert (p,n,t)    // 在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器;若n为0，则返回p
c.insert(p,b,e)     // 将迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素。返回指向新添加的第一个元素的迭代器;若范围为空，则返回p
c.insert (p,il)     // il是一个花括号包围的元素值列表。将这些给定值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器;若列表为空，则返回p

注意： 向一个vector.string或 deque插入元素会使所有指向容器的迭代器、引用和指针失效。

在顺序容器中访问元素的操作

at和下标操作只适用于string. vector. deque和array
back不适用于forward_list。
c.back ()    // 返回c中尾元素的引用。若c为空，函数行为未定义
c.front ()   // 返回c中首元素的引用。若c为空，函数行为未定义
c [n]        // 返回c中下标为n的元素的引用,n是一个无符号整数。若n>=c.size ( ) ,则函数行为未定义
c.at (n)     // 返回下标为n的元素的引用。如果下标越界，则抛出一out_of_range异常
注意：对一个空容器调用 front和back,就像使用一个越界的下标一样，是一种严重的程序设计错误。

顺序容器的删除操作

这些操作会改变容器的大小，所以不适用于array。
forward_list    // 有特殊版本的erase，参见9.3.4节（第312页)。
forward_list    // 不支持pop_back; vector和string不支持pop_front。
c.pop_back ()   // 删除c中尾元素。若c为空，则函数行为未定义。函数返回void
c.pop_front ()  // 删除c中首元素。若c为空，则函数行为未定义。函数返回void
c.erase (p)     // 删除迭代器p所指定的元素，返回一个指向被删元素之后元素的迭代器，若p指向尾元素，则返回尾后（off-the-end）迭代器。若p是尾后迭代器，则函数行为未定义
c.erase (b, e)  // 删除迭代器b和e所指定范围内的元素。返回一个指向最后一个被删元素之后元素的迭代器，若e本身就是尾后迭代器，则函数也返回尾后迭代器
c.clear ( )     // 删除c中的所有元素。返回void
注意：删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string 中删除点之后位置的迭代器、引用和指针都会失效。

顺序容器大小操作

resize不适用于array
c.resize (n)    // 调整c的大小为n个元素。若n<c.size()，则多出的元素被丢
弃。若必须添加新元素，对新元素进行值初始化
C. resize(n, t)  // 调整c的大小为n个元素。任何新添加的元素都初始化为值t
注意：如果resize缩小容器，则指向被删除元素的迭代器、引用和指针都会失
效;对vector、string或deque进行resize可能导致迭代器、指针
和引用失效。

修改string的操作

s.insert (pos,args)    // 在pos之前插入args指定的字符。pos 可以是-一个下标或-一个迭代器。接受下标的版本返回一个指向s的引用:接受迭代器的版本返回指向第一一个插入字符的迭代器
s.erase (pos,Ien)      // 删除从位置pos开始的len个字符。如果len被省略，则删除从pos开始直至s末尾的所有字符。返回一个指向s的引用
s.assign (args)        // 将s中的字符替换为args指定的字符。返回一个指向s的引用
s.append (args)        // 将args追加到s。返回一个指向s的引用
s.replace (range,args) // 删除s中范围range内的字符，替换为args指定的字符。range
					   // 或者是一个下标和一个长度，或者是- -对指向s的迭代器。返回
					   // 一个指向s的引用
args可以是下列形式之一; append 和assign可以使用所有形式。
str不能与s相同，迭代器b和e不能指向s。
str             // 字符串str
str, pos, len   // str中从pos开始最多len个字
cp, len         // 从cp指向的字符数组的前(最多) len个字符
cp              // cp指向的以空字符结尾的字符数组
n,c             // n个字符c
b,e .           // 迭代器b和e指定的范围内的字符
初始化列表       花括号包围的，以 逗号分隔的字符列表

string

初始化string对象的方式

string s1       	 // 默认初始化，s1是一个空串
string s2(s1)   	 // s2是s1的副本
string s2 = s1       // 等价于s2(s1)，s2是s1的副本
string s3 ("value")  // s3是字面值"value"的副本，除了字面值最后的那个空字符外string s3 = "value"  // 等价于s3("value")，s3是字面值"value"的副本
string s4(n, 'c')    // 把s4初始化为由连续n个字符c组成的串
n、len2和pos2都是无符号值
string s (cp,n)      // s是cp指向的数组中前n个字符的拷贝。此数组至少应该
包含n个字符
string S (s2, pos2)  // s是string s2从下标pos2开始的字符的拷贝。若
					 // pos2>s2.size()，构造函数的行为未定义
string s (s2, pos2, len2)   // s是string s2从下标pos2开始len2个字符的拷贝。.
							// 若pos2>s2.size(),构造函数的行为未定义。不管len2
							// 的值是多少，构造函数至多拷贝s2.size()-pos2个字符

子字符串操作

s.substr (PoS, n) // 返回一个string,包含s中从pos开始的n个字符的拷贝。pos的默
认值为0。n的默认值为s.size ()-pos，即拷贝从pos开始的所有字符

string的操作

os<<s           // 将s写到输出流os当中，返回os
is>>s           // 从is中读取字符串赋给s，字符串以空白分隔，返回is
getline(is, s)  // 从is中读取一行赋给s，返回is
s.empty ()      // s为空返回true，否则返回false
s.size ()       // 返回s中字符的个数
s[n]            // 返回s中第n个字符的引用，位置n从0计起
s1+s2           // 返回s1和 s2连接后的结果
sl=s2           // 用s2的副本代替s1中原来的字符
s1==s2          // 如果s1和 s2中所含的字符完全一样，则它们相等;string对象的相
s1!=s2          // 等性判断对字母的大小写敏感
<,<=，>,>=      // 利用字符在字典中的顺序进行比较，且对字母的大小写敏感

cctype头文件中的函数

isalnum(c)     // 当c是字母或数字时为真
isalpha(c)     // 当c是字母时为真
iscntrl(c)     // 当c是控制字符时为真
isdigit(c)     // 当c是数字时为真
isgraph(c)     // 当c不是空格但可打印时为真
islower(c)     // 当c是小写字母时为真
isprint (c)    // 当c是可打印字符时为真（即c是空格或c具有可视形式)
ispunct (c)    // 当c是标点符号时为真（即c不是控制字符、数字、字母、可打印空白中的一种)
isspace(c)     // 当c是空白时为真（即c是空格、横向制表符、纵向制表符、回车符、换行符、进纸符中的一种)
isupper(c)     // 当c是大写字母时为真
isxdigit(c)    // 当c是十六进制数字时为真
tolower (c)    // 如果c是大写字母，输出对应的小写字母;否则原样输出c
toupper (c)    // 如果c是小写字母，输出对应的大写字母;否则原样输出c

vector

初始化 vector对象的方法

vector<T> v1               // v1是一个空vector，它潜在的元素是T类型的，执行默认初始化
vector<T> v2(v1)           // v2中包含有v1所有元素的副本
vector<T> v2=v1            // 等价于v2(v1)，v2中包含有v1所有元素的副本
vector<T> v3(n,val)        // v3包含了n个重复的元素，每个元素的值都是val
vector<T> v4(n)            // v4包含了n个重复地执行了值初始化的对象
vector<T> v5{a,b,c...}     // v5包含了初始值个数的元素，每个元素被赋予相应的初始值
vector<T> v5 = { a,b,c.. . } // 等价于v5{a, b,c.. .}

vector支持的操作

v .empty ()       // 如果v不含有任何元素，返回真:否则返回假
v.size ()         // 返回v中元素的个数
v.push_back (t)   // 向v的尾端添加一个值为t的元素
v [n]             // 返回v中第n个位置上元素的引用
v1 = v2           // 用v2中元素的拷贝替换v1中的元素
vl = {a,b,C... }  // 用列表中元素的拷贝替换v1中的元素
v1 == v2          // v1和v2相等当且仅当它们的元素数量相同且对应位置的元素值都相同
vl != v2  
<,<=，>,>=        // 顾名思义，以字典顺序进行比较

迭代器

标准容器迭代器的运算符

*iter          // 返回迭代器iter所指元素的引用
iter->mem      // 解引用iter并获取该元素的名为mem的成员，等价于(*iter).mem
++iter         // 令iter指示容器中的下一个元素
--iter         // 令 iter指示容器中的上一个元素
iter1 == iter2 // 判断两个迭代器是否相等（不相等)，如果两个迭代器指示的是同一个元
iter1 != iter2 // 素或者它们是同一个容器的尾后迭代器，则相等;反之，不相等

vector和 string迭代器支持的运算

iter +n       // 迭代器加上一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比向前移动了若干个元素。结果迭代器或者指示容器内的一个元素，或者指示容器尾元素的下一位置
iter - n      // 迭代器减去一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比向后移动了若干个元素。结果迭代器或者指示容器内的一个元素，或者指示容器尾元素的下一位置
iter1 += n    // 迭代器加法的复合赋值语句，将iter1 加n的结果赋给iter1
iter1 -= n    // 迭代器减法的复合赋值语句，将iter1减n的结果赋给iter1
iter1 - iter2 // 两个迭代器相减的结果是它们之间的距离，也就是说，将运算符右侧的迭代器向前移动差值个元素后将得到左侧的迭代器。参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置
>、>=、<、<=  // 迭代器的关系运算符，如果某迭代器指向的容器位置在另一个迭代器所指位置之前，则说前者小于后者。参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置