Как перевернуть строку с минимальными затратами?

Развёртывание строки: оптимальные методы

Это классическая задача, которая проверяет понимание работы со строками, временной сложности и минимизации затрат памяти.

Метод 1: std::reverse() - Оптимальное решение

Самый эффективный встроенный метод.

#include <string>
#include <algorithm>

std::string reverse_optimal(std::string str) {
    std::reverse(str.begin(), str.end());
    return str;
}

// Использование:
std::string text = "Hello";
std::string reversed = reverse_optimal(text);
// reversed = "olleH"

Анализ сложности:

• Временная сложность: O(n) - один проход
• Пространственная сложность: O(1) - in-place операция (не считая исходной строки)
• Число операций: n/2 swap операций

Это оптимально, потому что:

• Один проход по строке
• Только n/2 обменов элементов
• Встроенная функция - оптимизирована компилятором

Метод 2: Ручной swap с двумя указателями

Если нужна большая контроль.

#include <string>

std::string reverse_manual(std::string str) {
    int left = 0;
    int right = str.length() - 1;
    
    while (left < right) {
        std::swap(str[left], str[right]);
        left++;
        right--;
    }
    
    return str;
}

Плюсы: ясный алгоритм, понимаешь что происходит Минусы: медленнее встроенного reverse (компилятор не знает об оптимизации)

Метод 3: Если нужно минимум памяти (const reference)

Для очень больших строк, когда нельзя копировать.

#include <string>

// Изменяет исходную строку
void reverse_inplace(std::string& str) {
    std::reverse(str.begin(), str.end());
}

// Использование:
std::string text = "Hello";
reverse_inplace(text);
// text = "olleH"

Сложность:

• Временная: O(n)
• Пространственная: O(1) - не создаём копию

Метод 4: Для C-строк (char*)

Если работаете с legacy кодом или требуется совместимость.

#include <cstring>
#include <algorithm>

void reverse_cstring(char* str) {
    int len = std::strlen(str);
    int left = 0;
    int right = len - 1;
    
    while (left < right) {
        std::swap(str[left], str[right]);
        left++;
        right--;
    }
}

// Использование:
char text[] = "Hello";
reverse_cstring(text);
// text = "olleH"

Метод 5: Для очень больших данных (streaming)

Если строка не помещается в памяти.

#include <fstream>
#include <queue>
#include <iostream>

void reverse_large_file(const std::string& input_file, 
                        const std::string& output_file) {
    std::ifstream input(input_file);
    std::ofstream output(output_file);
    
    // Буферизуем данные блоками
    const size_t buffer_size = 8192;  // 8KB
    std::vector<char> buffer(buffer_size);
    std::vector<char> all_data;
    
    // Читаем всё в буфер
    while (input.read(buffer.data(), buffer_size) || input.gcount()) {
        all_data.insert(all_data.end(), 
                       buffer.begin(), 
                       buffer.begin() + input.gcount());
    }
    
    // Разворачиваем
    std::reverse(all_data.begin(), all_data.end());
    
    // Пишем результат
    output.write(all_data.data(), all_data.size());
}

Сравнение методов

Метод              | Время    | Память | Читаемость | Production
───────────────────|----------|--------|-----------|──────────
std::reverse       | O(n)     | O(1)   | ⭐⭐⭐    | ✅
Мануальный swap    | O(n)     | O(1)   | ⭐⭐      | ✅
Копирование        | O(n)     | O(n)   | ⭐⭐⭐    | ❌
стандартный алгоритм| O(n)    | O(1)   | ⭐⭐⭐    | ✅

Практический пример: микро-оптимизация

#include <string>
#include <algorithm>
#include <chrono>
#include <iostream>

int main() {
    std::string text(1000000, 'a');
    
    auto start = std::chrono::high_resolution_clock::now();
    
    // Вариант 1: std::reverse
    std::reverse(text.begin(), text.end());
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
    
    std::cout << "Время: " << duration.count() << " нс" << std::endl;
    
    return 0;
}

Минимум затрат по типам

Если нужна копия (функция возвращает новую строку):

std::string reverse(const std::string& str) {
    std::string result = str;        // Копия
    std::reverse(result.begin(), result.end());
    return result;                   // RVO/move semantics
}
// Минимум затрат: O(n) время, O(n) память (неизбежно для копии)

Если можно изменять исходную строку:

void reverse(std::string& str) {
    std::reverse(str.begin(), str.end());
}
// Минимум затрат: O(n) время, O(1) память - ОПТИМАЛЬНО

Если работаете с очень большими объёмами:

// Используйте mmap и обрабатывайте блоками
#include <sys/mman.h>
// ... мэппируете файл в память
// ... обрабатываете блоками

Частые ошибки

Ошибка 1: Создание копии, когда можно обойтись без неё

// ПЛОХО
std::string temp = original;
std::reverse(temp.begin(), temp.end());
original = temp;  // Лишняя копия!

// ХОРОШО
std::reverse(original.begin(), original.end());

Ошибка 2: Работа с C-строками без проверки

// ПЛОХО
void reverse_unsafe(char* str) {
    // Не проверяем, что str != nullptr
    int len = strlen(str);
    // ...
}

// ХОРОШО
void reverse_safe(char* str) {
    if (!str) return;
    int len = strlen(str);
    // ...
}

Ошибка 3: Забывают про return value optimization

// МОЖНО (компилятор оптимизирует)
std::string get_reversed() {
    std::string result = "hello";
    std::reverse(result.begin(), result.end());
    return result;  // RVO исключит копию
}

Рекомендация

Используйте std::reverse() — это оптимальное решение для большинства случаев:

• Встроенная функция стандартной библиотеки
• Оптимизирована компилятором
• Работает за O(n) время и O(1) доп. памяти
• Читаемый и безопасный код

Вот complete example:

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string text = "Hello, World!";
    
    std::reverse(text.begin(), text.end());
    
    std::cout << text << std::endl;  // Выведет: !dlroW ,olleH
    
    return 0;
}