c++ - 如何实现仅在堆栈上分配的字符串

Question

在大约十年前的一个项目中，我们发现std::vector动态分配会导致严重的性能消耗。在这种情况下，分配了许多小向量，因此快速的解决方案是编写一个类似向量的类，该类包装一个基于堆栈的预分配char数组，用作其容量的原始存储。结果是一个static_vector<typename T, std::size_t Max>. 如果你知道一些基础知识，这样的东西很容易写，而且你可以在网上找到不少这样的野兽。事实上，boost现在也有一个。

现在在嵌入式平台上工作，我们碰巧需要一个static_basic_string. 那将是一个字符串，它在堆栈上预先分配固定的最大内存量并将其用作其容量。

起初我认为这应该相当容易（static_vector毕竟它可以基于现有std::basic_string的 . 它比std::vector's 接口复杂得多。尤其是实现附带的find()功能系列std::basic_string不仅仅是一项乏味的任务。

这让我再次思考。毕竟，这是创建分配器的目的：根据其他方式new替换分配。delete然而，说分配器接口笨拙是轻描淡写的。有几篇文章对此进行了解释，但我在过去 15 年中看到如此之少的本土分配器是有原因的。

所以这是我的问题：

如果你必须实现一个basic_string相似的，你会怎么做？

自己写static_basic_string？
写一个分配器传递给std::basic_string?
做一些我没有想到的事情？
使用我不知道的 boost 中的东西？

^{与往常一样，对我们来说有一个相当重要的限制：在嵌入式平台上，我们绑定到 GCC 4.1.2，所以我们只能使用 C++03、TR1 和 boost 1.52。}

score 4 · Accepted Answer

第一个问题是：你使用了多少额外的接口？的大多数std::string附加接口都可以使用<algorithm>（例如 std::find，std::find_if和std::search）中的函数轻松实现，并且在很多情况下，其中有很大一部分无论如何都不会使用。只需根据需要实施即可。

我认为您无法使用自定义分配器来完成这项工作。将内存“放在堆栈上”的唯一方法是将其声明为自定义分配器的成员，这会在复制它们时产生各种问题。并且分配器必须是可复制的，并且副本必须是幂等的。

也许你可以在网上找到一个免费的实现， std::string它使用小字符串实现；然后修改它，使截止大小（超出它使用动态分配）大于您实际使用的任何字符串。（有几个可用的标准库的开源实现；随 g++ 提供的那个仍然使用 COW，但我怀疑其他大多数都使用 SSO。）

score 1 · Accepted Answer

有很多basic_string实现，有些完全基于动态分配，有些基于动态分配，仅适用于大于给定长度的字符串（实际上，它们在适合时使用自己的内部缓冲区）。

使用分配器可能不是要走的路，因为字符串和分配器之间的接口假定分配器对象是容器的一部分，但分配的内存来自容器本身之外。您可以通过使用 POSIX 实现分配器来安排它alloca，但有所有缺点。

在堆栈上实现字符串时的问题是你不能让它动态增长（可能是当时的堆栈有更多的东西）但是你还必须注意这样的操作+=可以使字符串越来越长。

因此，您最终会预先分配（作为数组或作为 alloca 提供的缓冲区，在您的类中或在分配器中不会改变问题）您将主要浪费的字节数量，但不会全部填充，或者不使用如果字符串增长过多并且需要动态，则使用它们。

内存到缓存的通信过程（通常以 128 字节或 4KBytes 运行）可能需要权衡取舍，但它强烈依赖于硬件，因此很可能不会支付复杂性。

一个更实惠的解决方案可以是仍然在堆上分配的分配器，但能够保留和重用返回的块（达到一定限制），从而减少要求系统分配/解除分配的需要。

new/delete但是，在这种情况下，如果底层系统已经以这种方式实现，性能可能不一定会受益。

score 1 · Accepted Answer

一个很好的起点是Alexandrescu 的基于策略的字符串类，在 Dobbs 博士的这篇文章中进行了描述。它包括一个 SSO 策略，基本上可以满足您的需求（在页面中搜索SmallStringOpt），并且在您认为必要时可以轻松修改。它早于 C++11，所以你也可以。

score 1 · Accepted Answer

很简单，写一个栈分配器，下面是一个例子：

https://codereview.stackexchange.com/questions/31528/a-working-stack-allocator

使用分配器，您可以很容易地分配，例如，从内存映射文件，即从磁盘驱动器，或从chars 的静态数组。

score 1 · Accepted Answer

LLVM ADT 有SmallString类。它还有SmallVector许多其他有用的类。

虽然当前的 LLVM 代码库转向使用 C++11，但（不那么）旧版本的 LLVM 支持 C++03。

score 0 · Accepted Answer

0

我应该结合使用实现定义的 VLA 和标准算法。

于 2014-10-14T09:46:46.590 回答

score -1 · Accepted Answer

这是一个工作代码，但不是推荐的方式。

这段代码有很多痕迹来显示它在做什么。它不检查分配请求的大小是否不超过缓冲区。如有必要，您可以进行此项检查。请注意，std::basic_string 会尝试分配不必要的资源。

#include <string>
#include <iostream>

template<typename T, size_t S>
class fixed_allocator
{
  typedef std::allocator<T> _base;

  std::ostream& trace() const { return std::cerr << "TRACE fixed_allocator " << (void*)this ; }

public:
  typedef typename _base::value_type value_type;
  typedef typename _base::pointer pointer;
  typedef typename _base::const_pointer const_pointer;
  typedef typename _base::reference reference;
  typedef typename _base::const_reference const_reference;
  typedef typename _base::size_type size_type;
  typedef typename _base::difference_type difference_type;

  template<class C> struct rebind {
    typedef fixed_allocator<C, S*sizeof(C)/sizeof(T)> other;
  };
  T* buffer_;

  fixed_allocator(T* b) : buffer_(b) { trace() << "ctor: p="  << (void*)b << std::endl; }

  fixed_allocator() : buffer_(0) { trace() << "ctor: NULL" << std::endl; };
  fixed_allocator(const fixed_allocator &that) : buffer_(that.buffer_) { trace() << "ctor: copy " << (void*)buffer_ << " from " << (void*) &that << std::endl; };

  pointer allocate(size_type n, std::allocator<void>::const_pointer hint=0) {
    trace() << "allocating on stack " << n << " bytes" << std::endl;
    return buffer_;
  }

  bool operator==(const fixed_allocator& that) const { return that.buffer_ == buffer_; }
  void deallocate(pointer p, size_type n) {/*do nothing*/}
  size_type max_size() const throw() { return S; }
};

int main()
{
  char buffer_[256];
  fixed_allocator<char, 256> ator(buffer_);
  std::basic_string<char, std::char_traits<char>, fixed_allocator<char, 256> > str(ator);
  str.assign("ipsum lorem");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  std::cout << " has 'l' at " << str.find("l") << std::endl;
  str.append(" dolor sit amet");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  str.insert(0, "I say, ");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  str.insert(7, "again and again and again, ");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  str.append(": again and again and again, ");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  return 0;
}

此代码已在 GCC 和 LLVM 上进行了测试，并按预期（或意外）执行。

语法笨拙。无法从 basic_string 派生并嵌入缓冲区。更好的方法是使用所需的 basic_string 接口子集创建一个小的专用 buffer_string 类。

c++ - 如何实现仅在堆栈上分配的字符串

7 回答 7

Related

Reference