【C++17】string_view

  |  

摘要: 本文介绍 C++17 中的一个字符串相关的新特性 string_view,主要参考《C++17 STL Cookbook》$7-3

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文介绍 C++17 中的一个字符串相关的新特性 string_view,主要参考《C++17 STL Cookbook》$7-3。

本文我们先提出 string_view 解决的 std::string 中的问题,然后介绍 string_view 的好处、局限和用法。最后我们用 string_view 解决两道力扣中的题目 1392 (枚举前缀) 和 1316 (枚举子串)。


std::string 的问题以及 std::string_view 的解法

string 的问题

std::string 是持有对象的,并且可变 (mutable)。在实际使用中可能会遇到以下问题:

在参数传递时如果要传递 string,为了避免拷贝,可以用 const string& s 作形参。但是调用方给的实参可能是 char[] 或者 char*,如果出现这种情况,则传参时还是会创建临时的 string 对象。当然 C++11 之后,如果想转移 string 的所有权,例如函数返回 string、将 string 交给另一个数据结构等,可以不用拷贝,因为可以用 std::move

此外 string 的一些操作是需要通过迭代器 $O(N)$ 来完成的,例如 substr,取前后缀等。

string_view 的解法

C++17 在 std::string 的基础上增加了 std::string_view,不持有对象,并且不可变。

从 string 或者 constexpr char* 转换 string_view 的过程是 $O(1)$ 的。其内部的数据结构大致如下:

1
2
3
4
5
struct string_view
{
const char *data;
int length;
}

std::string_view 的好处

  • 形参改为 string_view s 传参时候就无拷贝了。
  • 大部分接口与 std::string 相同。
  • 以前必须通过迭代器 $O(N)$ 完成的操作,其中某些可以 $O(1)$ 了,例如:删前后缀,取 substr

std::string_view 的局限

  • 追加和拼接还是会触发拷贝。
  • 创建 string_viewstring 不能修改,否则再次访问对应的 string_view 时,行为未定义。

std::string_view 的使用

使用前引入以下头文件:

1
#include <string_view>

string_view 的基础用法有创建、拼接转换。下面分别介绍。

(1) 创建 Create

如果是创建 std::string,有两种创建方法,构造函数均会拷贝。

(1) 交给构造函数一个 C 风格字符串

1
string str_a("a");

编译后,C 风格字符串将作为包含字符的静态数组嵌入二进制文件中。

(2) 交给构造函数一个 string literal

string literal 的写法是在后面加一个 s,例如 "a"s

1
string str_b("b"s);

string 对象可以运行时创建。关于运行时创建对象和编译时创建对象的细节这里不深究,只罗列一下静态创建类对象、动态创建类对象、栈、堆的基础理解。

  • 静态创建类对象:由编译器为对象在栈空间中分配内存,通过直接移动栈顶指针挪出适当的空间,然后在这片内存空间上调用构造函数形成一个栈上的对象。
  • 动态创建类对象:使用 new运算符将对象创建在堆空间,在栈中只保留了指向该对象的指针。
  • 由编译器自动分配释放 ,存放函数的参数值,局部变量的值,对象的引用地址等。其操作方式类似于数据结构中的栈,通常都是被调用时处于存储空间中,调用完毕立即释放。
  • 中通常保存程序运行时动态创建的对象,C++ 堆中存放的对象需要由程序员分配释放,它存在程序运行的整个生命期,直到程序结束由 OS 释放;在Python中通常类的对象都分配在堆中,对象的回收由虚拟机的GC垃圾回收机制决定。

std::string_view 也有同样的两种创建方法,不会拷贝,仅引用所依赖的 string。

(1) 交给构造函数一个 C 风格字符串:

1
string_view strv_c("c");

(2) 交给构造函数一个 string_view literal

stiring_view 也有 literal operator,写法是在后面加一个 sv

1
string_view strv_d("d"sv);

(2) 拼接 Concatenate

std::string 重载了 +,因此 str_a + str_b 很简单。

string 和 string_view 混合

str_a + strv_c 就不容易了,首先需要将 strv_c 依赖的字符串取出来,这一步通过由 strv_c 构造一个临时的 string 实现,但这样就拷贝了。如果寄希望于使用 strv_c.data() 避免拷贝也有问题:string_view 对象依赖的字符串不一定是 zero-terminated 的,这可能引发缓冲区溢出。因此 string_view 的拼接受限制。

1
2
3
str_a + strv_c;
str_a + string(strv_c);
str_a + strv_c.data(); // 错误

std::string::append 接受 string_view 实参

std::string 提供了一个成员函数 append, 它可以处理 string_view 实例。它会更改原字符串,而不是返回一个附加了 string_view 内容的新字符串。

(io)stringstream — 处理 string 和 string_view 混合拼接的最佳方案

如果要进行复杂的字符串拼接,我们不应该在字符串实例上逐个执行。使用std::stringstreamstd::ostringstreamstd::istringstream 类是更合适的,因为它们增强了内存管理,并且提供了格式化功能。

如果我们要创建一个字符串而不是解析,使用 ostringstream;如果我们要从已有的字符串进行解析,用 istringstream。如果创建和解析都要做,可以用 stringstream

利用 str_a, str_b, strv_c, strv_d 创建一个新的 string

1
2
3
ostringstream o;
o << str_a << " " << str_b << " " << strv_c << " " << strv_d;
auto concatenated(o.str());

(3) 转换 Transformation

例如将所有字母变大写,可以用 C 库函数 toupper 结合 std::transform

1
transform(begin(concatenated), end(concatenated),begin(concatenated), ::toupper);

string_view 的特性

带有串长信息

std::string 方便了字符串的处理,但还是有痛点:传递子串的时候要么传递一份拷贝,要么传递完整串的引用,同时带上头和尾的两个指针或迭代器。

如果要给一个尚不支持 std::string 的库传递 string,则情况更糟,只能传递 C 风格字符串(raw string pointer)。raw pointer 的最大问题就是不带有串长的信息。

C++17 出现 std::string_view 之后,串长的问题就简化了,string_view 直接带 length 方法。

因此 string_view 的一个重要的好处是可以处理非 zero-terminated 的字符串,因为 std::string_view 自带 length 字段,print 函数可以安全处理。但也有要注意的点:通过计数到 zero terminator 之前的字符个数确定 string_view 对象的数据长度的做法是错的。

传递 string 实参时避免复制

设计函数时,如果接受的是一个 std::string 对象,在函数内对该 string 对象不做需要重新分配内存的修改,则可以用 string_view,兼容更多的 STL-agnostic 的库。

当形参为 std::string_view 喂进去 std::string 的实参时,不会发生堆内存分配。

提供 string 对象的 substr 无拷贝引用

string_view 的另一个重要的好处就是提供了 string 对象的 substr 的无拷贝引用。

此外可以无拷贝删除前缀和后缀,方法为 remove_prefixremove_suffix


例子:去除 string 开始和结束的 whitespace

std::string 的做法

可以使用下面的两个辅助函数。

1
2
string::find_first_not_of
string::find_last_not_of

如果输入 string 只有 whitespace,则返回 string::npos

1
2
3
4
5
const size_t first(s.find_first_not_of(whitespace));
if(string::npos == first)
return {};
const size_t last(s.find_last_not_of(whitespace));
return s.substr(first, (last - first + 1));

substr 返回一个有自己内存的新的 string 对象。

std::string_view 的做法

1
2
3
4
5
const auto words_begin(v.find_first_not_of(" \t\n"));
v.remove_prefix(min(words_begin, v.size()));
const auto words_end(v.find_last_not_of(" \t\n"));
if(words_end != string_view::npos)
v.remove_suffix(v.size() - words_end - 1);

原文的精辟总结

当你要传递字符串或子字符串,但希望避免复制或堆分配,并且不会丢失 string 类的舒适度,可以用 string_view,但需要注意string_view 放弃了字符串为零的假设。


题目

1392. 最长快乐前缀

「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀(不包括原字符串自身)的字符串。

给你一个字符串 s,请你返回它的 最长快乐前缀。如果不存在满足题意的前缀,则返回一个空字符串 “” 。

代码 (C++)

  • 枚举前缀
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
string longestPrefix(string s) {
int n = s.size();
string_view view = s;
for (int l = n - 1; l >= 1; --l)
{
if (view.substr(0, l) == view.substr(n - l))
return s.substr(0, l);
}
return "";
}
};

1316. 不同的循环子字符串

给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目:

可以写成某个字符串与其自身相连接的形式(即,可以写为 a + a,其中 a 是某个字符串)。

例如,abcabc 就是 abc 和它自身连接形成的。

代码 (C++)

  • 枚举子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int distinctEchoSubstrings(string text) {
int n = text.size();
string_view t_sv(text);
unordered_set<string_view> setting;
for(int len = 1; len * 2 <= n; ++len)
{
for(int i = 0; i <= n - len * 2; ++i)
{
if(t_sv.substr(i, len) == t_sv.substr(i + len, len))
setting.insert(t_sv.substr(i, len));
}
}
return setting.size();
}
};

Share