Как реализовать строку, которая выделяется исключительно в стеке

Первый вопрос: сколько дополнительного интерфейса вы используете? Большинство дополнительных интерфейсов std::string могут быть тривиально реализованы с использованием функций в <algorithm> (например, std::find, std::find_if и std::search), и во многих случаях есть большие их части, которые в любом случае не будут использоваться. Просто реализуйте его по мере необходимости.

Я не думаю, что вы сможете заставить это работать с помощью специального распределителя. Единственный способ получить память «в стеке» - это объявить ее членом настраиваемого распределителя, что может создать всевозможные проблемы при их копировании. И распределители должны быть копируемыми, а копии должны быть идемпотентными.

Возможно, вы найдете бесплатную реализацию в сети std::string, в которой используется реализация небольшой строки; затем измените его так, чтобы размер отсечения (за пределами которого используется динамическое распределение) был больше, чем любые строки, которые вы фактически используете. (Доступно несколько реализаций стандартной библиотеки с открытым исходным кодом; версия, поставляемая с g ++, по-прежнему использует COW, но я подозреваю, что большинство других используют SSO.)

Это просто, напишите распределитель стека, вот пример:

https://codereview.stackexchange.com/questions/31528/a-working-stack-allocator < / а>

LLVM ADT имеет класс SmallString. В нем также есть SmallVector и много других полезных классов.

В то время как текущая кодовая база LLVM движется к использованию C ++ 11, (не очень) старые версии LLVM поддерживают C ++ 03.

Отличной отправной точкой является основанный на политике строковый класс Александреску, описанный в этом Статья доктора Доббса. Он включает политику единого входа, которая в основном делает то, что вы хотите (ищите на странице SmallStringOpt), и ее легко изменить, если / по вашему усмотрению. Он предшествует C ++ 11, так что у вас тоже все в порядке.

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

Использование распределителя, вероятно, не лучший вариант, поскольку интерфейс между строкой и распределителем предполагает, что объект распределителя является частью контейнера, но выделенная память поступает извне самого контейнера. Вы можете организовать это, реализовав распределитель с использованием POSIX alloca, со всеми недостатками.

Проблема при реализации строк в стеке заключается в том, что вы не можете позволить им динамически расти (возможно, в то время в стеке есть что-то большее), но вам также нужно позаботиться о таких операциях, как +=, которые могут сделать строку длиннее и длиннее.

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

Вероятно, существует компромисс, связанный с процессом связи между памятью и кешем (обычно выполняется со 128 байтами или 4 КБ), но он сильно зависит от оборудования, поэтому сложность, которую можно позволить, скорее всего, не окупится.

Более доступным решением может быть распределитель, который по-прежнему выделяет в куче, но имеет возможность сохранять и повторно использовать возвращенные блоки (до определенного предела), уменьшая необходимость запрашивать у системы выделение / освобождение.

Но производительность в этом случае не обязательно улучшится, если базовая система уже реализует new/delete таким образом.

Думаю, я бы использовал комбинацию VLA, определяемых реализацией, и стандартных алгоритмов.

Это рабочий код, но НЕ РЕКОМЕНДУЕМЫЙ СПОСОБ.

В этом коде много следов, чтобы показать, что он делает. Он не проверяет, не превышает ли размер запроса на выделение размер буфера. При необходимости вы можете это проверить. Обратите внимание, что std :: basic_string пытается выделить больше, чем необходимо.

#include <string>
#include <iostream>

template<typename T, size_t S>
class fixed_allocator
{
  typedef std::allocator<T> _base;

  std::ostream& trace() const { return std::cerr << "TRACE fixed_allocator " << (void*)this ; }

public:
  typedef typename _base::value_type value_type;
  typedef typename _base::pointer pointer;
  typedef typename _base::const_pointer const_pointer;
  typedef typename _base::reference reference;
  typedef typename _base::const_reference const_reference;
  typedef typename _base::size_type size_type;
  typedef typename _base::difference_type difference_type;

  template<class C> struct rebind {
    typedef fixed_allocator<C, S*sizeof(C)/sizeof(T)> other;
  };
  T* buffer_;

  fixed_allocator(T* b) : buffer_(b) { trace() << "ctor: p="  << (void*)b << std::endl; }

  fixed_allocator() : buffer_(0) { trace() << "ctor: NULL" << std::endl; };
  fixed_allocator(const fixed_allocator &that) : buffer_(that.buffer_) { trace() << "ctor: copy " << (void*)buffer_ << " from " << (void*) &that << std::endl; };

  pointer allocate(size_type n, std::allocator<void>::const_pointer hint=0) {
    trace() << "allocating on stack " << n << " bytes" << std::endl;
    return buffer_;
  }

  bool operator==(const fixed_allocator& that) const { return that.buffer_ == buffer_; }
  void deallocate(pointer p, size_type n) {/*do nothing*/}
  size_type max_size() const throw() { return S; }
};

int main()
{
  char buffer_[256];
  fixed_allocator<char, 256> ator(buffer_);
  std::basic_string<char, std::char_traits<char>, fixed_allocator<char, 256> > str(ator);
  str.assign("ipsum lorem");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  std::cout << " has 'l' at " << str.find("l") << std::endl;
  str.append(" dolor sit amet");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  str.insert(0, "I say, ");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  str.insert(7, "again and again and again, ");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  str.append(": again and again and again, ");
  std::cout << "String: '" << str << "' length " << str.size() << std::endl;
  return 0;
}

Этот код был протестирован на GCC и LLVM и работает должным образом (или неожиданно).

Синтаксис громоздкий. Невозможно получить от basic_string и встроить буфер. Намного лучший способ - создать небольшой специализированный класс buffer_string с необходимым подмножеством интерфейса basic_string.