C++: практическое руководство по rotate

Вам приходилось перемещать элементы в контейнере? Функция std::rotate на C++ — незаменимый инструмент для этой задачи.

Изучим работу rotate и различные сценарии его эффективного применения в проектах на C++.

Что такое std::rotate?

std::rotate — функция стандартной библиотеки C++ для перемещения влево, выполняемого в диапазоне элементов. Это часть заголовка <algorithm> для работы с любым контейнером, которым предоставляются двунаправленные итераторы.

Вот базовый синтаксис:

template <class ForwardIt>
ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last);

Не пугайтесь синтаксиса этого шаблона. На практике rotate прост, с ним код сильно упрощается.

Принцип работы rotate

Начнем с простого примера:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Перемещаются влево на две позиции
    std::rotate(numbers.begin(), numbers.begin() + 2, numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Этим кодом выводится: 3 4 5 1 2.

Разберемся, что здесь происходит:

1. Начали с последовательности {1, 2, 3, 4, 5}.
2. Вызвали rotate при помощи среднего итератора, которым указывается на третий элемент — индекс 2.
3. Все элементы от среднего до конечного переместились функцией в начало последовательности.
4. Элементы, которые изначально были впереди, переместились в конец.

Практические применения rotate

С основами разобрались, изучим реальные сценарии, где rotate приходится особенно кстати.

Реализация кольцевого буфера

Кольцевые буферы много где применяются — от обработки аудио до сетевых пакетов. Вот как используется rotate для реализации простого кольцевого буфера:

#include <algorithm>
#include <vector>
#include <iostream>

class CircularBuffer {
private:
    std::vector<int> buffer;
    size_t head = 0;
    size_t capacity;

public:
    CircularBuffer(size_t size) : buffer(size), capacity(size) {}

    void push(int value) {
        buffer[head] = value;
        head = (head + 1) % capacity;
    }

    void rotate() {
        std::rotate(buffer.begin(), buffer.begin() + 1, buffer.end());
    }

    void print() {
        for (int value : buffer) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    CircularBuffer cb(5);
    for (int i = 1; i <= 7; ++i) {
        cb.push(i);
        cb.print();
    }
    return 0;
}

Когда буфер заполнен, элементы при помощи rotate перемещаются, и таким образом постоянно добавляются новые элементы.

Перестановка элементов при обработке данных

В задачах обработки данных элементы переставляются, исходя из тех или иных условий. Вот пример того, как с применением rotate все четные числа перемещаются в начало вектора.

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    auto partition_point = std::partition(data.begin(), data.end(), 
        [](int n) { return n % 2 == 0; });

    std::rotate(data.begin(), partition_point, data.end());

    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

В этом коде сначала вектор разделяется так, что все четные числа оказываются в начале, затем нечетные числа при помощи rotate перемещаются в конец.

Реализация простого планировщика

rotate приходится кстати и при реализации простых алгоритмов планирования. Вот базовый планировщик с циклическим перебором:

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

class Task {
public:
    std::string name;
    int priority;

    Task(std::string n, int p) : name(std::move(n)), priority(p) {}
};

class Scheduler {
private:
    std::vector<Task> tasks;

public:
    void addTask(const Task& task) {
        tasks.push_back(task);
    }

    void runNextTask() {
        if (!tasks.empty()) {
            std::cout << "Running task: " << tasks.front().name << std::endl;
            std::rotate(tasks.begin(), tasks.begin() + 1, tasks.end());
        }
    }
};

int main() {
    Scheduler scheduler;
    scheduler.addTask({"Task1", 1});
    scheduler.addTask({"Task2", 2});
    scheduler.addTask({"Task3", 3});

    for (int i = 0; i < 5; ++i) {
        scheduler.runNextTask();
    }

    return 0;
}

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

Передовые методы работы с rotate

От практического применения rotate переходим к продвинутым методам и рекомендациям.

Перемещения в обоих направлениях

С std::rotate элементы по умолчанию перемещаются влево. Чтобы переместить их вправо, подкорректируем средний итератор:

#include <algorithm>
#include <vector>
#include <iostream>

template<class ForwardIt>
void rotateRight(ForwardIt first, ForwardIt last, size_t n) {
    if (first == last) return;
    auto size = std::distance(first, last);
    n = n % size;
    std::rotate(first, std::prev(last, n), last);
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    rotateRight(numbers.begin(), numbers.end(), 2);

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Функцией rotateRight элементы перемещаются вправо на n позиций.

Работа с несмежными контейнерами

std::rotate пригоден для работы с любым контейнером, которым предоставляются не только векторы, но и однонаправленные итераторы. Вот пример использования списка:

#include <algorithm>
#include <list>
#include <iostream>

int main() {
    std::list<char> chars = {'a', 'b', 'c', 'd', 'e'};

    auto middle = std::next(chars.begin(), 2);
    std::rotate(chars.begin(), middle, chars.end());

    for (char c : chars) {
        std::cout << c << " ";
    }
    std::cout << std::endl;

    return 0;
}

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

Сочетание rotate с другими алгоритмами

Для операций посложнее rotate комбинируют с другими алгоритмами. Например, с std::find — для перемещения элементов диапазона, пока конкретный элемент не окажется в начале:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    auto it = std::find(numbers.begin(), numbers.end(), 3);
    if (it != numbers.end()) {
        std::rotate(numbers.begin(), it, numbers.end());
    }

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

В этом коде элементы вектора перемещаются так, что 3 оказывается в начале.

Производительность

Хотя rotate в целом эффективен, имейте в виду:

1. Для небольших диапазонов простой цикл быстрее из-за меньших накладных расходов.
2. Для больших диапазонов rotate эффективнее, чем перемещать элемент за элементом вручную.
3. Сложность rotate линейно зависит от количества элементов в диапазоне.
4. При работе с очень большими наборами данных, чтобы потенциально повысить производительность, воспользуйтесь std::rotate с политиками выполнения — доступно в версии C++17 и новее.

Заключение

std::rotate — функция стандартной библиотеки C++, ею упрощается задача перемещения элементов в последовательности.

Мы изучили базовое применение, практические сценарии вроде реализации кольцевых буферов и простых планировщиков, а также продвинутые методы.

Освоив rotate и соответствующие сценарии, вы сможете написать более эффективный и понятный код для задач, связанных с перестановкой элементов.

Занимаетесь ли вы обработкой данных, реализацией пользовательских контейнеров или созданием систем планирования, rotate будет ценным инструментом в вашем арсенале C++.

Читайте также:

• C++: руководство по сортировке строк
• cin.ignore() на C++
• C++: руководство по считыванию CSV-файлов

Читайте нас в Telegram, VK и Дзен

Перевод статьи ryan: C++ rotate: Practical Guide