C++rotate返回新起始迭代器

2026-04-01 14:05:29 1655阅读 0评论

C++ 中 `std::rotate` 函数的妙用

在C++编程中，std::rotate 是一个非常有用的算法，它可以在常数时间内将容器中的元素旋转一定位置。然而，很多人可能并不了解 std::rotate 返回的是什么类型的迭代器，以及如何利用这个特性来编写更高效的代码。

什么是 `std::rotate`

std::rotate 是 C++ 标准库中的一个算法，位于 <algorithm> 头文件中。它的作用是将区间 [first, last) 的元素向右移动 n 个位置。具体来说，如果 n <= (last - first) / 2，则将前 n 个元素移到后半部分；否则，将后 (last - first) - n 个元素移到前半部分。

std::rotate 的函数原型如下：

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

first 和 last 定义了要旋转的范围。
middle 是旋转点，即 first 到 middle 的元素会被移到 middle 到 last 的位置。

返回值

std::rotate 返回一个新的起始迭代器，指向原来的 middle 迭代器的位置。这个新的起始迭代器可以用来继续遍历或操作容器。

例如：

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto new_begin = std::rotate(vec.begin(), vec.begin() + 2, vec.end());

    for (auto it = new_begin; it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

在这个例子中，new_begin 将指向 3，因为 std::rotate 将前两个元素 {1, 2} 移到后面，变成了 {3, 4, 5, 1, 2}。

应用场景

快速找到中位数

由于 std::rotate 可以快速调整元素的位置，我们可以利用它来快速找到数组的中位数。以下是一个示例代码：

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

int find_median(std::vector<int>& vec) {
    std::nth_element(vec.begin(), vec.begin() + vec.size() / 2, vec.end());
    return vec[vec.size() / 2];
}

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int median = find_median(vec);
    std::cout << "Median: " << median << std::endl;
    return 0;
}

在这个例子中，std::nth_element 使用了类似 std::rotate 的思想，将第 k 小的元素放到正确的位置上，从而找到中位数。

分割数组

std::rotate 还可以用于分割数组。例如，我们将数组分成两部分，使得前一部分的和小于等于后一部分的和：

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

void split_array(std::vector<int>& vec) {
    std::sort(vec.begin(), vec.end());
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    int left_sum = 0;
    for (size_t i = 0; i < vec.size(); ++i) {
        left_sum += vec[i];
        if (left_sum >= sum / 2) {
            auto new_begin = std::rotate(vec.begin(), vec.begin() + i + 1, vec.end());
            for (auto it = new_begin; it != vec.end(); ++it) {
                std::cout << *it << " ";
            }
            break;
        }
    }
}

int main() {
    std::vector<int> vec = {1, 3, 5, 7, 9, 2, 4, 6, 8};
    split_array(vec);
    return 0;
}

在这个例子中，我们先对数组进行排序，然后使用 std::accumulate 计算总和，并通过 std::rotate 将分割点调整到正确的位置。