分类
Algorithm C++

C++ Library(2)

C++ Library(2)

4.字符串 string

4.1 定义

string代表字符序列(字符串),如”haha”、”Hello world! “等都可以称之为字符串(严格一点说,是字符串”值”)

4.2 常用运算

  • operator +

“`C++
string a = “1”;
string b = “2”;
string c = a + b;
cout << a + b << endl;


字符串可以直接相加, 结果等于两个字符串顺次连接 > > 练习1: 已知`string s = "1";` 下列哪些语句会编译错误? A.`string a = s + "2";` B.`string b = "1" + s + "2";` C.`string c = s + 1;` D.`string d = s + '2';` ### 4.3 常用函数 #### size()/length() 不多说 #### 插入insert(),删除erase(),替换replace(),子串substr() 参数形式较为统一:起始位置、长度、字符串(后两个参数依据具体函数而情况不同) ```c++ string a = "HelloWorld!"; // 0123456789 a.insert(5, ","); //Hello,World! a.erase(5, 5); //Hello! a.replace(5, 5, "OI"); //HelloOI!

值得注意的是,string在对非结尾处进行插入、删除、替换的时候的效率是较低的,在暴力的时候要慎重考虑使用。

一般情况下我们只使用string的+、[]、size()等操作

查找find()

string.find(要找的字符或字符串, 起始位置);

起始位置可以不填, 不填则默认为0

返回找到的第一个位置的下标, 没找到则返回一个常数string::npos, 这个常数是一个「机器相关」的数字, 转成int的时候「通常」为-1, 所以我们通常直接用string::npos而不用-1来判断

string s = "Hello world!";
cout << s.find ("o") << endl; // 输出4
cout << s.find ("o", 5) << endl; //输出7
cout << s.find ("o", 8) << endl; // 本机输出18446744073709551615
cout << (int) s.find ("hello", 8) << endl; // 本机输出-1

那么, 如何输出一个字符串中某个串出现的所有位置呢?

string s = "abcsasdqaweawqfdgadfsjhxacvazhwuaeyr";
string x = "a";
int pos = s.find (x); //先找到第一个位置
while (pos != string::npos)
{
    cout << pos << endl;
    pos = s.find (x, pos + 1);
}

练习2:P2799 国王的魔镜

推荐使用「递归」和string的一些函数

5.集合 set

C++中的集合set底层实现是平衡二叉树, 可以进行插入删除等操作来维护一个有序的集合, set的(中间)插入、删除等操作比序列容器vector要快很多

注意:set是默认没有重复元素的

常用操作:

set<int> s;
s.insert (1);//此时s中元素为{1}
s.insert (3);//此时s中元素为{1,3}
s.insert (2);//此时s中元素为{1,3,2}
s.insert (1);// 集合是没有「重复元素」的, 所以这句话没有产生什么影响
cout << s.size() << endl;
cout << s.count (1) << endl;//输出1, 最多也只会有一个元素, 所以count函数一般可以用来判断是否存在集合中
s.erase (2);
cout << s.count (2) << endl;//2被删除了, 所以输出0

练习3:P3370 【模板】字符串哈希

使用set水过去!

6.映射 map

map,可以看作是set的加强版, 大多数时候可以替代set

map表示的是一种「映射关系」, 并且是任意的映射关系(这取决于你想怎么映射)

我们最常用的一种映射关系就是int数组, 这是一种「int」到「int」的映射关系, 每一个int(当然必须在下标范围内)都「对应」着另一个int

对应于map,我们可以写一个「不算太无聊」的程序来作为示例:

map<int, int> mii;//建立一个int到int的映射
mii[1] = 1; //是不是很像数组?
mii[-1] = 1; //不过这个数组的「下标」只要是int就可以了
mii[1000000000] = 1;//如果是数组这样写, 内存就爆了
//不用担心这样子会产生很多内存, 实际上只产生了3份(因为map是动态申请的内存), 几乎忽略不计了
cout << mii.size() << endl;//输出3, 我们的map并没有占用很多空间
cout << mii[5] << endl;//虽然我们之前没有给这个位置赋值, 但是当我们直接访问的时候, map发现mii[5]不存在的话, 会自动创建一个, 并且初始化一个默认值(对于整数int, 当然就是0)
cout << mii.count (8) << endl; //输出0, 因为8并不在map里面(我们还没有用过8), 使用count函数并不会自动创建8, 所以我们可以用count来帮助判断map里面是否有这个键(key)
cout << mii.count (5) << endl; //输出1, 因为之前访问过mii[5]了, 所以5已经存在于map里面了
mii.erase (5);
cout << mii.count (5) << endl; //输出0, 因为5被我们删除了

同时还可以有非常多的应用:

map<string, int> msi;//建立一个string到int的映射
msi["sunlaoshi"] = 100;
msi["zhalaoshi"] = 90;
msi["wanglaoshi"] = 0;

练习4:P1032 字串变换

双向BFS, queue/string/map综合应用

7.迭代器 iterator

类似于指针, 比指针更高级和安全

map<int, int> cnt;
for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); ++it)
{
    cout << (it->first) << ' ' << (it->second) << endl;
}

练习5:P1097 统计数字

map+迭代器水过去

发表评论

电子邮件地址不会被公开。 必填项已用*标注