7

Scott Meyer 在“Effective STL”中说，在决定使用哪种数据结构时要考虑的一件事是容器是否使用引用计数。他说这种方法存在一些行为异常。

其中一些是什么？为什么像“string”和“rope”这样的容器会有异常行为？

4

4 回答 4

3

正如其他人所说，典型的例子是std::string。除了多线程程序中的锁定性能问题外，引用计数字符串还存在无线程问题。想象一下：

string s = "hello";
string t = s;                   // s and t share data
char &c = t[0];                 // copy made here, since t is non-const

问题是非常量operator[]必须复制字符串，如果它是共享的，因为返回的引用可以稍后用于修改字符串（您可以将其分配给 non-reference char，但operator[]不知道它应该表现有什么不同）。另一方面，const operator[]应该避免复制，因为这将消除引用计数的所有好处（这意味着您在实践中总是复制）。

const char &get_first(const string &s) {
    return s[0];                // no copy, s is const
}

string s = "hello";
string t = s;                   // s and t share data
const char &c1 = get_first(t);  // no copy made here
const char &c2 = t[0];          // copy made, since t is non-const
// c1 just got invalidated (in fact, it's pointing at s[0], not t[0]).
s[0] = 'X';
printf("%c, %c\n", c1, c2);     // outputs "X, h"

如您所见，这种区别令人困惑，可能会导致非常意外的行为。

这是一篇关于写时复制语义及其对性能影响的旧文章：http ://www.gotw.ca/gotw/045.htm 。

std::string这是在 C++11 标准中不计入引用的动机的提案： http ://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2534.html 。这就是上面例子的基础。

于 2012-09-27T09:00:47.120 回答
1

作为一般规则，引用计数会遇到竞争条件、死锁或过度同步等常见的多线程问题，以避免任何一种情况。

然后你会遇到上下文问题，这通常需要类似闭包的行为，即对象可能需要在它们明显超出范围后被捕获，但这可能会被 STL 避免，我不是 STL 专家。

这里有一个讨论，讨论了与智能指针相关的各种巴洛克式边缘情况：http ://www.velocityreviews.com/forums/t689414-c-primer-4th-edition-reference-counting-smart-pointers.html

于 2012-09-22T08:03:56.497 回答
1

作为示例，引用计数字符串可能发生的一个异常，特别是具有“子部分”处理（带有开始/结束切片）的字符串，是“不幸的锁定”。

假设您为文件的整个文本分配内存。然后你解析你的文件并使用一些“slice()”、“left()”、“mid()”或等效方法。您可能会结束锁定文件的整个字符串，而其中可能只有很小的一部分包含实际的文本数据（其余部分是已经解析的数字、标点符号或其他）。因此，您最终可能使用了比必要更多的内存，同时更容易控制峰值使用量。在这种情况下，如果您使用多线程并在各个线程中密集使用某些字符串，则可能会出现第二个问题：不必要的内存争用，字符串的引用计数可能会一直递增/递减，原子性可能会变得 int道路，

但是，只要您知道应用程序中的潜在问题并阻止它们（在这种情况下，只需通过复制它们来“单独”制作字符串），就没有什么反对引用计数的。

于 2012-08-30T14:32:12.007 回答
1

在第 13 项中，Meyers 详细阐述了多线程和引用字符串的问题。

它在很大程度上取决于确切的实现std::string和锁定以及使用模式。 如果在多线程环境中明显无害地使用 a 会因为隐藏锁而导致延迟，
这可能是一个问题。std::string循环中这种锁和上下文切换的代价可能是巨大的。但它绝不应该导致死锁。
这不一定是个问题。这本书是> 10岁。与此同时，线程实现也得到了改进。例如，Linux-Futex 在大多数情况下表现得更加流畅。

另一点：（我不知道迈耶斯是否也讨论过这个……）
引用计数std::string意味着它具有写时复制语义。这通常是一件好事。实际副本被推迟到实际需要时。但这也意味着复制品的价格必须在一个可能难以预测的点上支付。

于 2012-09-25T08:56:42.980 回答