在实现std ::字符串的实现时，是否允许这种优化？

StackOverflow https://stackoverflow.com/questions/4682603

题

我只是在考虑实施 std::string::substr. 。它返回新的 std::string 对象，这对我来说似乎有些浪费。为什么不返回一个引用原始字符串内容的对象，可以隐式分配给一个 std::string？对实际复制的一种懒惰评估。这样的班级看起来像这样：

template <class Ch, class Tr, class A>
class string_ref {
public:
    // not important yet, but *looks* like basic_string's for the most part

private:
    const basic_string<Ch, Tr, A> &s_;
    const size_type pos_;
    const size_type len_;    
};

该类的公共界面将模仿真实的所有仅阅读操作 std::string, ，因此用法将是无缝的。 std::string 然后可以有一个新的构造函数 string_ref 因此，用户永远不会更明智。当您尝试“存储”结果时，您最终会创建一个副本，因此指向数据的引用并将其修改后的后面没有真正的问题。

这样的想法是这样的代码：

std::string s1 = "hello world";
std::string s2 = "world";
if(s1.substr(6) == s2) {
    std::cout << "match!" << std::endl;
}

不超过2 std::string 总共构造的对象。这似乎是对执行许多字符串操作的代码的有用优化。当然，这不仅适用于 std::string, ，但是任何可以返回其内容子集的类型。

据我所知，没有实施这样做。

我想问题的核心是：

给定一个可以隐式转换为一个的类 std::string 根据需要，是否符合图书馆作者更改会员的原型以返回类型的标准？或更一般而言，图书馆作者是否有余地返回“代理对象”而不是在这些类型的情况下作为优化的常规对象？

我的直觉是不允许这样做，原型必须完全匹配。鉴于您不能单独使用返回类型过载，因此图书馆作家没有空间来利用这些类型的情况。就像我说的那样，我认为答案是否定的，但我想我会问:-)。

有帮助吗？

解决方案

这个想法是 抄写, ，但是，您不必屈服整个缓冲区，而是跟踪缓冲区的哪个子集是“真实”字符串。 （以正常形式的母牛在某些库实现中使用。）

因此，您根本不需要代理对象或界面的更改，因为这些详细信息可以完全内部。从概念上讲，您需要跟踪四件事：源缓冲区，缓冲区的参考计数以及该缓冲区内字符串的开始和末端。

每当操作完全修改缓冲区时，它都会创建自己的副本（从开始和结束定界符），将旧缓冲区的参考计数减少一个，并将新缓冲区的参考计数设置为一个。参考计数规则的其余部分是相同的：复制和增加计数，破坏字符串并减少计数，达到零并删除，等等。

substr 只是制作一个新的字符串实例，除了明确指定的开始和结束定界符外。

其他提示

这是一个非常众所周知的优化，相对广泛使用，称为折线或牛。基本的事情甚至与子字符串无关，而是与

s1 = s2;

现在，此优化的问题是，对于应该用于支持多个线程的目标的C ++库，必须使用原子操作访问字符串的参考计数（或更糟糕的是，在目标平台的情况下受到MUTEX的保护不提供原子操作）。这足够昂贵，在大多数情况下，简单的非牛字符串实现速度更快。

请参阅GOTW＃43-45：

http://www.gotw.ca/gotw/043.htm

http://www.gotw.ca/gotw/044.htm

http://www.gotw.ca/gotw/045.htm

更糟糕的是，使用牛的库，例如GNU C ++库，不能简单地恢复到简单的实现，因为那会破坏ABI。 （虽然，c ++ 0x的营救，因为无论如何都需要一个ABI颠簸！:)）

自从 substr 返回 std::string, ，没有办法返回代理对象，他们不能仅仅更改其上的返回类型或过载（出于您提到的原因）。

他们可以通过制作 string 本身能够成为另一个字符串的子。这将意味着所有用法的内存惩罚（要容纳一个额外的字符串和两个size_types）。另外，每个操作都需要检查其是否具有字符还是代理。也许这可以通过实施指针来完成 - 问题是，现在我们为可能的边缘情况降低了通用类。

如果需要的话，最好的方法是创建另一个类， substring, ，从字符串，POS和长度以及秘密到字符串构造。你不能用作 s1.substr(6), ，但是你可以做 

 substring sub(s1, 6);

您还需要创建共同的操作，以避免转换（因为这是全部）。

关于您的具体示例，这对我有用：

if (&s1[6] == s2) {
    std::cout << "match!" << std::endl;
}

对于通用解决方案，这可能无法回答您的问题。为此，如@Gman所建议的那样，您需要子弦牛。

您所说的是（或）Java的核心特征之一 java.lang.String 班级 （http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/）。在许多方面，Java的设计 String 班级和C ++的 basic_string 模板是相似的，所以我想编写 basic_string 使用此“基因优化”的模板是可能的。

您需要考虑的一件事是如何编写实施 c_str() const 成员。根据字符串作为另一个子字符串的位置，它可能必须创建一个新副本。如果请求C_ST的字符串不是尾随的子字符串，则绝对必须创建内部数组的新副本。我认为这需要使用 mutable 关键字在大多数（如果不是全部）的数据成员中 basic_string 实施，极大地使实施其他 const 方法是因为编译器不再能够以正确性为程序员提供帮助。

编辑： 实际上，为了容纳 c_str() const 和 data() const, ，您可以使用单个可变类型的字段 const charT*. 。最初设置为 NULL, ，它可能是每一步，初始化为新的指针 charT 随时随地 c_str() const 或者 data() const 被称为，并在 basic_string 如果非 -NULL.

如果并且仅当您确实需要比STD :: String提供更多的性能时，请继续写一些可以按照您需要的方式来编写的东西。我以前曾与Strings的变体合作过。

我自己的偏爱是使用不可用的字符串而不是编写纸条，并使用boost :: shared_ptr或等效的字符串，但仅当字符串实际上实际上超过16范围时，因此字符串类也有一个私人缓冲区，用于简短字符串。

这确实意味着字符串类可能会带来一些重量。

我在收藏列表中也有一个“切片”类，可以查看一个类的“子集”，只要原始对象的寿命完好无损。因此，在您的情况下，我可以切成薄片以查看子字符串。当然，它不会终止终止，也没有任何方法可以在不复制它的情况下进行此类制作。它不是字符串类。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top