Вам приходилось перемещать элементы в контейнере? Функция 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, 2, 3, 4, 5}. - Вызвали
rotateпри помощи среднего итератора, которым указывается на третий элемент — индекс2. - Все элементы от среднего до конечного переместились функцией в начало последовательности.
- Элементы, которые изначально были впереди, переместились в конец.
Практические применения 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 в целом эффективен, имейте в виду:
- Для небольших диапазонов простой цикл быстрее из-за меньших накладных расходов.
- Для больших диапазонов
rotateэффективнее, чем перемещать элемент за элементом вручную. - Сложность
rotateлинейно зависит от количества элементов в диапазоне. - При работе с очень большими наборами данных, чтобы потенциально повысить производительность, воспользуйтесь
std::rotateс политиками выполнения — доступно в версии C++17 и новее.
Заключение
std::rotate — функция стандартной библиотеки C++, ею упрощается задача перемещения элементов в последовательности.
Мы изучили базовое применение, практические сценарии вроде реализации кольцевых буферов и простых планировщиков, а также продвинутые методы.
Освоив rotate и соответствующие сценарии, вы сможете написать более эффективный и понятный код для задач, связанных с перестановкой элементов.
Занимаетесь ли вы обработкой данных, реализацией пользовательских контейнеров или созданием систем планирования, rotate будет ценным инструментом в вашем арсенале C++.
Читайте также:
Читайте нас в Telegram, VK и Дзен
Перевод статьи ryan: C++ rotate: Practical Guide
