4

このように初期化されている場合std::vector：

0 1 2 3 4 5

4を最初の場所にどのように伝播させるのが最善ですか? つまりstd::vector、この状態が必要です:

4 0 1 2 3 5

4を取り外して再挿入すると、前面に挿入すると費用がかかる可能性があるO(N)と思います. (バブルソートのように) 連続する場所で値を交換することを考えていましたが、それも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::vectorbig-O よりも、 の代わりにを使用するほうがはるかに優れた理由がありstd::listます。たとえば、メモリの局所性が向上し、メモリのオーバーヘッドが少なくなります。ただし、標準のアプローチを最適化することもできます (ただし、 dstbeforesrcである必要があります)。

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

両方の O(n) トラバーサル (1 つは で左シフトし、eraseもう 1 つは で右シフトするinsert) を 1 つの (おそらくさらに小さい) ものに変えることで少し:

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 に答える