1

以下を使用する以外に、ベクトルを分割する他の一定時間の方法はありますか。

 std::vector<int> v_SplitVector(start , end);

これには O(N) の複雑さが必要です。この場合、O(終了 - 開始)。これを行うための一定時間の操作はありますか。

または、タスクに間違ったコンテナを使用していますか?..

4

5 に答える 5

3

要素が連続したメモリ上にあるベクトルのようなコンテナの場合、コンテナを「分割」する行為には、必然的にすべてのコピー/移動が反対側に移動する必要があります。

listそれぞれが独自のメモリ ブロックに要素を持つ のようなコンテナは、簡単に再配置できます (「 」を参照std::list::splice) 。

ただし、連続していないメモリに要素があると、キャッシュが失われる頻度が高くなるため、メモリ アクセスのパフォーマンスが低下する可能性があります。

言い換えると、アルゴリズムの複雑さだけがパフォーマンスに影響を与える要因ではない可能性があります。分散した要素を頻繁にリニア ウォークするよりも、リニア コピーを頻繁に行わない方がダメージが少ない可能性があります。

トレードオフは、ハードウェアがキャッシュを管理する方法と、使用している std 実装がそれを処理する方法 (およびコンパイラが最終的にどのように最適化できるか) に大きく依存します。

于 2013-02-08T08:33:26.480 に答える
3

これは分割ではなくコピーであるため、複雑になります。おそらく、パフォーマンスが向上する分割を作成できlistます。

于 2013-02-08T08:26:09.917 に答える
2

Creating a new std::vector necessarily requires copying, since vectors aren't allowed to share parts of their implementation. A modification in the container from which you obtained start and end shouldn't affect the values in splitVector.

What you can do, fairly easily, is create a View container, which simply holds the two iterators, and maps all accesses through them. Something along the lines of: 

template <typename Iterator>
class View
{
    Iterator myBegin;
    Iterator myEnd;
public:
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    //  And the other usual typedefs, including...
    typedef Iterator iterator;

    View( Iterator begin, Iterator end )
        : myBegin( begin )
        , myEnd( end )
    {
    }

    iterator begin() { return myBegin; }
    iterator end()   { return myEnd; }
    value_type operator[]( ptrdiff_t index ) { return *(myBegin + index ); }
    //  ...
};

This requires a fair amount of boilerplate, because the interface to something like vector is rather complete, but it's all very straight forward and simple. The one thing you cannot do with this, however, is modify the topology of either the underlying container or of any View—anything which might invalidate any iterators will of course, wreck havoc.

于 2013-02-08T09:30:43.693 に答える
2

std::vectorは以下をサポートしていませんが、効率的な「分割」操作が非常に重要な場合は、おそらく独自のコンテナーを作成できます。これはかなりの作業になります。

次のように「分割」を定義できます。

  • コンテナの最初のセグメントを削除し、それらの要素を含む新しいコンテナを返します。これらの要素への参照は、新しいコンテナー内の同じ要素を参照し続けます。古いコンテナには、残りの要素が含まれています。新しいコンテナの容量はそのサイズに等しく、古いコンテナの容量は削除された要素の数だけ減少します。

次に、古いコンテナーと新しいコンテナーは、基になるストレージのブロックを共有します (おそらく参照カウントを使用)。新しいコンテナーは、追加する場合は再割り当てする必要があります (その要素の最後にあるメモリが使用されているため)。

サンプル コードはコピーを取りますが、元のコンテナーは変更しません。論理コピーが必要な場合、要素を実際にコピーせずにそれを行うには、COW または不変オブジェクトが必要です。

std::listsplice()要素の範囲をあるリストから別のリストに移動できる機能があります。O(1)これにより要素のコピーが回避されますが、移動した要素の数をカウントする必要があるため、C++11 の時点では実質的に ではないことが保証されています。C++03 の実装では、この op を にするか にするかを選択できましO(1)たlist::size()がO(1)、C++11 ではsize()、すべてのコンテナーに対して一定の時間にする必要があります。

std::vectorただし、 withのパフォーマンスを比較することstd::listは、通常、1 つの操作だけではありません。listランダム アクセス イテレータなどがないことを考慮する必要があります。

于 2013-02-08T08:55:52.703 に答える
0

開始/終了とは異なる場所に要素を追加または削除する場合、必要な内部シフトのために、ベクトルには少なくとも o(n) の複雑さが必要です。sme は、要素を削除するだけでなく、移動したい場合に続きます。ベクトルの場合、要素をコピーする必要があるため、移動する要素ごとに少なくとも 1 つの op が必要です。つまり、ベクトルから要素を移動すると、少なくとも O(N) になります。ここで、N は移動した要素の量です。

ほぼ一定時間の追加/削除操作 (1 つまたは複数の要素の追加/挿入) が必要な場合は、特にポインタ/イテレータ。またはツリー、またはその他の動的構造。

ところで、私は何を感じv_SplitVectorますが、それはどこから来たのですか? stdlib または boost でそのような関数/メソッドを覚えていませんか?

于 2013-02-08T08:27:38.827 に答える