Какие знаешь возможные реализации строк?

Реализации строк в C/C++

Строки могут быть реализованы несколькими принципиально разными способами, каждый с собственными trade-offs.

1. C-стиль — массив с нулевым терминатором

Классический подход — массив char с нулевым символом в конце:

const char* str = "Hello";
// В памяти: [H][e][l][l][o][0]
// Длина определяется поиском нулевого символа

char buffer[256];
strcpy(buffer, str);  // Опасно! Нет проверки размера

// Безопасная версия
strncpy(buffer, str, sizeof(buffer) - 1);
buffer[sizeof(buffer) - 1] = '\0';

Преимущества:

• Минимальный overhead
• Совместимость с C библиотеками
• Быстрый перебор

Недостатки:

• Buffer overflow — легко выйти за границы
• O(n) для определения длины
• Нельзя хранить нулевые байты

2. std::string — классический контейнер

std::string — стандартная реализация в C++:

std::string str = "Hello";
str += " World";      // Динамическое расширение

std::cout << str.length() << std::endl;  // O(1)
std::cout << str[0] << std::endl;        // O(1) доступ

const char* c_str = str.c_str();  // Совместимость с C

Внутренняя структура:

struct string_impl {
    char* data;           // Указатель на буфер
    size_t length;        // Текущая длина
    size_t capacity;      // Выделенная память
};

Преимущества:

• Безопасность — проверки границ в debug режиме
• O(1) определение длины
• Автоматическое управление памятью (RAII)
• Удобный API (concat, find, substr и т.д.)

Недостатки:

• Небольшой overhead на указатель + размеры
• Перестроение при изменении размера (может быть O(n))
• SSO (Small String Optimization) усложняет реализацию

3. Small String Optimization (SSO)

Оптимизация для коротких строк — хранение данных внутри самого объекта:

// Типичная реализация с SSO
struct string_with_sso {
    union {
        char* ptr;              // Указатель для больших строк
        char buffer[32];        // Встроенный буфер для малых
    } data;
    size_t length;
    size_t capacity;
};

// Коротких строк не требуют выделение heap памяти
std::string short_str = "Hi";      // Использует buffer
std::string long_str = "Very long string...";  // Использует ptr

Преимущества:

• Нет выделения heap для коротких строк
• Лучше cache locality
• Прямой доступ к памяти

Недостатки:

• Более сложная реализация
• Использует больше памяти на стеке

4. Copy-on-Write (CoW) — устаревший подход

Старинная оптимизация для снижения копирований:

std::string s1 = "Hello";
std::string s2 = s1;  // s2 указывает на тот же буфер!
                      // Копирование происходит только при модификации
s2[0] = 'h';          // Теперь s2 создаёт собственный буфер

Плюсы: экономия памяти при копированиях

Минусы:

• Хромает в многопоточности — требует синхронизации
• Сложнее отладить
• Медленнее на современных процессорах (cache misses)
• Запрещено в C++11

5. std::string_view (C++17)

Некопируемое представление строки (pointer + length):

std::string str = "Hello World";
std::string_view view = str;  // Не копирует!

std::cout << view.substr(0, 5) << std::endl;  // "Hello"

// Идеально для функций, которые только читают
void process(std::string_view data) {
    // Работаем как со строкой, но без копии
    for (char c : data) {
        std::cout << c;
    }
}

Преимущества:

• Нулевой overhead
• Работает с C-строками и std::string
• Отлично для параметров функций

Ограничение:

• Не владеет данными — опасна для сохранения
• Только для чтения (immutable)

Сравнительная таблица

Лучшие практики

1. Используй std::string по умолчанию
2. Передавай строки через std::string_view
3. Избегай C-строк, если не нужна совместимость
4. Рассмотри SSO при выборе container для коротких строк

Итог

std::string — универсальный выбор для C++ кода. Для параметров функций используй std::string_view. С-строки нужны только для interop с legacy кодом или особо узких мест производительности.