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

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

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

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

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.