C++常用标准模板库(未完待续)

C++常用标准模板库(未完待续)

1. vector(动态数组)

? 1）vector的定义：

? 一维：vector name，typename可以是任何类型；

? 二维：vector>，C++11后 “>>”之间不需要空格了。

? 2）vector的访问：

  • 和数组一样使用下标访问;
  • 使用迭代器：迭代器的定义 vector::iterator it。类似于指针，可以通过 it 来访问vector里的元素。可以通过 it=name.begin() 取得 vector 首元素的地址。name[i] 和 (it+i) 是等价的。

注意：在常用的 STL 容器中，只有在 vector 和 string 中，才允许使用 name.begin() + 数字 的这种写法。

? 3) vector 常用函数：

  • push_back(x)，在 vector 后面添加一个元素 x，时间复杂度 O(1)；
  • pop_back(),在 vector 删除 vector 尾元素，时间复杂度 O(1)；
  • size()，用来获得 vector 中元素个数，时间复杂度 O(1)；
  • clear()，清空 vector 中所有元素，时间复杂度 O(N) , N 是 vector 中元素的个数；
  • insert(),用来向 vector 的任意迭代器 it 处插入一个元素 x ，it 之后的元素顺次后移一位 ,时间复杂度 O(N),格式：insert(it,x)；
  • erase()
    删除单个元素 erase(it);
    删除区间内的元素 erase(st,ed)，删除 [st,ed) 内的元素。

vector的常见用途：
（1） 存储数据：便于输出需要输出的数；
（2） 用邻接表存储图。

2. set

set 翻译为集合，是一个内部自动有序且不含重复元素的容器。默认是升序。底层采用红黑树实现。

? 1）set的定义：

  • set s；
  • 降序的定义方式为： set> s。
  • typename 可以是任意类型包括STL容器。
  • set 数组的定义方式为，set s[size].s[0]…s[size-1] 都是 set 类型。迭代器的定义方式set::iterator it

2) set 容器内元素的访问：

? set 只能通过迭代器(iterator)访问。

? 3) set常用函数:

  • insert(x) 可将x插入set容器中，并且自动递增排序和去重，时间复杂度O(logN),其中N是set中元素的数量。

  • find(x) 返回set中对应值为x的迭代器，时间复杂度O(logN),N为set内元素的个数。

  • erase() ，erase有两种用法：删除单个元素，删除一个区间内的所有元素。

  • 删除单个元素有两种方式，erase(it)删除该迭代器对应的元素，时间复杂度O(1),erase(x)删除该元素,时间复杂度O(logN)

    • 删除一个区间的元素，erase(st,ed),删除区间[st,ed)内的元素，时间复杂度O(ed-st)

  • size() ,用来获得set内元素的个数，时间复杂度O(1)

  • clear() ,用来清空set中所有元素，复杂度O(N),其中N为set内元素的个数。

  • count(x) ,返回set中x的数量

set 的常见用途：

set 最主要的作用是自动去重并且升序排序，因此碰到需要去重但不方便开数组的时候，可以尝试用 set 解决。

注意： set 中的元素是唯一的，如果需要处理不唯一的情况可以使用 multiset。C++11 中还增加了 unordered_ set, 以散列代替 set 内部的红黑树，unordered_set 可以处理需要去重但是不需要排序的情况，速度比 set 快得多。Multiset 和unordered_set 的定义和常用函数和 set 类似。

3. string

C++ STL 中加入 string 类型，对字符串常用需求功能进行了封装，使得操作起来更方便，且不易出错。如果要使用 string,需要添加 string 头文件，即 #include[HTML_REMOVED], 注意 string.h 和 string 是不一样的头文件。除此之外要想使用string，还要在头文件下面加上一句 “using namespace std”，这样就可以在代码中使用 string 了。

string的定义：

定义方式与基本数据类型相同，只需要在 string 后面跟上变量名称即可。
eg. string str;

如果需要初始化，可以直接给 string 类型的变量赋值，string str = “hello”。

String中内容的访问：

  • 1) 通过下标访问，可以直接像字符数组那样去访问 string
string str = "hello" ;
    for(int i=0;i

输出结果:hello

如果用 string 读入和输出字符串一般只能用 cin 和 cout，使用 printf 输出也是可以的，但是要先将 string 装换为字符数组进行输出

string str ;
cin >> str ;
cout << str << endl ;
printf("%s\n",str.c_str()) ;
return 0 ;

输入：hello
输出：hello
hello

  • 2) 通过迭代器访问，string 的访问一般采用第一种方式，但是 string 有很多函数要求以迭代器为参数。

    string 迭代器的定义方式为 string::iterator it，可以使用 *it 来访问 string 中的每一位。String 迭代器的使用方法与其他容器的迭代器的使用方法类似，string 和 vector 一样，支持直接对迭代器进行加减某个数字。
    示例：

string str = "hello" ;
string::iterator it  ;
for(it = str.begin();it!=str.end();it++){
    cout << *it ;
}
it = str.begin() ;
cout << endl ;
    cout << *(it+1) << "<--->" << str[1] << endl ;

结果： hello
e<—>e

string常用函数：

string 提供的函数有很多，这里仅介绍常用的 string 函数

    1. operator += 拼接
      这是 string 的加法，可以将两个 string 直接拼接起来。
string str1 = "hello" ;
string str2 = " world" ;
cout << str1 + str2 << endl ;

结果：hello world

    1. compare operator 比较
      两个 string 类型可以直接使用：==, !=, <, <=, >, >= 比较大小，比较规则是字典序。
string str1 = "aa" ;
string str2 = "ab" ;
string str3 = "abc" ;
if(str1 != str2){
	cout << "not same" << endl ;
}else{
    cout << "same" << endl ;
} 
if(str3>str2){
    cout << "str3>str2" << endl ;
}

结果：not same
str3>str2

    1. length()/size() 取得大小
      length() 返回 string 的长度，即 string 存放的字符数，时间复杂度 O(1)。size() 和 length() 基本相同。
string str1 = "hello" ;
cout << str1.size() << ' ' << str1.length() << endl ;

结果：5 5

    1. insert（）插入（原字符串不会被覆盖）
      insert() 函数有很多种写法，这里列出几个常用的写法，时间复杂度度 O(N)。
      insert(pos,string)，在 pos 号位置插入 string。
      insert(it,it1,it2)，it 为原字符串欲插入的位置，it2 和 it3 为待插字符串的首尾迭代器，用来表示串 [it1,it2) 将被插在 it 的位置上。
string str1 = "hello world" ;
string str2 = "Maric" ;
str1.insert(str1.begin()+5,str2.begin(),str2.end()) ;
cout << str1 << endl ;
str2.insert(5,"hello") ;
cout << str2 << endl ;

结果：helloMaric world
Marichello

    1. erase() 删除
      erase() 有两种用法，删除单个元素，上出一个区间内所有元素。时间复杂度 O(N)。

    a. erase(it) 用于删除单个元素，it 为需要删除的元素的迭代器。
    b. 删除一个区间的元素有两种方法：
    第一种是 erase(st, ed), st，ed 为 string 迭代器，表示删除区间 [st,ed) 之间的元素。
    第二种是 erase(pos, len)，其中 pos 为需要删除的起始位置，len 为删除的字符个数。

string str1 = "hello world" ;
str1.erase(str1.begin()) ;
cout << str1 << endl ;
str1.erase(str1.begin()+5,str1.end()) ;
cout << str1 << endl ;
str1.erase(1,2) ;
cout << str1 << endl ;

结果：ello world
ello
eo

    1. clear() 清空
      clear() 函数用来清空 string 中的数据，时间复杂度 O(1)。
string str1 = "hello world" ;
cout << str1.length() << endl ;
str1.clear() ;
cout << str1.size() << endl ;

结果：11
0

    1. substr() 截取子串
      substr(pos,len) 返回的是以 pos 位开始长度为 len 的子串，时间复杂度 O(len)。
string str1 = "hello world" ;
cout << str1.substr(6,5) << endl ;

结果：world

    1. string::npos
      npos 是一个常数，用来表示不存在的位置，类型一般是 std::container_type::size_type 许多容器都提供这个东西。取值由具体实现决定，一般是 -1，但是由于是 unsigned_int 类型，也可以认为是 unsigned_int 类型的最大值，这样做，就不会存在移植的问题了。
      不建议将find的返回值作为是否匹配的依据。最好使用示例的使用方式。npos主要是和find()函数搭配使用，用以作为find()函数失配时的返回值，举个例子具体解释一下：
if (a.find(b) != string::npos) {
    cout << "Yes!" << endl;
} else {
    cout << "No!" << endl;
}
    1. find() 查找
      str.find(str1), 当 str1 是 str 的子串时，返回其在 str 中第一次出现的位置。如果 str1 不是 str 的子串，那么返回string::npos
      str.find(str1,pos), 从 str 的 pos 号位开始匹配 str1,返回值与上面的相同，时间复杂度为 O(nm),其中 n 和 m 分别为 str 和 str1 的长度。
string str1 = "hello world" ;
string str2 = "world" ;
if(str1.find(str2) != string::npos){
    cout << str1.find(str2) << endl ;
    cout << str1.find(str2,3) << endl ;
}else{
    cout << "match failure" << endl ;
}

结果：6
6

小结： find 函数的返回值是整数，假如字符串存在包含关系，其返回值必定不等于 npos，但如果字符串不存在包含关系，那么返回值就一定是 npos。

    1. replace()
      str.replace(pos,len,str1), 把 str 从 pos 号位开始，长度为 len 的子串替换为 str1。
      str.replace(it1,it2,str1) 把 str 的迭代器 [it1,it2) 替换为 str1
string str1 = "hello world" ;
string str2 = "kangkang" ;
cout << str1.replace(6,5,str2) << endl ;
cout << str1.replace(str1.begin()+6,str1.end(),str2) << endl ;

结果：hello kangkang
hello kangkang

4. map

map 翻译成映射，map 可以将任何基本类型（包括 STL 容器）映射到任何基本类。（包括 STL 容器）。

如要使用 map，需要添加 map 头文件，并在头文件底下加上 “using namespace std”, 这样就可以在代码中使用 map 了。

4.1. map 的定义:

map[HTML_REMOVED] mp; map 和其他 STL 容器的定义上有点不同，因为 map 需要确定映射前类型（键 key）和映射后类型（值 value）, map 存储的数据类型是一对 K-V 结构的数据。如果 map 是字符串到整型的映射，必须使用 string 而不能使用 char 数组。

map 的访问：

map 一般有两种访问方式，通过“下标”访问或者通过迭代器访问。

（1） 通过“下标”访问，和普通数组的访问方式一样。比如，定义了一个 map[HTML_REMOVED] mp; 的 map，可以使用mp[“hello”] = 8 的方式向 map 中添加数据，用 mp[“hello”] 访问 map 中键为 “hello” 的值。map 中的键是唯一的，可以观察下面代码的输出。

unordered_map um ;
um["hello"] = 8 ;
um["hello"] = 100 ;
cout << um["hello"] << endl ;

输出：100

（2） 通过迭代器访问，与其他 STL 迭代器有点不同，由于 map 的数据类型是 K-V 结构，因此迭代器包含了这两方面的数据。map 迭代器的定义方式为 map[HTML_REMOVED]::iterator it ; 可以通过 it->first 来访问键，it->second 来访问值。观察下面的代码:

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
for(map::iterator it=mp.begin();it!=mp.end();it++){
	cout << it->first << ' ' << it->second << endl ;
}

输出结果：aloha 666
good 777
hello 100

观察输出结果，很有意思的是 map 按照键值从小到大排序了，如果是字符串，则按照字典序排序。map 是采用红黑树来实现的。

map的常用函数：

（1） find（key），返回键为 key 的映射的迭代器，时间复杂度为 O(logN)，N 为 map 中映射的个数。

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
auto it = mp.find("good") ;
cout << it->first << ' ' << it->second << endl ;

输出结果：good 777

（2） erase(), erase() 有两种用法：删除单个元素和删除一个区间内的元素。
a． 删除单个元素，删除单个元素也有两种方法
mp.erase(it)，it 为需要删除的元素的迭代器，时间复杂度O(1)。

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase(mp.find("good"));
for(auto ele : mp){
	cout << ele.first << ' ' << ele.second << endl ;
}

输出结果：aloha 666
hello 100

mp.erase(key)，key 为欲删除的映射的键。时间复杂度 O(logN)。N 为 map 中元素的个数。

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase("good");
for(auto ele : mp){
	cout << ele.first << ' ' << ele.second << endl ;
}

输出结果：aloha 666
hello 100

b. 删除一个区间的元素，这里只能用迭代器删除，erase(st,ed), 表示删除 [st,ed) 区间内的元素。

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase(mp.find("good"),mp.find("hello"));
for(auto ele : mp){
	cout << ele.first << ' ' << ele.second << endl ;
}

输出结果：aloha 666
hello 100

注意，st 的迭代器位置必须在 ed 之前。

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase(mp.find("good"),mp.find("good"));
for(auto ele : mp){
	cout << ele.first << ' ' << ele.second << endl ;
}

输出结果：aloha 666
good 777
hello 100

其实是什么也没有删除。

（3） size(), 用来获得 map 中映射的对数，时间复杂度 O(1)。

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
cout << mp.size() << endl ;

输出结果：3

（4） clear()，用来清空 map 中所有元素，复杂度为 O(N)，其中 N 为 map 中元素的个数。

map mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.clear() ;
cout << mp.size() << endl ;

输出结果：0

map的常见用途：

（1） 需要建立字符（或字符串）与整数之间映射的题目，使用 map 可以减少代码量。
（2） 判断大整数或者其他类型数据是否存在的题目，可以把 map 当成 bool 数组用。
（3） 字符串和字符串之间的映射。

补充： map 和键和值都是唯一的，而如果一个键需要对应多个值，就只能使用 multimap 。另外，C++11 标准中还增加了unordered_map, 以散列代替 map 内部的红黑树实现，使其可以用来处理映射而不需要按 key 排序的需求，速度比 map 快很多。

5. queue

6. priority_queue

7. stack

8. pair

9. algorithm

作者：gulangyuzzz
链接：https://www.acwing.com/blog/content/844/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

AlgorithmCCPP

相关

linux - hash algorithm

深度聚类算法研究综述(A Survey of Deep Clustering Algorithms)

C语言折半算法/二分查找算法/数字扫雷算法（binary search algorithm、digital mineswee

最小生成树核心Algorithm(C++)

计算机图形学 - 实验： Bresenham’s Line Algorithm

Apache Flink Machine Learning algorithm-library

Apache Flink Machine Learning algorithm-library

Apache Flink Machine Learning algorithm-library

Apache Flink Machine Learning algorithm-library

神奇的 algorithm

【Algorithm】Union Find

标签