【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)$ 的。其内部的数据结构大致如下：

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_view 的 string 不能修改，否则再次访问对应的 string_view 时，行为未定义。

---

std::string_view 的使用

使用前引入以下头文件：

#include <string_view>

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

(1) 创建 Create

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

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

string str_a("a");

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

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

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

string str_b("b"s);

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

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

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

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

string_view strv_c("c");

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

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

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 的拼接受限制。

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::stringstream、std::ostringstream 和 std::istringstream 类是更合适的，因为它们增强了内存管理，并且提供了格式化功能。

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

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

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

(3) 转换 Transformation

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

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_prefix 和 remove_suffix。

---

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

std::string 的做法

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

string::find_first_not_of
string::find_last_not_of

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

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 的做法

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++)

• 枚举前缀

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++)

• 枚举子串

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();
    }
};

---