这种std::string实现的优化是否被允许？

Question

这种std::string实现的优化是否被允许？

c++optimizationstandard-libraryproxy-object

7

我在思考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，那么库编写者改变成员函数的原型返回类型是否符合标准？或者更一般地说，在这些情况下，库编写者是否有余地返回“代理对象”而不是常规对象以进行优化？

我的直觉是不允许这样做，原型必须完全匹配。考虑到你不能仅仅因为返回类型不同而重载，这将不留余地给库编写者利用这些情况的空间。像我说的，我认为答案是不行的，但我想问一下:-)。

- Evan Teran

3

@Evan: 你可能想读一下《C++程序设计语言》 - 它提供了这个概念的实现。不过，这样的string_ref很容易失效，而且复制通常比较便宜，所以一般人都乐意将其复制到一个新的字符串中。当我实现这样一个类时，我倾向于使用const char*和size来实现，这使得它更具有普适性（例如，在内存映射文件，const char[]数据等上面覆盖）。如果你需要子字符串可以独立于源进行更改，则事情很快会变得复杂，特别是在多线程环境中... - Tony Delroy

@Tony：像 llvm::StringRef 这样的吗？ - Matthieu M.

@Martin York：我不知道有任何COW实现适用于原始字符串的子字符串。这并不意味着它们不存在，只是我没有见过。 - Evan Teran

@Tony：谢谢，我确实有一份副本，但不记得那个部分了，我得去查一下。 - Evan Teran

@Evan：实际上，由于多线程的原因，现在COW被认为是一个不好的想法。与同步访问共享缓冲区相关的开销很烦人。而且它并不像看起来那么迷人：许多方法授予对内部的访问（例如非const版本的operator[]、at），这实际上需要提前复制，即使它不会有用。 - Matthieu M.

显示剩余2条评论

6个回答

3

这是一种相对广泛使用的优化技术，被称为写时复制或COW。基本原理甚至与子字符串无关，而是与像这样简单的东西有关。

s1 = s2;

现在，这种优化的问题在于对于应该在支持多线程的目标上使用的C++库来说，字符串的引用计数必须使用原子操作进行访问（或更糟的是，在目标平台不提供原子操作的情况下使用互斥锁进行保护）。这足够昂贵，以至于在大多数情况下，简单的非COW字符串实现更快。

参见GOTW＃43-45：

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

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

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

更糟糕的是，使用了COW的库（例如GNU C++库）不能简单地回退到简单的实现，因为那样会破坏ABI。（不过，幸运的是，C++0x可以解决这个问题，因为它将需要进行ABI升级！ :) ）

- janneb

1

由于substr返回std::string，因此无法返回代理对象，也不能仅更改返回类型或对其进行重载（出于您提到的原因）。

他们可以通过使string本身能够成为另一个字符串的子字符串来实现这一点。这意味着所有用法都需要付出内存代价（以容纳额外的字符串和两个size_types）。此外，每个操作都需要检查它是否具有字符或是代理。也许可以使用实现指针来完成这项工作——问题是，现在我们正在为可能的边缘情况使一个通用类变慢。

如果您需要这样做，最好的方法是创建另一个类substring，该类从字符串、pos和length构造，并转换为字符串。您不能将其用作s1.substr(6)，但您可以执行以下操作：

 substring sub(s1, 6);

你还需要创建常见操作，以便使用子字符串和字符串而避免转换（因为这就是整个目的）。

- Lou Franco

0

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

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

这可能不能回答你的一般性解决方案问题。为此，你需要像@GMan建议的那样使用子字符串CoW。

- chrisaycock

0

你所谈论的是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正确性。

编辑：实际上，为了适应和，你可以使用一个可变的类型字段。初始设置为NULL，它可以每个实例都有，当调用或时初始化为指向一个新的数组的指针，并在析构函数中删除（如果非NULL）。

- Daniel Trebbien

0

只有在确实需要比std::string提供的性能更高时，才可以编写符合您需求的代码。我以前使用过字符串的变体。

我个人偏好使用不可变字符串而不是写时复制，并且仅在字符串实际长度超过16时使用boost::shared_ptr或等效项，因此字符串类还具有短字符串的私有缓冲区。

这意味着字符串类可能会带来一些负担。

我的收藏列表中还有一个“切片”类，它可以查看其他地方存在的类的“子集”，只要原始对象的生命周期保持完整。因此，在您的情况下，我可以将字符串切片以查看子字符串。当然，它不会以空字符结尾，也没有任何方法可以使其成为这样，除非进行复制。并且它不是一个字符串类。

- CashCow

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- GManNickG · Accepted Answer

这个想法是写时复制，但与其将整个缓冲区进行COW，你需要追踪缓冲区的哪个子集是“真实”的字符串。（在一些库的实现中，通常情况下会使用COW。）

因此，你根本不需要代理对象或更改接口，因为这些细节可以完全内部化。从概念上讲，你需要追踪四个东西：源缓冲区、缓冲区的引用计数以及该字符串在此缓冲区中的起始位置和结束位置。

每当操作修改缓冲区时，它都会创建自己的副本（从起始和结束定界符开始），将旧缓冲区的引用计数减少一，并将新缓冲区的引用计数设置为1。其他引用计数规则相同：复制并增加一个计数，析构一个字符串并减少一个计数，达到零并删除等等。 substr只是创建一个新的字符串实例，不过明确指定了起始和结束定界符。