商务网站建设论文答辩ppt,网站数据分析报告,网店推广联盟,培训网站设计此文作为学习stl的笔记#xff0c;许多普及、概念性的知识点将不再罗列#xff08;如stl的发展、背景等#xff09; 便于读者作为复习等方法了解。 0.STL简介#xff08;笔记向#xff09; STL不是祖师爷本贾尼实现的#xff0c;是在惠普实验室中实现的。其作为一个数据结… 此文作为学习stl的笔记许多普及、概念性的知识点将不再罗列如stl的发展、背景等 便于读者作为复习等方法了解。 0.STL简介笔记向 STL不是祖师爷本贾尼实现的是在惠普实验室中实现的。其作为一个数据结构与算法的库主要是数据结构现在有很多商业公司开发的目的有的开源有的收费目前使用最多的是也是我们使用的继承自HP版本的SGI版本。 学习STL有三重境界能用、明理、能扩展如自己扩展B树等
此篇我们介绍string的运用。 目录
0.STL简介笔记向
1.string
2.string的构造函数constructor重点是abcde会被当作const char*
3.string的运算符重载[ ]两种重载带const和不带const
4.string的遍历
5.string在VS编译器下的大小了解
6.将string按照字典序排序
7.string的插入和修改
7.1 push_back 和 append
7.2更常用的添加方法运算符重载
7.3 assign函数
7.4 重点 insert 与 erase
7.5 replace替换函数 注意两个迭代器传参时的左闭右开
8.小试牛刀
9.capacity大类
编辑 9.1 max_size(了解)
9.2clear
9.3扩容
9.4 resize和reserve ★★
9.5 shrink_to_fit
9.6 at
9.7 c_str
10.find
11. string相关的部分外部函数
12.编码表UNICODE 1.string string也就是常说的数据结构“串”。string出现的比stl早所以有一些功能较冗杂 C 语言中字符串是以 \0 结尾的一些字符的集合为了操作方便 C 标准库中提供了一些 str 系列的库函数 但是这些库函数与字符串是分离开的不太符合OOP面向对象编程 的思想而且底层空间需要用户自己管理稍不留神可 能还会越界访问。 比如 strcpy和strcat你需要自己管理空间大小、是否有/0、操作的方法。。。。 非常麻烦。 许多都需要使用string存储如身份证号码数据很大用int存储很不划算并且还有可能带X string也叫basic_string并且被默认为管理char类型数据的容器。 还可以管理wchar wchar是一种 双字节 字符 在大多数情况下我们可以认为string就是一个char类型的数组、顺序表。 string - C Reference (cplusplus.com)
string一共一百二十个左右的成员函数其实很多函数是冗余的。 2.string的构造函数constructor重点是abcde会被当作const char*
我们要学会通过文献来使用函数 掌握默认构造、拷贝构造、带参构造、其他的会查网站看明白即可。 第一个是默认构造第二个是我们最常用的常量区赋值 string sabcdefg; 如果我们定义一个空字符串 string str1; 那么str1中是包含了\0的 默认构造出的s2中间不是乱码而是什么都没有。 s可以直接被cout输出也可以通过cin直接获得内容。甚至可以使用中文。 第三种初始化substring是按照使用者主观定制长度拷贝第一个参数是数组名字符串名字第二个是开始拷贝的位置包括该位置,数据结构喜欢左闭右开第三个是拷贝的长度。长度的默认参数是npos 成员变量npos: 注意npos是无符号整形size_t所以npos其实是四十二亿左右。当然一个string没有那么长。 其中str is too short的意思是相对于我传的参数lenstr可以被拷贝的内容太短了 不传参或者写npos就相当于直接拷贝到末尾都属于str is too short
同样的学会通过英文来了解含义 常量字符串被认为是const char*,调用的是第五个构造
这种直接常量字符串接数字表示前三个字符如果是一个string接数字表示从第数字个位置开始省略了一个要打印个数的参数。 如下单参数构造函数的隐式类型转换const char* 转化成string中间会生成一个临时变量string构造再加上一个拷贝构造有时候直接优化成一次构造 因此对于引用 string s4 abcdw;//涉及隐式类型转换abcdw被当作char* 3.string的运算符重载[ ]两种重载带const和不带const
size和length在此处是相同的作用length是一开始被设计的,size是在之后stl设计时从整体角度考虑的便于和其他stl统一。
size和length都不会计算\0 使用较少的调用方法 这样我们的自定义类型就能像数组一样使用。 作为自定义、尤其是一些需要深拷贝的类型我们可以传引用返回来减少拷贝次数以提升效率那么此处的运算符重载[ ]为什么也要使用传引用返回拷贝几个字节很费劲吗
我们先只看第一排的重载
!!! 传引用返回的第二大作用得以体现可修改容器中的返回值 string底层开的空间在堆上。 并且由于string的底层的越界检查很多都是使用assert所以错误都能检查出来。 那么。面对不希望被修改的字符串如下图的被const修饰的常量字符串string底层开的空间在堆上 我们再观察之前的声明[ ]有两种运算符重载相互构成函数重载第一种的参数不含const也就是刚刚提到的展示引用返回作用的重载还有一种是参数带const的那么我们对返回值也进行const的修饰使常量字符串不得被修改。 再加上匹配机制优先匹配最合适的为了让不能被修改的就一直不被修改可以修改的就可以修改所以我们需要实现两个重载。只使用带const的重载也可以调用非常量字符串但是这样的话非常量字符串也不能修改 不太方便。但是大部分函数用const修饰是只有好处没有坏处的这样的观念我们在前文提到过 所以到底提供几个const需要在实战中按照实际需要来确定。 4.string的遍历 根据刚才的size功能和运算符重载我们可以通过循环实现数组的遍历。 for (size_t i 0; i s4.size(); i) {cout s4[i] ;
}
C还有一种方法遍历迭代器 iterator。 首先iterator是定义在类域中的必须在string域中使用。 string::iterator it1 s4.begin();
while (it1 ! s4.end()) {cout *it1 ;it1;
} 那什么又是begin和end呢 最重要的概念所有容器的begin和end都满足左闭右开 begin返回首字符“指针”end返回最后一个有效字符的下一个的“地址” 迭代器就可以看做是类似指针的东西。但是其本质不一定是指针。 我们可以利用typeid来看一下其类型非常奇怪。 typeid还可以将被typedef的类型的原名称给显式出来 it1被当作指针一样想访问其对应的内容就直接解引用。 就对于string而言, 直接使用[ ]下标访问 更方便但是对于大部分数据结构iterator更加主流。 上文中的begin和end的用法也都符合所有的容器。 利用范围for遍历C11才支持 e是赋值拷贝对e或者--等操作不会实际影响s4中的字符大小。 但是范围for的自动循环在编译时其实和迭代器的底层是几乎一样的所以对于容器的学习主要掌握迭代器版本。 5.begin等函数的重载 const string s1(abcdefg); 由匹配规则我们知道当s1被const修饰时如果再调用begin会调用下面那个重载。 定义s1使用的const对应的是const_iterator begin() const中后面的那个const有const修饰和没const修饰的被认为是两种参数类型 然后返回一个const类型的iterator,这样返回的iterator就是只读的。 细心的读者可能已经发现了为什么不是const iterator而是const_iterator?
const限定的是迭代器所指向的内容迭代器指向的内容不能修改不代表迭代器本身不能修改。
如果迭代器本身都被限制得到的迭代器甚至不能无法遍历。 此处的差距就可以类比于指针的const的不同的修饰
string :: const_iterator const string :: iterator(这种我们一般不使用)更多使用string :: iterator和string :: const_iterator 还可以通过auto来减少输入量。 除了iterator和const_iterator还有反向迭代器用得不多: 此时对反向迭代器就是向左走--就是向右走。他同样有两种带const的和不带const的。带const的同样不能通过迭代器修改迭代器所指向的参数。 因为可以用方括号遍历的缘故string其实很少这样遍历。直接循环即可。 string::reverse_iterator re_it2 s2.rbegin();
while (re_it2 ! s2.rend()) {cout *re_it2 ;re_it2;
} 一共四种迭代器在之后的容器中都是同样的作用。 5.string在VS编译器下的大小了解 第一点不同的编译器的计算出的大小是不一样的此处只针对vs2019进行学习 string是一个字符串数组按理来说其由 _str _size _capacity三部分组成在x86也就是32位环境下应该是一个指针 两个int一共是12。但是其实string中还有一个大小为16的buffer数组当字符串数量小于16时直接存在string内不存在堆中因此大小为28 6.将string按照字典序排序 首先明确字典序就是ASCII的顺序。 其次此处我们需要引入一个新的头文件algorithm,并利用其中的算法sort sort是一个函数模板他不是属于容器string的类函数。sort函数的参数是各种类型的迭代器。 原文介绍如下 Sort elements in range Sorts the elements in the range [first,last) into ascending order. The elements are compared using operator for the first version, and comp for the second. Equivalent elements are not guaranteed to keep their original relative order stable_sort 可以直接排序vector等不过链表暂时不能直接排序。 底层是快速排序不具有稳定性。 传参时任然要遵守左闭右开
如果要全部排列直接使用迭代器的begin和end
如果只排前n个则直接让beginn即可因为类似于数组begin返回的是0位置。 由于0的存才si,begin()5其实指的是第六个字符 7.string的插入和修改
7.1 push_back 和 append
首先介绍老朋友push_back 插入常量字符串使用append 插入常量字符(只插入一个字符)使用push_back append有多种重载风格非常类似构造函数。
因此还需要再注意常量字符串是const char*的问题。 可以从指定的位置加入指定数量的字符、全部用某个字符去“覆盖式加入”、使用迭代器区间去添加。 如从指定位置开始的指定个数注意一定使用string类型变量不要用常量字符串等const char*类型变量 同样可能用到npos在无符号整形中这就是最大的数据。 7.2更常用的添加方法运算符重载
对于运算符的运算符重载 更加形象更易理解。 而且后面既可以是单个字符也可以是字符串。 7.3 assign函数
其本质是一种赋值会先清空本来有的内容 则s1中原先的内容会被改为111111。 7.4 重点 insert 与 erase insert的第一个参数都是与位置相关的下标或者迭代器。 但是insert能少用就少用因为其时间复杂度是O(n)每次插入都需要把被插入位置之后的所有元素平移。 但是不支持只在某个位置只插入一个字符 这样是不可以的 这样是可以的 但是给y加上一个双引号呢应该是没问题的但是必须有支持单个字符的情况否则无法应对诸多情况如字符作为变量 毕竟字符串不可能完全替代字符的插入。
如下4的意思是在第四个字符的位置插入包括0会将位置4之后的元素都平移。 频繁使用平移插入时需要注意效率。
此处只实现第三种对应的是方法7就好也就是通过迭代器加入对应的区间中的字符串。 不过还是那句话insert的时间复杂度不低慎用。 erase同样时间复杂度为O(n),也要慎用。 关于erase共有三种用法一种是关于下标的从pos位置删len个。还有两种是迭代器版本的。 我们观察第一个重载默认是从0位置开始删除size_t类npos个数据很多个也就是如果什么都不传就会全部删完。 同理如果还是is too short依然是有多少删多少。 长度超了就自动删完但是下标超了或者迭代器超了就会报错。下标和迭代器必须合法 7.5 replace替换函数 注意两个迭代器传参时的左闭右开 将第五个位置开始的一个元素换成后面的内容此处为const char*
对于迭代器版本i1和i2依然指的是一个左闭右开的空间。 针对是char* 还是string的问题 之前的解释都没有错但是只实现一个string版本的就可以了因为string类型可以用char* 去自动构造只是在char*和string都存在时会使用更匹配的那个。 之前的构造函数中需要注意两种参数的不一样是因为 char*作为参数和string作为参数的功能是不一样的前者表示前n个后者表示从下标为n的位置开始的。这次是一样的所以只用实现一个。 但是隐式类型转换又会一定程度上较低效率而c就是以效率著称的语言....... 比如我们想实现一个功能将给出的string 类型的s中的所有空格都替换为%20
string DeleteSpace(string s) {for (auto it s.begin(); it ! s.end();) {if (*it ) {s.replace(it, it1, %20);it 3;}else {it;}}return s;
} 如果写成s.replace(it,it,%20)就会不停的在第一个空格处加上%20。左闭右开的目的就是从 左边的闭区间开始替换但是不替换右边开区间那个位置因此会不停的替换直到溢出。 使用迭代器时尤其是两个迭代器都要注意左闭右开的问题。 (replace处也可以直接使用下标版本) 但是这样效率并不高 除非替换的内容相互一样长将三个元素换成另外三个元素。 否则每次都涉及平移后面的全部内容。 可以用空间换时间的做法
string QuickDeleteSpace(string s) {string ret;for (auto ch : s) {if (ch ! ) {ret ch;}else{ret %20;}}return ret;
}
但是此处的ret是临时变量不能再返回引用而应该传值返回。 8.小试牛刀
917. 仅仅反转字母 - 力扣LeetCode
class Solution {
public:bool IsLetter(char c){return (aczc)||(AcZc);}string reverseOnlyLetters(string s) {size_t left0,rights.size()-1;while(leftright){//让左右两个下标都找到是字母的位置。while(!IsLetter(s[left])leftright)left;while(!IsLetter(s[right])leftright)right--;swap(s[left],s[right]);left;right--;}return s;}
};
类似于快排中每一次单趟的方法。
387. 字符串中的第一个唯一字符 - 力扣LeetCode
利用计数统计建立哈希映射两次遍历。
new的开辟是利用了初始化的int数组值都为0
初始化的char数组值都为\0
class Solution {
public:int firstUniqChar(string s) {int* arrnew int[26]{0};for(auto e : s){arr[e-a];}for(int i0;is.size();i){if(arr[s[i]-a]1){delete[] arr;return i;}}delete[] arr;return -1;}
}; 在vs中作为内置类型char的数组delete delete[] free都可以用于释放new出来的数组但是在leetcode中只能使用delete[] 125. 验证回文串 - 力扣LeetCode 125. 验证回文串 - 力扣LeetCode 回文判断都是头尾指针。
此题最大的坑在于‘0’32是P所以直接用32加减的方法不妥。需要加上判断语句。
class Solution {
public:bool IsLetterOrNumber(char ch){if(chA chZ){ch32;return true;}return (cha chz)||(ch0ch9);}bool isPalindrome(string s) {int left0,rights.size()-1;while(leftright){while(leftright !IsLetterOrNumber(s[left]))left;while(leftright !IsLetterOrNumber(s[right]))right--;if(s[left]!s[right]){return false;}left,right--;}return true;}
}; 难点大数运算之字符串加减
415. 字符串相加 - 力扣LeetCode
class Solution {
public:string addStrings(string num1, string num2) {int pcur1num1.size()-1;int pcur2num2.size()-1;string ans; ans.reserve(max(num1.size(),num2.size()));int next0;while(pcur10||pcur20){int x1 pcur1 0 ? num1[pcur1]-0 : 0;int x2 pcur2 0 ? num2[pcur2]-0 : 0;nextx1x2next;ans.insert(0,1,next%100);next/10;--pcur1,--pcur2;} if(next){ans.insert(0,1,1);}return ans;}
}; 此处的reverse是用来先调整capacity大小目的是提升效率不加这一句也能跑过。但是不能乱使用resize。如果胡乱加大了size空间ans串中可能有其他意想不到的值 我们进一步优化我们的算法计算此时的时间复杂度 算时间复杂度时需要联系每个接口来计算此处消耗最大的就是每一次的insert(不想使用第二个参数也可以使用iterator版本)。如此处的头插复杂度就是n^2. 所以可以使用尾差加逆置使用algorithm中的reverse使用方法直接查cpp官网的方法复杂度就是O(n) class Solution {
public:string addStrings(string num1, string num2) {int pcur1num1.size()-1;int pcur2num2.size()-1;string ans; ans.reserve(max(num1.size(),num2.size()));int next0;while(pcur10||pcur20){int x1 pcur1 0 ? num1[pcur1]-0 : 0;int x2 pcur2 0 ? num2[pcur2]-0 : 0;nextx1x2next;//ans.insert(ans.begin(),next%100);ans.push_back(next%100);next/10;--pcur1,--pcur2;} if(next){ans.push_back(1);}reverse(ans.begin(),ans.end());return ans;}
}; 9.capacity大类 capacity表示当前string实际开出的空间大小这一点有别于sizesize表示的是此时已有字符串所占用空间的大小。 9.1 max_size(了解)
max_size没什么用目的就是告诉你理论上最多能开出多大的空间。 实际上是不可能开出这么大空间的这已经是九百万TB了 9.2clear
就是全部清空类似于不传参的erase 9.3扩容
在vs上因为buffer数组的存在
第一次严格意义不算扩容因为刚开始都是存在buffer数组上的。
第一次change之后就开始在堆上存放数据了。 void TestOfCapacity(string s) {size_t sz s.capacity();cout the primary size : sz endl;for (int i 200; i 0; i--) {s.push_back(p);if (sz ! s.capacity()) {sz s.capacity();cout now the size of capacity is : sz endl;}}
}
capacity显式出来的比实际的capacity的空间少一个会预留一个给\0
在vs2019中刚开始是二倍扩容后面是接近一点五倍扩容
在linux中 明显没有buffer数组 并且每次都是2倍扩容。
g编译器更加直观vs的编译器封装更加全面有其自己的想法。
不过无论g还是vscapacity都没有计算斜杠零。 9.4 resize和reserve ★★
reserve(保留意为保留一定量的空间区分于逆置reverse)和resize,分别用来管理capacity和size 但是两者的影响范围又稍有不同 reserve只影响capacityresize主要目标是影响size但是因为影响了size所以也会影响capacity。 reserve:
在vs中
你需要n个空间他可能开的比n多。 对于reserve缩容不同的平台有不同的实现所以不建议使用。
并且vs中的string有一个buffer数组所以再怎么变都不会小于15 真实大小是16还有一个位置留给\0
reserve的真正作用是在知道大致需要多少空间时节省扩容的动作 提升了效率。 不过依然有一个问题 这样操作会越界编译器会报错。 operator []只能访问size以内的部分而reserve不会改变size所以超过size的部分依然不能被使用。因此在reserve之后是不能实现从尾部开始使用的任然只能使用原size以内的部分。 resize: 如果不给值默认值就是ASCII值为0的‘\0’ 在已有空间上使用resize并且初始化内容: 不会改变原空间内容但是会同时对capacity和size造成影响。 练一练
//下面程序的输出结果是:
int main()
{string str(Hello Bit.);str.reserve(111);str.resize(5);str.reserve(50);coutstr.size():str.capacity()endl;return 0;
}
在vs2022中最后输出的结果是 5 11 分析: str.reserve(111); //调整容量为 111 str.resize(5); //调整元素个数为 5 str.reserve(50); //调整容量为 50由于调整的容量小于已有空间容量故容量不会减小 所以size5 capacity111 9.5 shrink_to_fit
该函数是专门用来缩空间的。 但是空间在底层是不能分段释放的。
所以其本质是开一个更小的空间把已有内容拷贝过去。本质是时间换空间的做法代价较大。
//调用方法
str.shrink_to_fit(); 9.6 at
功能与重载的[]类似区别在于检查方面[ ]用assert检查会直接报错而at可以在抛异常时捕获。
但是只有下标版本没有迭代器版本。 9.7 c_str
string是可以由char*作为参数来构造的但是char* 不能通过string来构造。
作用是将string转换到c语言中的标准字符串。 目的是与只能编C的接口兼容如fopen不能使用str只能使用char* , 此时就能发挥c_str的作用。
string file(string_test.cpp);
FILE* pf fopen(file.c_str(), r);
注意c_str返回的类型是const char* 所以对于下题 string ahello world;string ba;if (a.c_str()b.c_str()){couttrueendl;}else coutfalseendl; a和b的内容虽然一样但是存放的地址不一样所以应该输出false。 10.find 由缺省参数为0可知find函数默认都是从头开始找。给了数字之后就可以从数字对应的位置开始找。
可以找单个字符也可以找一个句子。
若想从尾部开始找可使用refind。
比如我们想取出一个后缀名suffix 此时又涉及一个操作substr 将pos位置开始长度为len的内容拷贝到一个新生成的字符串中去。 记住substr的两个参数都是整数即可前一个是位置后一个是长度。 string file(string_test.cpp);
size_t posfile.find(.);
string suffix file.substr(pos, file.size() - 1);cout suffix endl; 再比如
希望用find分别得到一个网址的协议域名端口 。
网址
https://leetcode.cn/problems/add-strings/description/
string url(https://leetcode.cn/problems/add-strings/description/);
size_t pos1 url.find(:,0);
string url1 url.substr(0, pos1 - 0);
size_t pos2 url.find(/, pos1 3);//从leetcode的l处开始寻找
string url2 url.substr(pos1 3, pos2 - (pos1 3));
string url3 url.substr(pos2 1, url.size() - (pos2 1));cout url1 endl url2 endl url3 endl; 此处选取pos时依然利用左闭右开的好处直接做减法就能获得长度len find_first_of 四兄弟 (类似于strtok) 了解即可 使用一个string类型对象调用该函数时他能正向或逆向找出 非你给出的参数中第一个与string对象中所包含元素一样的位置。所以最坏时间复杂度是两个串的长度之积,O(m*n) 官网解释 Searches the string for the first character that matches any of the characters specified in its arguments.功能 When pos is specified, the search only includes characters at or after position pos, ignoring any possible occurrences before pos.第二个参数pos的作用 Notice that it is enough for one single character of the sequence to match (not all of them). See string::find for a function that matches entire sequences.与find区分 find_last_of的实际作用 比如在一个项目中需要处理不同系统下的多个文件路径但是由于Linux中的文件分隔符是右斜杠/windows中的文件分隔符是左斜杠\ 如果使用find函数查找这两个·会去找这两个一起出现的字符串当然找不到此时就需要find_first_of来发挥作用 void SplitFilename(const std::string str)
{std::cout Splitting: str \n;std::size_t found str.find_last_of(/\\);std::cout path: str.substr(0, found) \n;std::cout file: str.substr(found 1) \n;
}int main()
{std::string str1(/usr/bin/man);std::string str2(c:\\windows\\winhelp.exe);cout str2 endl;SplitFilename(str1);SplitFilename(str2);return 0;
}
左斜杠\\需要多加一个表示转义字符而右斜杠/不用在windows中的操作要注意这个。
转义字符仍然只是一个字符。
11. string相关的部分外部函数
11.1 operator
为什么不能写成成员函数而是全局重载 原因就在于最后这种无法通过成员函数实现。 除了char* char*没有实现其他都能直接加。
11.2 operator
类似于strcmp按照字典序比较两个字符串相应位置的ASCII码值。
成立返回1不成立返回0。
流插入的优先级较高需要加括号。 11.3 getline
getline:
想获取一行中包含空格的串不能直接使用流提取需要使用getline 字符串最后一个单词的长度_牛客题霸_牛客网 (nowcoder.com)
#include iostream
using namespace std;int main() {string s;getline(cin,s);int poss.rfind( );couts.size()-(pos1);return 0;
} 持续获取 你如果一次输入按下三次空格再回车其实这个循环就走了三次空格作为分隔符将之后的内容都存在缓存区cout的时候会输出全部再等待下次输出。 使用 ctrlZ回车 可以终止这个程序。 11.4 字符串和int类型的转换 to_string和stoi(类比于C语言的atoi itoa a to i ASCII到int i to a int 到ASCII)
但是stoistring to int不能处理大数运算串长之后就会爆放不下。 12.编码表UNICODE
string的底层是如何装汉字的呢
计算机中的编码除了ASCII编码还有万国码UNICODE。
万国码支持ASCII编码并以此为基础增加了世界上绝大多数国家的语言文字。
大部分汉字编入两个字节的部分部分生僻的编入3字节或者4字节 因此有可能一个字节表示有可能两个字节表示有可能三个字节去表示。 string默认支持UTF8还有默认支持UTF16和UTF32、以及双字符的wstring
所有的string都是以basic_string为模版实现的。 还有一种库叫GBK库由于万国码在中文一些方面优化的不够好这一套GBK作为国标也被很多系统支持如windows等更适合中国宝宝的体质。
