4

如果我有这样的std::vector初始化：

0 1 2 3 4 5

我怎样才能最好地将 4 传播到第一位？即我希望std::vector处于这种状态：

4 0 1 2 3 5

O(N)我相信，卸下 4 并重新插入它可能会很昂贵，因为前面的插入是。我正在考虑在连续的地方交换值（比如在冒泡排序中），但这也是O(N). 是否使用另一个容器，就像std::list唯一的方法？

编辑：在看到一些混乱之后，让我澄清一下，我的目标是std::vector在std::vector.

4

4 回答 4

15

即使有一个公认的答案，正常的 C++ 方法是使用提供的算法。在这种情况下，它应该是std::rotate

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // for std::advance


int main(int argc, char** argv) {

    std::vector<int> v = { 0, 1, 2, 3, 4, 5 };

    std::cout << "Before: ";
    for (auto element : v)
        std::cout << element << " ";
    std::cout << std::endl;

    // edit starts here
    auto first=v.begin();
    auto nfirst=first;
    std::advance(nfirst, 4); // Iterator of first element to move to front
    auto last=nfirst;
    std::advance(last, 1); // 1 is element count for moving to front

    std::rotate(first, nfirst, last);
    // edit ends here

    std::cout << "After: ";
    for (auto element : v)
        std::cout << element << " ";
    std::cout << std::endl;

    return 0;
}

编辑： 在与 Luc Touraille 讨论后，我看到了改进的空间。现在该解决方案std::advance用于迭代器操作。所以它应该与前向迭代器一起工作，这是std::rotate.

于 2013-07-10T10:53:14.297 回答
7

如果 O(N) 是一个问题，则更改容器（例如 std::deque）是唯一的选择。

但是，请确保 O(N) 确实是一个问题！

于 2013-07-10T10:24:57.157 回答
3

说真的，我非常怀疑 O(n) 在您的实际代码中确实是一个问题。std::vector使用 a而不是 a有更好的理由std::list，例如更好的内存局部性和更少的内存开销，而不仅仅是 big-O。但是您仍然可以优化标准方法（尽管需要dst在 before src）

std::vector<int>::iterator src = ..., dst = ...;
...
auto tmp = std::move(*src);
vec.erase(src);
vec.insert(dst, std::move(tmp));

通过将两个 O(n) 遍历（一个在 中左移erase，一个在 中右移insert）变成一个（甚至更小）一个：

auto tmp = std::move(*src);
for(auto iter=src; iter!=dst; --iter)
    *iter = std::move(*std::prev(iter));
*dst = std::move(tmp);

编辑：虽然请注意，我上面的代码片段除了按照Jan在他的回答std::rotate中提出的不必要的复制外，什么也没做。

于 2013-07-10T10:57:19.793 回答
2

作为@JanHerrmann 提供的出色答案的补充，这是一个用于在范围内移动元素的通用函数：

#include <algorithm>
#include <iostream>
#include <iterator>

// Moves the element src before dst, maintaining the order of other values
template <typename RandomAccessIt>
void moveElement(RandomAccessIt src, RandomAccessIt dst)
{ 
    if (dst == src)
    {
        return;
    }
    if (dst < src)
    { 
        std::rotate(dst, src, src + 1);
    }
    else
    { 
        std::rotate(src, src + 1, dst);
    }
}

void printVector(const std::vector<int> &v)
{
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

int main() {

    std::vector<int> v = { 0, 1, 2, 3, 4, 5 };
    printVector(v); // 0 1 2 3 4 5

    moveElement(v.begin() + 4, v.begin());
    printVector(v); // 4 0 1 2 3 5

    moveElement(v.begin() + 2, v.begin() + 2);
    printVector(v); // 4 0 1 2 3 5

    moveElement(v.begin() + 2, v.begin() + 3);
    printVector(v); // 4 0 1 2 3 5

    moveElement(v.begin() + 2, v.end());
    printVector(v); // 4 0 2 3 5 1
}
于 2013-07-10T14:20:32.630 回答