9

我需要一个“字符串池”对象，我可以在其中重复插入一个“字符序列”（我使用这个短语来表示“字符串”，而不会将其与 std::string 或 C 字符串混淆），获取指向该序列的指针，并保证如果/当池需要增长时指针不会失效。使用简单std::string的 as 池将不起作用，因为当字符串超出其初始容量时可能会重新分配字符串，从而使所有先前指向它的指针无效。

池不会无限制地增长——有明确定义的点，我将在其clear()上调用方法——但我也不想在其上保留任何最大容量。它应该能够生长，无需移动。

我正在考虑的一种可能性是将每个新的字符序列插入 aforward_list<string>并获取begin()->c_str(). 另一个是插入到 中unordered_set<string>，但我很难找出当 unordered_set 必须增长时会发生什么。我正在考虑的第三种可能性（不太热情）是滚动我自己的 1K 缓冲区链，我将字符序列连接到其中。这具有（我猜）具有最高性能的优势，这是该项目的要求。

我很想听听其他人会如何建议解决这个问题。

更新 1：编辑以澄清我对短语“字符序列”的使用等同于“字符串”的一般概念，而不暗示 std::string 或以空字符结尾的字符数组。

4

3 回答 3

12

我过去使用过这种方法：

using Atom = const char*;

Atom make_atom(string const& value)
{
    static set<string> interned;
    return interned.insert(value).first->c_str();
}

显然，如果您想/需要清除该集合，则可以使其在更广泛的范围内可用。

为了提高效率，将字符串移动/放置到集合中。

更新为了完整性，我添加了这种方法。在 Coliru 上看到它

#include <string>
#include <set>
using namespace std;

using Atom = const char*;

template <typename... Args>
typename enable_if<
    is_constructible<string, Args...>::value, Atom
>::type emplace_atom(Args&&... args)
{
    static set<string> interned;
    return interned.emplace(forward<Args>(args)...).first->c_str();
}

#include <iostream>

int main() {
    cout << emplace_atom("Hello World\n");
    cout << emplace_atom(80, '=');
}
于 2014-01-06T23:24:11.343 回答
1

是的，你将不得不写一个缓冲区列表。不，不要自己做所有的艰苦工作。

底层数据结构应该是一个std::vector<std::string>. 使用（转发）列表不会给你带来很多好处。当向量被调整大小时，字符串被有效地移动。 std::forward_list<std::string>. 即使调整了列表的大小，字符串本身也会保留在原位。仅 a 需要迭代列表，.clear因此列表性能并不重要。

包装类应该抽象出新字符串的添加。当最后一个字符串的容量不足以添加新字符串时，应添加新字符串。当您添加一个新字符串时，reserve一个块将需要的所有内存 - 这确保容量足够大以防止以后重新分配。

当大的新分配强制使用新块时，此设置可能会浪费一些空间，从而使旧块的一部分未使用。您当然可以记住最后 N 个块中剩余的大小，因为 N 的值很小，这样这些块可能仍在缓存中。但是很有可能在您的应用程序中 N=5 已经太大了。

于 2014-01-06T23:15:27.223 回答
0

回顾一下，您的要求是：

  • 能够推送元素
  • 能够获取到序列开头的迭代器
  • 如果序列增长，迭代器不应失效
  • 能够clear按顺序
  • 不要预留最大容量

这似乎std::list<char>完全符合这个要求列表。当然，您可能需要对类进行包装以使其行为与 完全一样std::string，但这实际上取决于您如何操作数据。

以下是它符合要求的程度：

  • 要推送元素，您可以使用push_back和emplace_back成员函数。

  • std::begin(container)或者成员函数begin将检索到序列的第一个元素的迭代器。

  • 在列表中或跨多个列表添加、删除和移动元素不会使迭代器无效。只有当相应的元素被删除时，迭代器才会失效。

  • 要清除序列，您可以使用成员函数clear。

  • 大多数情况下，它是作为双向链表实现的，因此不保留任何容量。

由于std::list 似乎内存效率低下（即使标准没有指定它的大小也没有指定它的实现），所以添加您也可以使用std::deque<char>与上述几乎相同的接口是正确的。唯一的区别是std::deque可能会保留未使用的内存。

于 2014-01-05T20:53:09.863 回答