1

ベクトルがあり、STL アルゴリズムを使用してベクトルの後半を別のベクトルに効率的に分割したいと考えています。これを行う方法の 1 つを次に示しますが、より効率的で簡潔な回答、または少なくとも stl アルゴリズムを使用する回答があることを期待しています。

std::vector<Entry> &entries = someFunction();
int numEntries = entries.size();

// Assume numEntries is greater than or equal to 2.

std::vector<Entry> secondEntries;
std::vector<Entry>::iterator halfway = entries.begin() + numEntries / 2;
std::vector<Entry>::iterator endItr  = entries.end() 

// Copy the second half of the first vector in the second vector:
secondEntries.insert(secondEntries.end(), halfway, endItr);

// Remove the copied entries from the first vector:
entries.erase(halfway, endItr);
4

3 に答える 3

4

一歩下がって、（必然的に）コンテナではなく、独自のアルゴリズムでイテレータを使用していることを確認してください。したがって、これがある場合：

void foo(const std::vector<Entry>& v) { /* ... */ }

そして今、あなたはこの状況で立ち往生しています：

std::vector<Entry> entries = someFunction();

// have to split entries! make more containers? :(
foo(first_half(entries));
foo(second_half(entries));

代わりに反復子を使用することを検討してください。

// or a template, if it doesn't hurt
void foo(std::vector<Entry>::const_iterator first, 
         std::vector<Entry>::const_iterator second) { /* ... */ }

したがって、コンテナではなく範囲を示します。

std::vector<Entry> entries = someFunction();

// easy to split entries! :)
auto middle = entries.begin() + entries.size() / 2;
foo(entries.begin(), middle);
foo(middle + 1, entries.end());

これにより、不要なコンテナーと割り当ての数が制限されます。

邪魔にならないように、C++ 11ではこれを行うことができます（残りは同じです）：

// *Move* the second half of the first vector in the second vector:           
secondEntries.insert(secondEntries.end(),
                        std::make_move_iterator(halfway),
                        std::make_move_iterator(endItr));

Entry移動コンストラクターがある場合、move_iteratorアダプターは挿入中にそれが使用されることを保証します (そうでない場合は、通常のコピーが作成されます)。C++03 では、あなたが持っているものがおそらく最高です。

于 2012-08-13T17:17:39.543 に答える
1

c++11 コンパイラと移動可能なオブジェクトにアクセスできる場合、 std::moveはより良い仕事をすることができます。

最初のベクトルからそれらを消去する必要があることに注意してください。

于 2012-08-13T17:08:42.483 に答える
0

このタスクを実行する方法は他にもいくつかあります。たとえば、コピーアルゴリズムと挿入イテレータを使用します。

ただし、ベクトルコンテナの性質上、アルゴリズムによるこれらのアクションの複雑さは常にO（n）になります。ベクターは、O（1）（定数）時間内にあるコンテナーから別のコンテナーにデータの大きなチャンクを移動できるリストではありません。特定のSTLの実装によっては、一方の方法がもう一方の方法よりも10〜20％優れている場合がありますが、それ以上になることはほとんどありません。

コンテナのデータ型で移動セマンティクスが許可されており、これらの言語機能を利用できる場合、これは間違いなく役立ちます。ただし、これは、コンテナ自体ではなく、コンテナ内のデータオブジェクトの処理に関するものです。

于 2012-08-13T17:09:58.693 に答える