Выделяйте постоянные строки в контейнере непрерывно

Question

Допустим, у меня есть std::vector из const std::string с.

std::vector<const std::string> strs;

Теперь поведение по умолчанию здесь состоит в том, что фактические строковые контейнеры могут быть размещены в любом месте кучи, что в значительной степени отключает любыепредварительная выборка данных при итерации по содержащимся строкам.

strs.push_back("Foo"); // allocates char block on heap
strs.push_back("Boo"); // allocates char block on heap

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

Есть ли способ достичь этого поведения?

Answer 1

Вам нужен пользовательский распределитель, известный как распределитель области памяти.Вы можете посмотреть википедию или гугл для получения дополнительной информации, но основная идея - это что-то вроде аппаратного стека - выделите один большой блок, а затем просто увеличьте указатель, чтобы пометить его как использованный.Он может очень быстро обслуживать множество смежных запросов, но не может обрабатывать освобождения и распределения - все освобождение выполняется сразу.

Answer 2

Пользовательский распределитель - это хорошо, но почему бы не сохранить все строки в одном std::vector<char> или std::string и не получить доступ к исходным строкам по смещению?

Просто и эффективно.

Answer 3

Не совсем.

std::string не является POD, оно не хранит свое содержимое "внутри объекта". Более того - даже не требуется хранить его содержимое в одном блоке памяти.

Также для std::vector (как и для всех массивов) необходимо, чтобы его содержимое было одного типа (= одинакового размера), поэтому вы не можете создать буквальный «массив» строк различной длины.

Ваш лучший снимок - взять длину и использовать std::vector<std::array<char, N> >

Если вам нужны действительно разные длины, альтернативой является просто std::vector<char> для данных плюс std::vector<unsigned> для индексов, где начинаются последовательные строки.

---

Свернуть свой собственный распределитель для строки - заманчивая идея, вы можете основать его на std::vector<char>, а затем свернуть на нем свой собственный std::basic_string, а затем собрать их.

Обратите внимание, что вы на самом деле сильно зависите от конкретной реализации std::string. Некоторые из них имеют внутренний буфер из N символов и выделяют память только снаружи, если длина строки больше, чем у буфера. Если это так в вашей реализации, вы все равно не получите непрерывную память для всего буфера строк.

Исходя из этого, я заключаю, что с std::string вы, как правило, не сможете выполнить то, что хотите (если вы не полагаетесь на конкретную реализацию STL), и вам нужно предоставить другую строковую реализацию, соответствующую вашим потребностям.

Answer 4

Если это действительно так просто - выдвигать строки, которые никогда не изменятся, легко написать свой собственный распределитель. Выделите большой блок памяти, установите указатель free на смещение 0 в блоке. Если вам нужно хранилище для новой строки strncpy, то до free и увеличения free с помощью strlen. Следите за концом блока памяти и выделяйте другой блок при необходимости.

Answer 5

Вектор гарантированно является непрерывной памятью и совместим с массивом.Это не односвязный список.

"Смежность на самом деле является частью векторной абстракции. Это так важно, что в стандарт C ++ 03 были внесены поправки для явного добавления гарантии."

Источник: http://herbsutter.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/

Используйте reserve(), чтобы заставить его быть непрерывным и не перераспределять.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main()
{
    // create empty vector for strings
    vector<const string> sentence;

    // reserve memory for five elements to avoid reallocation
    sentence.reserve(5);

    // append some elements
    sentence.push_back("Hello,");
    sentence.push_back("how");
    sentence.push_back("are");
    sentence.push_back("you");
    sentence.push_back("?");

    // print elements separated with spaces
    copy (sentence.begin(), sentence.end(),
          ostream_iterator<string>(cout," "));
    cout << endl;

return 0;
}

Answer 6

Вы всегда можете написать частный распределитель (второй параметр шаблона для std::vector), который будет выделять все строки из непрерывного пула. Также вы можете использовать std::basic_string вместо std::string (что является частным случаем std::basic_string), что позволяет аналогично указывать свой собственный распределитель. В общем, я бы сказал, что это случай «преждевременной оптимизации», но я надеюсь, что вы измерили и увидели здесь снижение производительности ... Я думаю, что цена за это будет потрачена впустую.