Nano Hash - криптовалюты, майнинг, программирование

std :: string без выделения свободной памяти для хранилища

У меня вопрос очень похож на

Как выделить std :: строка в стеке с использованием строковой реализации glibc?

но думаю стоит спросить еще раз.

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

std::basic_string<
char, 
std::char_traits<char>, 
inline_allocator<char, 10> 
> 
x("test");

Я попытался написать класс inline_allocator, который работал бы так, как вы ожидаете: он резервирует 10 байтов для хранения, а если basic_string требуется более 10 байтов, он вызывает ::operator new(). Я не мог заставить его работать. В ходе выполнения указанной выше строки кода моя стандартная строковая библиотека GCC 4.5 вызывает конструктор копирования inline_allocator 4 раза. Мне не ясно, есть ли разумный способ написать конструктор копирования для inline_allocator.

В другом потоке StackOverflow Эрик Мельски предоставил эту ссылку на класс в Chromium:

http://src.chromium.org/svn/trunk/src/base/stack_container.h

что интересно, но это не прямая замена для std::string, потому что он оборачивает std::basic_string в контейнер, так что вам нужно вызвать перегруженный operator->(), чтобы получить std::basic_string.

Я не могу найти других решений этой проблемы. Может быть, нет хорошего решения? И если это правда, то являются ли концепции std::basic_string и std::allocator сильно ошибочными? Я имею в виду, похоже, что это должен быть очень простой и простой вариант использования для std::basic_string и std::allocator. Я полагаю, что концепция std::allocator предназначена в первую очередь для бассейнов, но я думаю, что она также должна охватывать и это.

Похоже, что семантика перемещения rvalue-reference в C ++ 0x может позволить записать inline_allocator, если строковая библиотека переписана так, что basic_string использует конструктор перемещения своего распределителя вместо конструктора копирования. Кто-нибудь знает, каковы перспективы такого исхода?

Мое приложение должно создавать миллион крошечных строк ASCII в секунду, поэтому в итоге я написал свой собственный класс строк фиксированной длины на основе Boost.Array, который отлично работает, но меня это все еще беспокоит.

c++ memory-management c++11 stdstring
30.03.2011

  • Как человек, который в прошлом боролся с кастомными распределителями, мне очень интересно услышать, как авторитетные источники говорят на эту тему. 31.03.2011
  • +1 для бесплатного магазина. Да, и потому что это хороший вопрос. 31.03.2011
  • Ссылка на Generic: основанная на политике реализация basic_string - это потрясающее обсуждение хранилища basic_string. Я все еще задаюсь вопросом, можно ли написать класс inline_allocator в моем вопросе. Беглый взгляд на статью Александресу не дает мне ответа, мне придется потратить некоторое время на это. 31.03.2011
  • Ссылка на stack_container.h Chromium мертва. Вот обновленный: src.chromium .org / viewvc / chrome / trunk / src / base / container /. 01.08.2013

Ответы:


1

Андрей Александреску, выдающийся программист на C ++, написавший «Современный дизайн C ++», однажды написал отличную статью о создании различных строковых реализаций с настраиваемыми системами хранения. В его статье (ссылка здесь) описывается, как вы можете делать то, что вы описали выше, как частный случай гораздо более общей системы, которая может обрабатывать всевозможные умные требования к распределению памяти. Здесь не так много говорится о std::string и больше внимания уделяется полностью настраиваемому строковому классу, но вы, возможно, захотите изучить его, поскольку в реализации есть некоторые настоящие жемчужины.

30.03.2011
  • Это отличная статья Александреску, спасибо. Это очень хороший ответ на вопрос, как настроить хранилище для basic_string. 31.03.2011

    • 2

    C ++ 2011 действительно поможет вам в этом :)

    Дело в том, что концепция allocator в C ++ 03 была искалечена. Одно из требований заключалось в том, что распределитель типа A должен иметь возможность освобождать память от любого другого распределителя типа _3 _... К сожалению, это требование также противоречит распределителям с отслеживанием состояния, каждый из которых подключен к своему собственному пулу.

    Ховард Хиннант (который управляет подгруппой STL комитета C ++ и реализует новый STL с нуля для C ++ 0x) исследовал стековые распределители на его веб-сайте, из которых вы можете почерпнуть вдохновение.

    31.03.2011
  • Это очень интересно. Я посмотрел на класс Хиннанта stack_alloc, и он отлично работает для std::vector, но, увы, не для std::basic_string. Я считаю, что проблема снова в том, как std::basic_string использует stack_alloc конструктор копирования. 31.03.2011
  • И я думаю, что разрешено использовать конструктор копирования таким образом из-за требования, которое вы описали. 31.03.2011
  • @James: да, к сожалению, поскольку стандарт почти подразумевает, что распределители не имеют состояния (или, по крайней мере, все распределители одного типа каким-то образом более или менее разделяют одно и то же состояние), копии вполне разрешены. 31.03.2011

    • 3

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

    Например, вот соответствующая часть sso_string_base.h, которая является частью MinGW:

      enum { _S_local_capacity = 15 };

  union
  {
_CharT           _M_local_data[_S_local_capacity + 1];
size_type        _M_allocated_capacity;
  };

    Член _M_local_data является релевантным - пространство для хранения (до) 15 символов (плюс терминатор NUL) без выделения места в куче.

    Если память не изменяет, библиотека Dinkumware, включенная в VC ++, выделяет место для 20 символов, хотя я давно не смотрел, поэтому я не могу на это поклясться (а отслеживание большей части чего-либо в их заголовках, как правило, затруднительно, поэтому Я предпочитаю избегать поиска, если могу).

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

    30.03.2011
  • VC ++ выделяет 16 байтов для SSO, что, на мой взгляд, слишком мало, чтобы быть в целом полезным, поскольку std::wstring чаще используется в коде Windows, чем std::string, и это позволяет использовать только 8 символов в std::wstring (или 7, если .c_str() используется часто). 31.03.2011
  • Разве заголовок не принадлежит расширениям библиотеки MinGW (не является частью std :: string)? 31.03.2011
  • @UncleBens: Я так не думал, но могу ошибаться. Существуют также альтернативы (например, STLPort, libc ++), которые определенно используют SSO в своих реализациях std::string. 31.03.2011
  • @ildjarn: Посмотрев еще раз, вы совершенно правы, и я согласен, что это немного маловато. Я все же думаю, что было бы проще изменить его и перекомпилировать стандартную библиотеку, чем пытаться взломать ее потом. 31.03.2011
  • Ах, спасибо за краткосрочную оптимизацию строки. Мне нужно иметь возможность контролировать пороговую длину оптимизации короткой строки. И я не шучу насчет миллиона построений струн в секунду. 31.03.2011
  • @ Джеймс Брок: Конечно - и я никогда не сомневался в этом. Что касается управления порогом, в большинстве случаев это вопрос поиска enum в заголовке, его изменения по мере необходимости и (возможно) повторной компиляции стандартной библиотеки для соответствия (но, поскольку это шаблон, есть большая вероятность, что вы только нужно доработать шапку). 31.03.2011
  • @Jerry Coffin: Говоря о VC ++, до VC ++ 2010, std::basic_string<char> и std::basic_string<wchar_t> предварительно создаются и экспортируются из CRT, а не только для заголовка, что делает изменение размера SSO довольно болезненным. Для VC ++ 2010 std::basic_string<> теперь используется только для заголовков, что, как вы говорите, делает его тривиальным. 31.03.2011

    • 4

    Я считаю, что код из Chromium просто оборачивает вещи в красивую оболочку. Но вы можете получить тот же эффект, не используя контейнер-обертку Chromium.

    Поскольку объект-распределитель копируется очень часто, он должен содержать ссылку или указатель на память. Итак, что вам нужно сделать, это создать буфер хранилища, создать объект распределителя, а затем вызвать конструктор std :: string с распределителем.

    Это будет намного сложнее, чем использование класса-оболочки, но должно дать тот же эффект.

    Вы можете увидеть пример подробного метода ( все еще использую хром) в моем вопросе о векторах стека.

    30.03.2011
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..