C++ での STL ベクトルと STL リストの違い
この記事では、C++ の STL vector コンテナと list コンテナの主な違いについて説明し、説明します。
C++ で std::list コンテナの代わりに std::vector を使用するタイミングを決定する
C++ STL コンテナは、要素を操作するために同様のインターフェイスを共有することがよくあります。それでも、これらのデータ構造の内部の違いを調べて、特定の問題に最適なコンテナーを選択する必要があります。std::vector 関数は、一般に動的配列として知られています。動的メモリを内部で自動的に管理し、C スタイルの配列と同様に要素を連続して格納します。後者の機能により、一定時間で要素にアクセスできます。
一方、std::list コマンドは、要素が二重にリンクされたリストとして管理されるデータ構造を実装します。C++ 標準では通常、正確な実装が二重リンクリストになることを強制しないため、前の文をそのまま作成します。それでも、標準ライブラリの実装者が満たす必要のある特定の特性を指定します。
std::list コマンドはテンプレートクラスとして提供され、std::vector と同様のあらゆるタイプのオブジェクトを格納します。push_back または push_front メンバー関数を使用して、新しい要素を std::list オブジェクトに格納できます。これらはすべて、一定の時間計算量を持っています。std::vector に関しては、平均的な一定の複雑さを持つ push_back しかありません。これらの関数は、指定されたオブジェクトの最初/最後に要素を追加するために使用されることに注意してください。
以下のサンプルコードは、各コンテナタイプでの上記の関数の基本的な使用法を示しています。
#include <algorithm>
#include <iostream>
#include <list>
using std::cout;
using std::endl;
using std::list;
using std::vector;
int main() {
vector<int> v = {1, 2, 13, 84};
list<int> l = {1, 2, 13, 84};
v.push_back(25);
v.push_back(13);
l.push_back(25);
l.push_front(13);
return EXIT_SUCCESS;
}
対照的に、指定された位置に新しい要素を挿入する場合は、insert メンバー関数を使用する必要があります。現在、この操作は、std::list と std::vector の主な違いの 1つです。一般に、insert 操作は、リストオブジェクトよりもベクトルオブジェクトの方がコストがかかります。
ベクトルの内容は連続して保存されるため、新しく挿入された各要素は、ベクトル自体のサイズに応じて、次の要素を強制的に右に移動します。したがって、オブジェクトの先頭の途中で多くの挿入を実行する必要がある場合は、vector コンテナの使用を避ける必要があります。後者の場合は、位置がわかればリストの任意の場所に新しい要素を挿入するのに一定の時間がかかるため、list コンテナを使用することをお勧めします。
次のコード例では、挿入の時間差を示しています。ここでは、両方のコンテナーが任意の 100000 整数で初期化され、各オブジェクトへの 1 回の挿入操作の時間が計測されます。std::search 関数で取得した、両方のコンテナの比較的中間の位置（39999）を選択したことに注意してください。その結果、リストのベクトルに新しい要素を挿入するには、数百の要素が必要になります。
要素の削除操作は挿入に似ているため、vector よりも list オブジェクトの方が効率的です。欠点として、list 要素には、最初と最後の要素を除いて、定数時間アクセス操作がありません。
#include <sys/time.h>
#include <algorithm>
#include <iostream>
#include <list>
#include <random>
using std::cout;
using std::endl;
using std::list;
using std::vector;
float time_diff(struct timeval *start, struct timeval *end) {
return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}
const int MIN = 1;
const int MAX = 100;
const int CAPASITY = 100000;
int main() {
struct timeval start {};
struct timeval end {};
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
vector<int> vec1;
list<int> list1;
vec1.reserve(CAPASITY);
for (int i = 0; i < CAPASITY; ++i) {
if (i % 39999 == 0) {
vec1.push_back(111);
continue;
}
vec1.push_back(distr(eng));
}
for (int i = 0; i < CAPASITY; ++i) {
if (i % 39999 == 0) {
list1.push_back(111);
continue;
}
list1.push_back(distr(eng));
}
auto iter = std::find(vec1.begin(), vec1.end(), 111);
gettimeofday(&start, nullptr);
vec1.insert(iter, 1111);
gettimeofday(&end, nullptr);
printf("insert vector: %0.8f sec\n", time_diff(&start, &end));
auto iter2 = std::find(list1.begin(), list1.end(), 111);
gettimeofday(&start, nullptr);
list1.insert(iter2, 1111);
gettimeofday(&end, nullptr);
printf("insert list : %0.8f sec\n", time_diff(&start, &end));
return EXIT_SUCCESS;
}
出力：
insert vector: 0.00053000 sec
insert list : 0.00000100 sec
