Реализация & quot; пула строк & quot; это гарантированно не двигаться

Question

Реализация & quot; пула строк & quot; это гарантированно не двигаться

Мне нужен объект «пул строк», в который я могу многократно вставлять «последовательность символов» (я использую эту фразу для обозначения «строка», не путая ее с std :: string или строкой C), получить указатель на последовательность и быть уверенным, что указатель не станет недействительным, если / когда необходимо увеличить пул. Используя простой std::string поскольку пул не будет работать, из-за возможности перераспределения строки, когда она превосходит свою первоначальную емкость, тем самым аннулируя в ней все предыдущие указатели.

Пул не будет расти без границ — есть четко определенные точки, в которых я буду называть clear() метод на это — но я не хочу резервировать максимальную емкость на нем, либо. Он должен быть в состоянии расти, не двигаясь.

Одна из возможностей, которую я рассматриваю, — вставить каждую новую последовательность символов в forward_list<string> и получение begin()->c_str(), Другой вставляет в unordered_set<string>, но мне трудно выяснить, что происходит, когда unordered_set должен расти. Третья возможность, которую я рассматриваю (с меньшим энтузиазмом), — это свертывание собственной цепочки буферов 1К, в которую я объединяю последовательность символов. Это имеет преимущество (я полагаю), имея самую высокую производительность, которая является требованием для этого проекта.

Мне было бы интересно услышать, как другие рекомендуют подходить к этому.

ОБНОВЛЕНИЕ 1: отредактировано для пояснения моего использования фразы «последовательность символов», чтобы быть эквивалентным общему понятию «строка» без указания либо std :: string, либо массива char с нулевым символом в конце.

9

c++c++-standard-library string string-pool

Решение

Другие решения

Да, вам придется написать список буферов. Нет, не делай всю тяжелую работу самостоятельно.

Основная структура данных должна быть std::vector<std::string>, Использование (пересылки) списка не приносит вам большой выгоды. При изменении размера вектора строки перемещаются эффективно. std::forward_list<std::string>, Даже если размер списка изменяется, сами строки остаются на месте. Перебор списка необходим только для .clear так что производительность списка не критична.

Класс-обертка должен абстрагироваться от добавления новых строк. Новая строка должна быть добавлена, когда емкости последней строки недостаточно для добавления новой строки. Когда вы добавляете новую строку, reserve вся память, которая потребуется блоку — это гарантирует, что емкость будет достаточно большой для предотвращения перераспределения в дальнейшем.

Эта настройка может тратить некоторое пространство, когда большое новое выделение вынуждает использовать новый чанк, оставляя часть старого чанка неиспользованной. Вы, конечно, можете помнить размер, оставшийся в последних N блоках, для небольшого значения N, такого, что эти куски могут все еще находиться в кэше. Но вполне возможно, что в вашем приложении N = 5 уже будет слишком большим.

1

Подводя итоги, ваши требования:

Уметь толкать элементы
Уметь получить итератор к началу последовательности
Итераторы не должны становиться недействительными, если последовательность увеличивается
Быть способным clear последовательность
Не резервируйте максимальную вместимость

Кажется, что std::list<char> отлично вписывается в этот список требований. Конечно, вам может понадобиться обертка вокруг класса, чтобы он вел себя так же, как std::string, но это действительно зависит от того, как вы манипулируете данными.

И вот как хорошо это соответствует требованиям:

Чтобы подтолкнуть элементы, вы можете использовать push_back а также emplace_back функции-члены.
std::begin(container) или функция-член begin извлечет итератор к первому элементу последовательности.
Добавление, удаление и перемещение элементов в списке или в нескольких списках не делает недействительными итераторы. Итератор становится недействительным только при удалении соответствующего элемента.
Чтобы очистить последовательность вы можете использовать функцию-член clear,
В большинстве случаев он реализован в виде двусвязного списка, поэтому емкость не зарезервирована.

поскольку std::list кажется неэффективная память (хотя стандарт не определяет ни ее размер, ни ее реализацию), правильно добавить, что вы также можете использовать std::deque<char> с почти тот же интерфейс, что и выше. Единственная разница в том, что std::deque может зарезервировать неиспользованную память

0

Источник

Accepted Answer

Я использовал этот подход в прошлом:

using Atom = const char*;

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

Очевидно, что если вы хотите / должны очистить набор, вы сделаете его доступным в более широкой области.

Для еще большей эффективности перемещайте / вставляйте струны в набор.

Обновить Я добавил этот подход для полноты. Видеть это Жить на Колиру

#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, '=');
}

8