STL常用标准库容器
C++ STL中最基本以及最常用的类或容器无非就是以下几个:
目录
string
vector
deque
list
forward_list
queue
priority_queue
stack
四种关联容器
set
multiset
map
multimap
四种无关联容器
string
对比在C语言中一般怎么使用字符串的
char* s1 = "Hello JackYu!"; //创建指针指向字符串常量,既然是常量字符串,这段字符串我们是不能修改的//想要创建 可以修改的字符串,我们可以使用数组分配空间char s2[20] = "Hello JackYu!";//或者这样char s3[] = "Hello JackYu!";//当然我们也可以手动的动态分配内存char* s4 = (char*)malloc(20);gets(s4);
C++ 标准库中的string表示可变长的字符串,它在头文件string里面。
#include <string>using std::string;
直接初始化和拷贝初始化
string s1;//初始化字符串,空字符串string s2 = s1; //拷贝初始化,深拷贝字符串string s3 = "I am b"; //直接初始化,s3存了字符串string s4(10, 'a'); //s4存的字符串是aaaaaaaaaastring s5(s4); //拷贝初始化,深拷贝字符串string s6("I am d"); //直接初始化string s7 = string(6, 'c'); //拷贝初始化,cccccc
//// main.cpp// LearnEffective C++//// Created by 于磊 on /6/24.// Copyright © 于磊. All rights reserved.//#include <iostream>using std::string;using std::cout;using std::endl;using std::cin;int main(int argc, const char * argv[]) {string s1;//初始化字符串,空字符串string s2 = s1; //拷贝初始化,深拷贝字符串string s3 = "Hellor World"; //直接初始化,s3存了字符串string s4(10, 'a'); //s4存的字符串是aaaaaaaaaastring s5(s4); //拷贝初始化,深拷贝字符串string s6("Scott"); //直接初始化string s7 = string(6, 'c'); //拷贝初始化,cccccc//string的各种操作string s8 = s3 + s6;//将两个字符串合并成一个s3 = s6;//用一个字符串来替代另一个字符串的对用元素cin >> s1;cout << s1 << endl;cout << s2 << endl;cout << s3 << endl;cout << s4 << endl;cout << s5 << endl;cout << s6 << endl;cout << s7 << endl;cout << s8 << endl;cout << "s7 size = " << s7.size() << endl; //字符串长度,不包括结束符cout << (s2.empty() ? "This is empty string" : "This string is not empty") << endl;;return 0;}
string的IO操作
使用cin读入字符串时,遇到空白就停止读取
"Hello World"
那么我们得到的字符串将是"Hello",前面的空白没了,后面的world也读不出来。
如果我们想把整个hello world读进来怎么办?那就这样做
cin>>s1>>s2;
hello存在s1里,world存在s2里了。
有时我们想把一个句子存下来,又不想像上面那样创建多个string来存储单词,怎么办?
那就是用getline来获取一整行内容。
string str;getline(cin, str);cout << str << endl;
当把string对象和字符面值及字符串面值混在一条语句中使用时,必须确保+的两侧的运算对象至少有一个是string
string s1 = s2 + ", "; //正确,此处其实包含了隐式的类型转换,string对象+字符串常量转成了string对象string s3 = "s " + ", "; //错误,const char *中没有此算术运算符string s4 = "hello" + ", " + s1; //错误,同上string s5 = s1 + "hello " + ", "; //改一下顺序,s1放前头,正确了,注意理解=号右边的运算顺序
遍历以及读写string中的每一个元素
for(auto &iter:s6){cout<<iter<<endl;iter = '1';}
在C++里,有个新奇的东西叫做迭代器iterator,我们可以使用它来访问容器元素。
string str1("some string");if (str1.begin() != str1.end()) {auto it = str1.begin();*it = toupper(*it);}cout << str1 << endl;string str2("some string");//ylfor (string::iterator it = str2.begin(); it != str2.end(); it++) {*it = toupper(*it);}cout << str2 << endl;
迭代器类型也可以定义为const_iterator类型,表现形式是只能读元素不能写元素
处理string对象中的字符,在cctype头文件中定义了一部分标准库函数处理这部分工作
string还有一些很好用的算法,比如找子串
string sq("aaaaa bbb cc s");cout << sq.find("aa", 0) << endl; //返回的是子串位置。yl第二个参数是查找的起始位置,如果找不到,就返回string::nposif (sq.find("aa1", 0) == string::npos){cout << "找不到该子串!" << endl;}
string中包含的专有的操作(相对于vector来说)
1. string的添加与替换
在string中,增加了append()与 replace()函数str.append(args)// 在尾部添加一个字符或一个字符str.replace(pos, args)// 在尾部添加一个字符或一个字符 ,它的重载函数很多,共16个。
2. string的访问子字符串:
str.substr(_pos, n)//该函数可以获得原字符串中的部分字符, 从pos开始的n个字符,当_pos超过范围时,会抛出out_of_range的异常yl。
3. str的搜索操作:
str.find(args)//查找args 第一次出现的位置str.rfind(args)//查找args最后一次出现的位置str.find_first_of(args)//搜索的是字符, 第一个是args里的字符的位置ystr.find_last_of(args)// 搜索的是字符, 最后一个是args里的字符的位置lstr.find_first_not_of()// 搜索的是字符,第一个不是args里的字符的位置str.find_last_not_of()// 搜索的是字符, 最后一个不是args里的字符的位置
4. str的大小操作:
str.length()// 该函数与str.size()函数完成一样,只是名字不同而已罢了。只所以这样搞的原因,可能开发人员感觉length更适合字串符,size更适合容器吧。
c字符串的转换函数
1. 由数值转换为字符串:
to_string(val):
2. 由字符串转换为数值:(要转换的string的第一个非空白符必须是数值中可能出现的字符,处理直到不可能转换为数值的字符为止,以下内容来自:c++primer)
stoi(str, pos, base) // 字符串转换为整型,其中str表示字符串, pos用于表示第一个非数值字符的下标(意思就是我给函数传入一个地址,它会对它进行赋第一个非数值字符的位置), base表数值的基数,默认为10,即10进制数。yuleistol(str, pos, base)// 转换为longstoul(str, pos, base)// 转换为 unsigned longstoll(str, pos, base)// 转换为 long longstoull(str, pos, base)// 转换为unsigned long longstof(str, pos)// 转换为floatstod(str, pos,)// 转换为doublestold(str, pos,)// 转换为long double
vector
vector是数组的一种类表示,它提供了自动内存管理功能,可以动态地改变vector对象的长度,并随着元素的添加和删除而增大缩小,
它提供了对元素的随机访问,在尾部添加和删除元素的时间是固定的,但在头部或中间插入和删除元素的复杂度为线性时间。除序列外,vector还是可反转容器
vector存在于头文件vector中
#include <vector>
初始化
如果vector的元素类型是int,默认初始化为0;如果vector元素类型为string,则默认初始化为空字符串。
vector<int> v1;vector<father> v2;vector<string> v3;vector<vector<int> >; //注意空格。这里相当于二维数组int a[n][n]嵌套vector;vector<int> v5 = { 1,2,3,4,5 }; //C11列表初始化vector<string> v6 = { "hi","C++","Primer","learning","hard yl" };vector<int> v7(5, -1); //初始化为-1,-1,-1,-1,-1。第一个参数是数目,第二个参数是要初始化的值vector<string> v8(3, "hi");vector<int> v9(10); //默认初始化为0vector<string> v10(4); //默认初始化为空字符串
向vector写入数据(注意写入位置对时间复杂度产生的影响)
for (int i = 0; i < 5; i++){vec.push_back(i);}
vector其他成员函数操作
访问和操作vector中的每个元素(注意vector是有序容器,频繁增删将导致严重的性能问题)
for (int i = 0; i < vec.size(); i++){cout << vec[i] << endl;vec[i] = 100; //不建议这样写数据cout << vec[i] << endl;}
注意:只能对已存在的元素进行赋值或者修改操作,如果是要加入新元素,务必使用push_back。push_back的作用有两个:告诉编译器为新元素开辟空间、将新元素存入新空间里。
比如下面的代码是错误的,但是编译器不会报错,就像是数组越界。
vector<int> vec;vec[0] = 1; //错误!
当然我们也可以选择使用迭代器来访问元素
vector<string> v6 = { "hi","C++","Primer","learning","hard" };for (vector<string>::iterator iter = v6.begin(); iter != v6.end(); iter++){cout << *iter << endl;//下面两种方法都行,对象和引用的区别cout << (*iter).empty() << endl;cout << iter->empty() << endl; }//反向迭代器for (vector<string>::reverse_iterator iter = v6.rbegin(); iter != v6.rend(); iter++){cout << *iter << endl;}
vector最常用的增删操作
//// main.cpp// LearnEffective C++//// Created by 于磊 on /6/24.// Copyright © 于磊. All rights reserved.//#include <iostream>#include <vector>#include <string>using namespace std;template <typename T> void showvector(vector<T> v) {for (typename vector<T>::iterator it = v.begin(); it != v.end(); it++) {cout << *it;}cout << endl;}int main(int argc, const char *argv[]) {vector<string> v6 = {"hi", "C++", "Primer", "learning", "hard"};v6.resize(3); //重新调整vector容量大小showvector(v6);vector<int> v5 = {1, 2, 3, 4, 5}; //列表初始化,注意使用的是花括号cout << v5.front() << endl; //访问第一个元素cout << v5.back() << endl; //访问最后一个元素showvector(v5);v5.pop_back(); //删除最后一个元素showvector(v5);v5.push_back(6); //加入一个元素并把它放在最后showvector(v5);v5.insert(v5.begin() + 1, 9); //在第二个位置插入新元素showvector(v5);v5.erase(v5.begin() + 3); //删除第四个元素showvector(v5);v5.insert(v5.begin() + 1, 7,8); //连续插入7个8showvector(v5);v5.clear(); //清除所有内容showvector(v5);return 0;}
注意:
虽然vertor对象可以动态增长,但是也或有一点副作用:已知的一个限制就是不能再范围for循环中向vector对象添加元素。另外一个限制就是任何一种可能改变vector对象容量的操作,不如push_back,都会使该迭代器失效。另外,为容器申请内存空间的时候会为其额外的多申请一些空间。C++ Primer中专门有说明
总而言之就是:但凡使用了迭代器的循环体,都不要向迭代器所属的容器添加元素!
?:C++中push_back和insert两个有什么区别?
顾名思义push_back把元素插入容器末尾,insert把元素插入任何你指定的位置。不过push_back速度一般比insert快。如果能用push_back尽量先用push_back。
vecotr常使用的操作
1. 属性操作
v1.size()//v1内已经存放的元素的数目v1.capacity()// v1现有的在存储容量(不再一次进行扩张内存空间的前提下)v1.empty()// 判断v1是否为空v1.max_size() // 返回vector可以存放的最大元素个数,一般这个数很大,因为vector可以不断调整容量大小。v1.shrink_to_fit()// 该函数会把v1的capacity()的大小压缩到size()大小,即释放多余的内存空间。
2. 访问操作:访问操作都会返回引用,通过它,我们可以修改vector中的值。
v1[n]// 通过下标进行访问vector中的元素的引用 (下标一定要存在 ,否则未定义,软件直接崩了)v1.at(n)// 与上面类似,返回下标为n的元素的引用,不同的是,如果下标不存在,它会抛出out_of_range的异常。它是安全的,建议使用它。v1.front()// 返回vector中头部的元素的引用(使用时,一定要进行非空判断)v1.back()// 返回vector中尾部的元素 引用(使用时,一定要进行非空判断)
3. 添加操作:
v1.push_back(a)//在迭代器的尾部添加一个元素v1.push_front(a)// vector不支持这个操作v1.insert(iter, a)// 将元素a 插入到迭代器指定的位置的前面,返回新插入元素的迭代器(在c++11标准之前的版本,返回void)v1.insert(iter, iter1, iter2) //把迭代器[iterator1, iterator2]对应的元素插入到迭代器iterator之前的位置,返回新插入的第一个元素的迭代器(在c++11标准之前的版本, 返回空)。
在c++11标准中,引入了emplac_front()、 emplace()、emplace_back(), 它们分别与push_front()、insert()、 push_back()相对应,用法与完成的动作作完全相同,但是实现不一样。push_front()、insert()各push_back()是对元素使用copy操作来完成的,而emplac_front()、 emplace()和emplace_back()是对元素使用构造来完成的,后者的效率更高,避免了不必要的操作。因此,在以后更后推荐使用它们。
4. 删除操作:
v1.erase(iterator)// 删除人人迭代器指定的元素,返回被删除元素之后的元素的迭代器。(效率很低,最好别用)v1.pop_front()//vector不支持这个操作v1.pop_back()//删除vector尾部的元素 , 返回void类型 (使用前,一定要记得非空判断)v1.clear() //清空所有元素
5. 替换操作:
v1.assign({初始化列表})// 它相当于赋值操作,v1.assign(n, T)// 此操作与初始化时的操作类似,用个n T类型的元素对v1进行赋值v1.assign(iter1, iter2)// 使用迭代器[iter1, iter2]区间内的元素进行赋值(该迭代器别指向自身就可以),另外,只要迭代器指的元素类型相同即可(存放元素的容器不同,例如:可以用list容器内的值对vector容器进行assign操作,而用 "=" 绝对做不到的。v1.swap(v2)// 交换v1与v2中的元素。
swap操作速度很快,因为它是通过改变v1与v2两个容器内的数据结构(可能是类似指针之类的与v1和v2的绑定)完成的,不会对容器内的每一个元素进行交换。 这样做,不仅速度快,并且指向原容器的迭代器、引用以及指针等仍然有效,因为原始的数据没有变。在c++ primer 中建议大家使用非成员版本的swap()函数,它在范型编程中很重要。
deque
deque模版类 double-ended queue(双端队列) ,支持随机访问,从deque对象的开始位置插入和删除元素的时间是固定的,而不像vector是线性时间。
所以多数操作是发生在序列的起始和结尾处,就应该考虑deque。为实现在deque两端执行插入和删除操作的时间为固定的这一目的,deque对象的设计比vector对象更为复杂。
因此,尽管两者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作,但是vector容器执行这些操作时速度还要快些。
list
list(双向链表),除了第一个和最后一个元素外,每个元素都与前后的元素相连接,这意味着可以双向遍历链表,list和vector之间关键区别在于,list在链表中任一位置进行插入和删除的时间都是固定的(vector模版提供了除结尾处外的线性时间的插入和删除,在结尾处,它提供了固定时间的插入和删除)。因此,vector强调的是通过随机访问快速访问,而list强调的是元素的快速插入和删除。list也可以反转容器,list不支持数组表示法和随机访问。因为它是用双向链表实现的,所以,它的一大特性就是它的迭代器永远不会变为无效(除非这段空间不存在了),即无论增加、删除操作,都不会破坏迭代器。list是一个双向链表,而单链表对应的容器则是foward_list。
list的头文件
#include <list>
遍历和访问list
//// main.cpp// set//// Created by yulei on /8/10.// Copyright © 于磊. All rights reserved.//#include <iostream>#include <list>#include <string>using namespace std;template <typename T> void showlist(list<T> v) {for (typename list<T>::iterator it = v.begin(); it != v.end(); it++) {cout <<" "<< *it;}cout << endl;}int main(int argc, const char *argv[]) {list<int> lst1{1, 2, 3, 4, 5, 6, 7};showlist(lst1);list<double> l2;list<char> lst3(10);list<int> lst2(5, 10); //将元素都初始化为10showlist(lst2);return 0;}
值得注意的是,list容器不能调用algorithm下的sort函数进行排序,因为sort函数要求容器必须可以随机存储,而list做不到。所以,list自己做了一个自己用的排序函数,用法如下:
list<int> lst1{1, 4, 343, 5, 666, 2, 3, 4, 5, 6, 7};showlist(lst1);lst1.sort();showlist(lst1);
forward_list
forward_list,它实现了单链表,在这种链表中,每个节点都只链接到下一个节点,而没有链接到前一个节点。因此forward_list只需要正向迭代器,而不需要双向迭代器。因此,不同于vector和list,forward_list是不可反转的容器。相比list,forward_list更简单,更紧凑,但功能也更少。
queue
queue,queue模版的限制比deque更多,它不仅不允许随机访问队列元素,甚至不允许遍历队列。它把使用限制在定义队列的基本操作上,可以将元素添加到队尾,从队首删除元素,查看队首和队尾的值,检查元素数目和测试队列是否为空。
priority_queue
priority_queue,和queue的区别在于,最大的元素被移到队首。内部区别在于,默认的底层类是vector。可以修改用于确定哪个元素放到队首的比较方式。方法是提供一个构造函数。
stack
7.stack,提供了典型的栈接口,stack模版的限制比vector更多。它不仅不允许随机访问栈元素,甚至不允许遍历栈,它把使用限制在定义栈的基本操作上,即可以将压入推到栈顶,从栈顶弹出元素,查看栈顶的值,检查元素数目和测试栈是否为空.于queue想死,如果要使用栈中的值,必须首先使用top()来检索这个值,然后使用pop将它中栈中删除。
四种关联容器
set
其值类型与键相同,键是唯一的。这意味着集合中不会有多个相同的键。set跟vector差不多,它跟vector的唯一区别就是,set里面的元素是有序的且唯一的,只要你往set里添加元素,它就会自动排序,而且,如果你添加的元素set里面本来就存在,那么这次添加操作就不执行。
头文件
#include <set>
//// main.cpp// set//// Created by yulei on /8/10.// Copyright © 于磊. All rights reserved.//#include <iostream>#include <string>#include <set>using namespace std;template <typename T> void showset(set<T> v) {for (typename set<T>::iterator it = v.begin(); it != v.end(); it++) {cout << *it << " ";}cout << endl;}int main(int argc, const char *argv[]) {set<int> s1{91, 8, 341, 3, 3, 4, 3, 3, 4, 5, 66, 6, 1, 5, 5, 6, 7, 7}; //自动排序,从小到大,剔除相同项showset(s1);set<string> s2{"hello", "C++", "Primer", "5th"}; //字典序排序showset(s2);s1.insert(9); //有这个值了,do nothingshowset(s1);s2.insert("aaa"); //没有这个字符串,添加并且排序showset(s2);return 0;}
multiset
可以有多个相同的键。
map
map运用了哈希表地址映射的思想,也就是key-value的思想,来实现的,底层和set一样都是用红黑树实现。内部元素按照key哈希排序。首先给出map最好用也最最常用的用法例子,就是用字符串作为key去查询操作对应的value。
注意:在查找一个不存在的key的时候,map会自动生成这个key,这里涉及到如何安全和挑选符合自己业务逻辑的关联容器格外重要
头文件
#include <map>
//// main.cpp// set//// Created by yulei on /8/10.// Copyright © 于磊. All rights reserved.//#include <iostream>#include <string>#include <map>using namespace std;void showmap(map<string, int> v){for (map<string, int>::iterator it = v.begin(); it != v.end(); it++){cout << it->first << " " << it->second << endl; //注意用法,不是用*it来访问了。first表示的是key,second存的是value}cout << endl;}int main(int argc, const char *argv[]) {map<string, int> m1; ///<里的第一个参数表示key的类型,第二个参数表示value的类型m1["year"] = ;m1["month"] = 8;m1["day"] = 10;string s("month");m1[s] = 7;cout << m1["year"] << endl;cout << m1["month"] << endl;cout << m1["day"] << endl; //不存在这个key,就显示0,并在map中创建没有的keym1.erase("minute");//通过关键字来删除showmap(m1);m1.insert(pair<string, int>("second", 52)); //也可以通过insert函数来实现增加元素showmap(m1);m1.clear(); //清空全部return 0;}
如果想看看某个存不存在某个key,可以用count来判断
if (m1.count("year")) {cout << "year is in m1!" << endl;} else {cout << "year do not exist!" << endl;}
用迭代器来访问元素
for (map<string, int>::iterator it = m1.begin(); it != m1.end(); it++){cout << it->first<<" "<<it->second << endl; //注意用法,不是用*it来访问了。first表示的是key,second存的是value.也就是在map中存储的又是另外一种数据结构(pair)}
用find来访问元素
map<string, int> m_map = {{"key1", 1}, {"key2", 2}, {"key3", 3}, {"key4", 4}};auto itr = m_map.find("key2");while (itr == m_map.end()) {(itr->second)++;}
一些其他操作
vector<int> ivec = {2, 1, 3, 2, 2, 2, 3, 4, 6, 7, 8, 9, 2};set<int> set2;map<string, int> m_map = {{"key1", 1}, {"key2", 2}, {"key3", 3}, {"key4", 4}};auto itr= m_map.find("key2");while (itr == m_map.end()) {(itr->second)++;}m_map.insert(pair<string, int>("key5", 100));for (auto &x : m_map) {if (x.first == "key3")cout << "1 " << x.first << ":" << x.second << endl;elsecout << "2 " << x.first << ":" << x.second << endl;}pair<string, int> authors = {"key6", 111};pair<string, int> p("key7", 2222);pair<string, int> p2("key8", 122);m_map.insert({p2, authors, p});m_map.insert(map<string, int>::value_type("key9", 1111));auto ret = m_map.insert({"key9", 1111});pair<map<string, int>::iterator, bool> ret2; //非泛型if (!ret.second)++ret.first->second;auto map_it = m_map.cbegin();while (map_it != m_map.cend()) {cout << map_it->first << " key " << map_it->second << " value" << endl;++map_it;}set2.insert(ivec.cbegin(), ivec.cend());set2.insert({11, 22, 33, 44});set2.insert(set<int>::value_type(11111));auto set_it = set2.cbegin();while (set_it != set2.end()) {cout << *set_it << endl;++set_it;}
multimap
multimap也是可以反转的,经过排序的关联容器,但键和值的类型不同,且同一个键可能与多个值相关联。
四种无关联容器
无序关联容器是对容器概念的另一种改进。与关联容器一样,无序关联容器也将键与值关联起来,并使用键来查找值,但底层的差别在于,关联容器是基于树结构的,而无序关联容器是基于数据结构哈希表的
1.unordered_set
2.unordered_multiset
3.unordered_map
4.unordered_mutimap