brpc小课堂：从StringPiece说开来

319次阅读  |  发布于2年以前

序言

在brpc源码的src目录下，有一级子目录名为butil。代码中的util目录一般就是存放常用的工具类或函数的地方。今天我们来聊一下butil/strings/string_piece.h(cpp) 中的StringPiece类。

其实brpc项目中的StringPiece并非brpc原创，而是从Google的Chromium项目中拿过来的。

可以看下该文件的开头的注释：

// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Copied from strings/stringpiece.cc with modifications

因为Chromium项目是以BSD开源协议发布的，所以brpc拿过来用，其实并没有问题。只需要保留原项目的BSD协议声明即可。

其实StringPiece并不新鲜，在很多C++项目中都能见到类似的字符串工具类的身影。

项目 (类名） 源码在线阅读地址
chromium (StringPiece) https://github.com/chromium/chromium/blob/master/base/strings/string_piece.h
llvm (StringRef) https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/StringRef.h
boost (string_ref) https://github.com/boostorg/utility/blob/master/include/boost/utility/string_ref.hpp
folly (StringPiece) https://github.com/facebook/folly/blob/main/folly/Range.h
pcre (StringPiece) https://opensource.apple.com/source/pcre/pcre-4.1/pcre/pcre_stringpiece.h.in.auto.html
leveldb (Slice) https://github.com/google/leveldb/blob/master/include/leveldb/slice.h
abseil (string_view) https://github.com/abseil/abseil-cpp/blob/master/absl/strings/string_view.h
boost (string_view) https://github.com/boostorg/utility/blob/master/include/boost/utility/string_view.hpp

其中boost的string_ref实现方式是参考的llvm的StringRef以及谷歌发布的这个提案：string_ref: a non-owning reference to a string

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3442.html

brpc采用了Chromium的实现，muduo采用了pcre的实现。这两个几乎是照搬的源码（brpc仅微调），故不列到上面的表格中了。

何谓StringPiece？

StringPiece和普通std::string的最大不同之处是，它并不持有数据！俗称是StringPiece没有数据的所有权。它存储的是外部字符串的数据指针，而自己并没有开辟空间在存储这份数据（字符串）。因此StringPiece中数据的生命周期并不和StringPiece等价，而是依旧和传入的数据指针的来源一致。

比如下面这段代码就是高危操作：

StringPiece foo() {
    std::string str = "xxx";
    ...
    return StringPiece (str); // 函数返回时，StringPiece持有的数据（属于str）已经析构 
}
void bar() {
    StringPiece sp = foo(); // 后面再通过sp访问其中的字符串时危险的
    cout<<sp.data() << endl; // 危险！
}

StringPiece的常见使用场景

看完上面例子，你会不会感觉StringPiece太危险了，那它存在有必要吗？答案是肯定的，因为有时候尽管我们需要字符串中的一段数据，但并不需要潜在的字符串拷贝。最常见的例子就是字符串拆分的时候。、字符串切分是一个高频操作，在NLP领域，这个操作被称为tokenize，切分出来的单词称为token。

但C++没有像其他语言一样提供官方的std::string的split()函数，为此各种实现五花八门。比如这种：

void split(std::vector<std::string> &vec, const std::string& str, const std::string& sep) {
    size_t start = str.find_first_not_of(sep);
    size_t end;

    while (start != std::string::npos) {
        end = str.find_first_of(sep, start + 1);
        if (end == std::string::npos) {
            //vec.push_back(str.substr(start));
            vec.emplace_back(str, start);
            break;
        } else {
            //vec.push_back(str.substr(start, end - start));
            vec.emplace_back(str, start, end - start);
        }
        start = str.find_first_not_of(sep, end + 1);
    }
}

这里其实就是会产生临时字符串拷贝的开销，每个被切割出来的token字符串都会拷贝到vector容器中。但有时候在我们接下来的使用观察中，我们对于切分好的token其实并不会去修改它，都是只读操作。

换句话说我们只是观测它而已，那么我们完全没必要这么多token的拷贝！这时候StringPiece就派上用场了。你可以将传入的string，赋值给一个StringPiece对象，然后让StringPiece去参与split的过程，最后存储到vector的容器中。

这样整个过程完全没有字符串拷贝的开销。当然如果你split完的字符串，后续你需要修改它，那么用StringPiece依旧是危险的。

源码剖析StringPiece

下面针对StringPiece源码的解读是基于brpc中代码，也就是Chromium的实现来展开。这一节很长，你可能感觉枯燥，你可以根据目录，选择性地查看相关内容。

BasicStringPiece模板

StringPiece其实是BasicStringPiece类模板用std::string实例化后的类型：

typedef BasicStringPiece<std::string> StringPiece;

来看BasicStringPiece模板的定义：

template <typename STRING_TYPE> class BasicStringPiece {
 public:
  // Standard STL container boilerplate.
  typedef size_t size_type;
  typedef typename STRING_TYPE::value_type value_type;
  typedef const value_type* pointer;
  typedef const value_type& reference;
  typedef const value_type& const_reference;
  typedef ptrdiff_t difference_type;
  typedef const value_type* const_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  static const size_type npos;
...

先记住两个类型：

再看看唯二的成员变量：

 protected:
  const value_type* ptr_;
  size_type     length_;

一个指针ptr_指向字符串数据，还有一个length_标记该字符串的长度。一个指针类型，一个size_type类型，所以StringPiece基本就是两个long的大小，轻量的很。

构造函数

再来看看它的构造函数：

  BasicStringPiece() : ptr_(NULL), length_(0) {}
  BasicStringPiece(const value_type* str)
      : ptr_(str),
        length_((str == NULL) ? 0 : STRING_TYPE::traits_type::length(str)) {}
  BasicStringPiece(const STRING_TYPE& str)
      : ptr_(str.data()), length_(str.size()) {}
  BasicStringPiece(const value_type* offset, size_type len)
      : ptr_(offset), length_(len) {}
  BasicStringPiece(const BasicStringPiece& str, size_type pos, size_type len = npos)
      : ptr_(str.data() + pos), length_(std::min(len, str.length() - pos)) {}
  BasicStringPiece(const typename STRING_TYPE::const_iterator& begin,
                    const typename STRING_TYPE::const_iterator& end)
      : ptr_((end > begin) ? &(*begin) : NULL),
        length_((end > begin) ? (size_type)(end - begin) : 0) {}

可以看出StringPiece支持传入C风格字符串（const char*)，也支持传入std::string。甚至你也可以指定传入的std::string的起始位置以及长度。也就是说StringPiece不必持有全部的原始std::string的字符串，而是可以只取其一段。当然普通的std::string的构造函数也支持传入另外一个std::string并指定其起始位置和长度，但是std::string的做法是将原字符串的这一小段字符串拷贝到自己的堆存储中来，后面就和原字符串没有瓜葛了。但StringPiece却不会做这个拷贝操作，所以它依旧和原始字符串藕断丝连！

这里指的一提的是当只传入const char*，不指定长度的时候。StringPiece会调用string::traits_type::length()函数来计算长度。

http://www.cplusplus.com/reference/string/char_traits/length

Get length of null-terminated stringReturns the length of thenull-terminatedcharacter sequences.

返回的是'\0'结尾的字符串的长度。如果你传入的const char*类型的字符串中间有'\0'会被截断。

容量相关函数

  const value_type* data() const { return ptr_; }
  size_type size() const { return length_; }
  size_type length() const { return length_; }
  bool empty() const { return length_ == 0; }
...
  size_type max_size() const { return length_; }
  size_type capacity() const { return length_; }

这是几个比较简单的函数。需要这里的是data()返回的就是持有的字符串的指针，这段数据的中间也可能是存在\0的，比如size()是10，但是在第5个字符处是\0，这也是完全有可能的。这一点和普通的std::string其实也一样。

另外size()、length()、max_size()、capacity()这4个函数返回的都是length_，他们的值是相同的。这点和std::string是不同的。

  void clear() {
    ptr_ = NULL;
    length_ = 0;
  }

clear()也很简单，只是单纯的将两个成员变量清零而已。StringPiece是没有resize()、reserve() 函数的。

数据修改函数

  BasicStringPiece& assign(const BasicStringPiece& str, size_type pos, size_type len = npos) {
    ptr_ = str.data() + pos;
    length_ = std::min(len, str.length() - pos);
    return *this;
  }
  void set(const value_type* data, size_type len) {
    ptr_ = data;
    length_ = len;
  }
  void set(const value_type* str) {
    ptr_ = str;
    length_ = str ? STRING_TYPE::traits_type::length(str) : 0;
  }

StringPiece可以从另外一个StringPiece通过assign()或set()函数来修改自己的数据。但是全程也都是修改自己的两个成员而已，并没有数据拷贝。

  void remove_prefix(size_type n) {
    ptr_ += n;
    length_ -= n;
  }

  void remove_suffix(size_type n) {
    length_ -= n;
  }

这两个函数表面上是移除字符串的前缀或后缀中的n个字符。实际也只是做的指针和长度的修改而已。修改后缀的时候，不需要调整ptr_。

相关的还有一个移除前后空格的trim_spaces()函数，本质是对前面两个函数的调用。

  // Remove heading and trailing spaces.
  void trim_spaces() {
    size_t nsp = 0;
    for (; nsp < size() && isspace(ptr_[nsp]); ++nsp) {}
    remove_prefix(nsp);
    nsp = 0;
    for (; nsp < size() && isspace(ptr_[size()-1-nsp]); ++nsp) {}
    remove_suffix(nsp);
  }

修改其他字符串的函数

StringPiece还支持修改其他的字符串。

  // 将StringPiece指向的这段字符串覆盖到target指向的位置
  void CopyToString(STRING_TYPE* target) const {
    internal::CopyToString(*this, target);
  }

  // 将StringPiece指向的这段字符串追加到target指向的位置
  void AppendToString(STRING_TYPE* target) const {
    internal::AppendToString(*this, target);
  }

  // 将StringPiece指向的这段字符串从pos位置开始复制n个字符到buf开始的位置中
  size_type copy(value_type* buf, size_type n, size_type pos = 0) const {
    return internal::copy(*this, buf, n, pos);
  }

这三个不一一展开介绍了。CopyToString()本质是调用的std::string的assign()函数。AppendToString()本质是调用的std::string的append()函数。copy本质调用的是memcpy()。

数据访问函数

  value_type operator[](size_type i) const { return ptr_[i]; }

可以通过下标运算符[]来访问StringPiece中的单个元素（即字符），这个函数和std::string是有区别的，下面这个是std::string中的定义：

      reference operator[] (size_type pos);
const_reference operator[] (size_type pos) const;

不同之一就是std::string支持const和非const两个重载，而StringPiece只有const版本。也就是无法通过[]来修改原类型的。其二就是std::string返回的都是引用（const版本是const引用），而StringPiece返回的值类型。这也不难理解，主要目的就是让Stringpiece的[]返回的单个字符和原字符串的生命周期解耦。（StringPiece内心OS：整个字符串的生命周期都是你的了，单个字符还是我说了算吧，不然也太不安全了）

其他访问函数还有：

  char front() const { return *ptr_; }
  char back() const { return *(ptr_ + length_ - 1); }
  // Return the first/last character, 0 when StringPiece is empty.
  char front_or_0() const { return length_ ? *ptr_ : '\0'; }
  char back_or_0() const { return length_ ? *(ptr_ + length_ - 1) : '\0'; }

支持front()、back()直接返回首尾元素，同样是const函数，且返回的是值。和普通std::string不同。比std::string多两个函数：front_or_0()和back_or_0()，他们是当字符串长度为0的时候，返回一个'\0'字符。

StringPiece也支持迭代器访问：

  const_iterator begin() const { return ptr_; }
  const_iterator end() const { return ptr_ + length_; }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(ptr_ + length_);
  }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(ptr_);
  }

可以正向遍历，也可以逆向遍历。但无一例外，也都是const函数，返回const迭代器。

比较函数

比较函数分为大类，一类是类内定义的成员函数，另外一类是类外定义的比较运算符的重载函数。先说第一类：

  // Does "this" start with "x"
  bool starts_with(const BasicStringPiece& x) const {
    return ((this->length_ >= x.length_) &&
            (wordmemcmp(this->ptr_, x.ptr_, x.length_) == 0));
  }

  // Does "this" end with "x"
  bool ends_with(const BasicStringPiece& x) const {
    return ((this->length_ >= x.length_) &&
            (wordmemcmp(this->ptr_ + (this->length_-x.length_),
                        x.ptr_, x.length_) == 0));
  }

这两个函数在std::string中是没有的。在定义中不难看出都是调用的wordmemcmp()：

  static int wordmemcmp(const value_type* p,
                        const value_type* p2,
                        size_type N) {
    return STRING_TYPE::traits_type::compare(p, p2, N);
  }

对于StringPiece而言，最终还是调用的这个C++标准中的traits函数：char_traits::compare

对应的这个实现：

static int compare (const char_type* p, const char_type* q, size_t n) {
  while (n--) {if (!eq(*p,*q)) return lt(*p,*q)?-1:1; ++p; ++q;}
  return 0;
}

其中eq和lt分别表示如何判断两个元素（字符）是否相等以及是否小于。对于字符而言这并不难。

现在说一下第二类，在StringPiece类外主要定义了operator==和operator<两个运算符。

bool operator==(const StringPiece& x, const StringPiece& y) {
  if (x.size() != y.size())
    return false;

  return StringPiece::wordmemcmp(x.data(), y.data(), x.size()) == 0;
}
inline bool operator<(const StringPiece& x, const StringPiece& y) {
  const int r = StringPiece::wordmemcmp(
      x.data(), y.data(), (x.size() < y.size() ? x.size() : y.size()));
  return ((r < 0) || ((r == 0) && (x.size() < y.size())));
}

可以看出他们还是在调用wordmemcmp()来完成比较。有了这两个函数以后，那剩下的 !=、>、>=、<= 就能能实现了。这里不赘述了。这一部分可以看出StringPiece在进行比较的时候并没有什么新意。核心部分还是C++库中已经实现的，针对两段连续存储的字符比较的功能。

查找函数

这块相关的函数比较多，首先看两个常用的两类查找函数，正向查找find()和反向查找rfind()：

  // find: Search for a character or substring at a given offset.
  size_type find(const BasicStringPiece<STRING_TYPE>& s,
                 size_type pos = 0) const {
    return internal::find(*this, s, pos);
  }
  size_type find(value_type c, size_type pos = 0) const {
    return internal::find(*this, c, pos);
  }

  // rfind: Reverse find.
  size_type rfind(const BasicStringPiece& s,
                  size_type pos = BasicStringPiece::npos) const {
    return internal::rfind(*this, s, pos);
  }
  size_type rfind(value_type c, size_type pos = BasicStringPiece::npos) const {
    return internal::rfind(*this, c, pos);
  }

他们都支持查找字符串和查找单个字符。并且还能指定查找的起始位置。然后返回查询到的位置。接口定义和std::string中是相同的。实现上来看他们都是调用的internal::find()/internal::rfind()，先看find()其定义如下：

size_t find(const StringPiece& self, const StringPiece& s, size_t pos) {
  return findT(self, s, pos);
}
size_t find(const StringPiece& self, char c, size_t pos) {
  return findT(self, c, pos);
}

他们都调用的findT()，但是是不同的重载。

template<typename STR>
size_t findT(const BasicStringPiece<STR>& self,
             const BasicStringPiece<STR>& s,
             size_t pos) {
  if (pos > self.size())
    return BasicStringPiece<STR>::npos;

  typename BasicStringPiece<STR>::const_iterator result =
      std::search(self.begin() + pos, self.end(), s.begin(), s.end());
  const size_t xpos =
    static_cast<size_t>(result - self.begin());
  return xpos + s.size() <= self.size() ? xpos : BasicStringPiece<STR>::npos;
}

template<typename STR>
size_t findT(const BasicStringPiece<STR>& self,
             typename STR::value_type c,
             size_t pos) {
  if (pos >= self.size())
    return BasicStringPiece<STR>::npos;

  typename BasicStringPiece<STR>::const_iterator result =
      std::find(self.begin() + pos, self.end(), c);
  return result != self.end() ?
      static_cast<size_t>(result - self.begin()) : BasicStringPiece<STR>::npos;
}

可以看出对于查找字符串其本质是使用的STL的search()函数，而查找单个字符的时候使用的是STL的find()函数。不过对于rfind()则并不相同。它的实现如下：

template<typename STR>
size_t rfindT(const BasicStringPiece<STR>& self,
              const BasicStringPiece<STR>& s,
              size_t pos) {
  if (self.size() < s.size())
    return BasicStringPiece<STR>::npos;

  if (s.empty())
    return std::min(self.size(), pos);

  typename BasicStringPiece<STR>::const_iterator last =
      self.begin() + std::min(self.size() - s.size(), pos) + s.size();
  typename BasicStringPiece<STR>::const_iterator result =
      std::find_end(self.begin(), last, s.begin(), s.end());
  return result != last ?
      static_cast<size_t>(result - self.begin()) : BasicStringPiece<STR>::npos;
}

template<typename STR>
size_t rfindT(const BasicStringPiece<STR>& self,
              typename STR::value_type c,
              size_t pos) {
  if (self.size() == 0)
    return BasicStringPiece<STR>::npos;

  for (size_t i = std::min(pos, self.size() - 1); ;
       --i) {
    if (self.data()[i] == c)
      return i;
    if (i == 0)
      break;
  }
  return BasicStringPiece<STR>::npos;
}

对于字符串的反向查找本质的调用的STL的find_end()。而对于字符的反向查找是完全手写实现的。

另外StringPiece也支持std::string中的find_first_of()、find_first_not_of()、find_last_of()、find_last_not_of()。这里只展开一个：

size_t find_first_of(const StringPiece& self,
                     const StringPiece& s,
                     size_t pos) {
  if (self.size() == 0 || s.size() == 0)
    return StringPiece::npos;

  // Avoid the cost of BuildLookupTable() for a single-character search.
  if (s.size() == 1)
    return find(self, s.data()[0], pos);

  bool lookup[UCHAR_MAX + 1] = { false };
  BuildLookupTable(s, lookup);
  for (size_t i = pos; i < self.size(); ++i) {
    if (lookup[static_cast<unsigned char>(self.data()[i])]) {
      return i;
    }
  }
  return StringPiece::npos;
}

其中BuildLookupTable()主要是建了一张映射表：

inline void BuildLookupTable(const StringPiece& characters_wanted,
                             bool* table) {
  const size_t length = characters_wanted.length();
  const char* const data = characters_wanted.data();
  for (size_t i = 0; i < length; ++i) {
    table[static_cast<unsigned char>(data[i])] = true;
  }
}

映射表用数组实现，数组下标就是对应字符的数值，value是是否在StringPiece中出现过。后面就是普通的遍历find了。其他的其他函数实现也是类似。

截取子串

StringPiece也有substr函数可以截取子串，其返回值也是StringPiece。

StringPiece substr(const StringPiece& self,
                   size_t pos,
                   size_t n) {
  return substrT(self, pos, n);
}

template<typename STR>
BasicStringPiece<STR> substrT(const BasicStringPiece<STR>& self,
                              size_t pos,
                              size_t n) {
  if (pos > self.size()) pos = self.size();
  if (n > self.size() - pos) n = self.size() - pos;
  return BasicStringPiece<STR>(self.data() + pos, n);
}

也是常数时间复杂度，并没有产生字符串的拷贝，仅是重新计算了数据指针和长度，并构造了一个新对象。

返回string对象

 STRING_TYPE as_string() const {
    // std::string doesn't like to take a NULL pointer even with a 0 size.
    return empty() ? STRING_TYPE() : STRING_TYPE(data(), size());
  }

as_string()函数会构造出std::string类型的对象。这一步会有数据的拷贝。

从StringPiece到string_view

备胎转正

在各个C++开源项目提供了不同版本StringPiece的许多年以后，事情开始有了变化。C++14开始，string_view作为实验功能被进入到C++标准。<experimental/string_view>头文件中有std::experimental::string_view 这一新增的字符串视图类型。C++17 开始string_view顺利转正。头文件<string_view>纳入标准，std::string_view类型正式进入大家的视野。

https://en.cppreference.com/w/cpp/string/basic_string_view

从Piece到View，二者不完全相同，但也很像。有点hash_map和unordered_map的意味。StringPiece是string_view的前身。进入标准以后，string_view的API和前面我提到到Chromium版StringPiece的API有一些变化。

从Piece到View，二者不完全相同，但也很像。有点hash_map和unordered_map的意味。StringPiece是string_view的前身。进入标准以后，string_view的API和前面我提到到Chromium版StringPiece的API有一些变化。

API的差异

比如string_view没有assign()、clear() 以及as_string() 函数。访问函数增加了at()，和一般的string类似。

string_view有front()和back()，但没有front_or_0()、back_or_0()。并且front()和back()返回的是 constexpr const_reference。当string_view为空的时候，此时调用front()和back()是未定义行为（UB）！这点要注意。

C++20开始string_view加入了starts_with()和ends_with()。C++23中多了一个contains()可以用来查找一个const char*、string_view、char是否在当前string_view中，返回一个bool类型。而StringPiece中没有contains()。

最主要的是string_view在C++的语法层面，增加了一个运算符sv。

#include <string_view>
#include <iostream>
using namespace std::literals;
int main() {
    auto print = [](std::string_view sv) {
        std::cout << "size:" << sv.size() << std::endl;
        for (char c: sv) {
            std::cout << c << std::endl;
        }
        std::cout<<"----"<<std::endl;
    };

    std::string_view s1 = "abc\0\0def";
    std::string_view s2 = "abc\0\0def"sv;
    print(s1);
    print(s2);
    print(s1.substr(1, 5));
    print(s2.substr(1, 5));
}

输出：

size:3
a
b
c
----
size:8
a
b
c

d
e
f
----
size:2
b
c
----
size:5
b
c

d
----

在""双引号表达的C风格字符作为参数，且不指定长度来构造string_view对象的时候，其表现和StringPiece一致，会默认以'\0'结尾的字符作为string_view的有效字符串。而加了sv后缀以后则能将整个字符串视为有效字符串。

如果你没有C++14/17

好了，没有享受到C++14或17编译器的小伙伴们，可以使用boost库中的boost::string_view:

https://github.com/boostorg/utility/blob/master/include/boost/utility/string_view.hpp

boost::string_ref也可以用。但貌似后面会被弃用。另外abseil中也有一个stringview。

https://github.com/abseil/abseil-cpp/blob/master/absl/strings/string_view.h

当然为了你的项目兼容性（毕竟C++98还苟活于世！），你仍然可以继续沿用各种第三方轮子中的StringPiece，可以回头在看一下本文第一节，找到适合你的。

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8