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

MrFuWen 2020-02-22

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

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

1. vector(动态数组)

? 1)vector的定义:

? 一维:vector name,typename可以是任何类型;

? 二维:vector<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<typename,greater> 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<str.size();i++){
        printf("%c",str[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

  • 2) 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

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

结果:5 5

  • 4) 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

  • 5) 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

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

结果:11
0

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

结果:world

  • 8) 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;
}
  • 9) 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。

  • 10) 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<string,int> 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<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
for(map<string,int>::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<string,int> 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<string,int> 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<string,int> 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<string,int> 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<string,int> 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<string,int> 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<string,int> 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
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关推荐

whtqsq / 0评论 2019-06-21