std::string::size() 的实现方式是什么？

Question

cout << sizeof(std::string) << endl;

在我的64位机器上，结果为8，与sizeof(char*)相同，因此我认为string类只存储char*。那么，size函数是如何实现的呢？它是否使用strlen（因为它没有存储实际大小或指向结束字节的指针）？

在这个页面上，显示size函数具有恒定的时间复杂度，所以我很困惑。在另一个页面上，有人有更大的字符串大小。

我正在使用Fedora 64位上的GCC 4.7.1。

- SwiftMango

---

<string> 应该是仅有头文件的，所以你只需要看一下就可以了... - Oliver Charlesworth

你没有指定string是什么。你是指来自<string>的std::string吗？ - T Percival

可以想象，std::string 可以存储指向单个内存块的指针，该内存块包含其长度和实际字符。 - Igor Tandetnik

我在头文件中找到的唯一非静态成员是：mutable _Alloc_hider _M_dataplus;，而 _Alloc_hider 似乎只有一个 char* 成员。 - SwiftMango

@IgorTandetnik：或者（正如微软定义的BSTR一样）是指向实际字符的指针，前缀为它们的长度。即 *((size_t*)ptr - 1)。这意味着.size()需要一个固定的偏移量，而operator[]需要一个可变的偏移量，但是使用您的建议，operator[]需要两个偏移量。在x86上更昂贵，如果我没记错的话。 - MSalters

Answer 1

可能有许多解释。仅因为 std::string 恰好存储指针而不存储其他内容，并不意味着这一定是 char * 指向受控序列的指针。你为什么会得出这样的结论呢？

你的 std::string 可以很容易地变成一个 PImpl 风格的包装器，用于指向某个内部对象的指针，该对象存储所有内部数据，包括 char * 指针、长度和其他必要信息。这样，内部对象的大小可以任意大，而不会对 std::string 本身的大小产生任何影响。例如，为了方便快速引用计数复制，在某些实现中，std::string 可能类似于 std::shared_ptr 实现。也就是说，在这种情况下，std::string 实际上将变成类似于带有添加写时复制语义的 std::shared_ptr<std::string_impl>。

目标 "字符串实现" 对象甚至可以使用 "struct hack"-style 方法来存储实际的字符串，这意味着它可能不会存储 char * 指针，而是在其末尾将整个字符串嵌入其中。

- AnT stands with Russia

Answer 2

阅读 libstdc++ 的 doxygen 文档：

_CharT* _M_p; // The actual data

假设std::basic_string<char>，_M_p是指向实际数据的char*指针，这就是为什么你得到了8的原因。

它甚至说：

_M_p指向字符串中的第一个字符，您将其转换为指向_Rep的指针并减去1以获取指向标题的指针。

因此，在存储字符串数据的位置之前，它在一块内存中隐藏了指向实际表示（容量、长度等）的指针。

然后，有以下成员函数可用于访问表示：

Rep* _M_rep() const
{ return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

然后他们会这样调用 _M_rep()->_M_length; 来获取例如 size。

- Jesse Good

Answer 3

您认为std::string是char*的假设是错误的。这里是一种可能的实现之一，其中sizeof(std::string)==sizeof(char*)：

struct std::string
{
    string_implementation
    {
        size_t size;
        size_t buffer_size;
        char_traits whatever;
        char *buffer; // Here is your actual string!
    };

    string_implementation *ptr;
}

- Michael

Answer 4

std::string是std::basic_string<char>的typedef，而basic_string在我的机器上定义在文件/usr/include/c++/4.4/bits/basic_string.h 中。该文件有很多间接引用，但大致来说，std::string存储指向实际数据的指针。

// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
      struct _Alloc_hider : _Alloc
      {
    _Alloc_hider(_CharT* __dat, const _Alloc& __a)
    : _Alloc(__a), _M_p(__dat) { }

    _CharT* _M_p; // The actual data.
      };

这就是为什么您观察到了这样的行为。该指针可能会被转换为指向描述众所周知的字符串属性的结构体指针（位于实际数据之前）：

  struct _Rep_base
  {
size_type       _M_length;
size_type       _M_capacity;
_Atomic_word        _M_refcount;
  };

_Rep* _M_rep() const
      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

- 4pie0