学ぶシーケンスコンテナ：Vector、Deque、List

メニューを表示するにはスワイプしてください

std::vector、std::deque、std::list の違いを理解することは、アプリケーションの要件に最適なコンテナを選択するために重要。これらは C++ 標準ライブラリの主要なシーケンスコンテナであり、それぞれ異なるメモリレイアウト、アクセスパターン、典型的な使用例を持つ。

Vector

std::vector は要素を連続したメモリ領域に格納し、高速なランダムアクセスと効率的な CPU キャッシュ利用を実現。インデックスによる要素アクセスは定数時間で可能。ただし、途中や先頭での挿入・削除は、後続のすべての要素を移動させる必要があり、これらの操作はコストが高くなる場合がある。末尾への要素追加は一般的に高速だが、内部配列の再割り当てが必要な場合は例外となる。

main.cpp


              12345678910
            
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v = {1, 2, 3};
    v.push_back(4);  // Fast append
    v.insert(v.begin() + 1, 10);  // Slower insert (shift elements)
    std::cout << v[1];  // Fast random access
}

Deque

std::deque（両端キュー）は高速なランダムアクセスを提供するが、内部構造は単一の連続メモリブロックではなく、複数のメモリブロックのシーケンスとなっている。この設計により、前後両端での効率的な挿入・削除が可能。ただし、分割されたメモリレイアウトのため、ランダムアクセスは std::vector よりわずかに遅い。途中での挿入や削除は依然として比較的コストが高い。

main.cpp


              123456789
            
#include <deque>
#include <iostream>
int main()
{
    std::deque<int> d = {1, 2, 3};
    d.push_front(0);  // Fast front insertion
    d.push_back(4);   // Fast back insertion
    std::cout << d[2];  // Random access (slightly slower)
}

std::list は二重リンクリストであり、各要素は前後の要素へのポインタを持つ個別のノードに格納されます。この構造により、位置を示すイテレータがあれば、リスト内の任意の場所で定数時間で挿入および削除が可能です。ただし、ランダムアクセスはサポートされておらず、リストの先頭または末尾から順に走査する必要があり、これは線形時間の操作となります。また、ポインタの格納によるメモリのオーバーヘッドも大きくなります。

main.cpp


              1234567891011
            
#include <list>
#include <iostream>

int main()
{
    std::list<int> l = {1, 2, 3};
    auto it = ++l.begin();
    l.insert(it, 10);  // Fast insert at known position
    l.erase(--l.end());  // Fast erase at known position
    for (int x : l) std::cout << x << ' ';  // Linear traversal
}

適切なシーケンスコンテナの選択は、アプリケーションのパフォーマンス要件や典型的なアクセスパターンによって異なります。上記のコードサンプルは、それぞれのコンテナ内部構造が実際にどのような影響を及ぼすかを示しています。

注意

シーケンスコンテナを選択する際は、メモリオーバーヘッド、キャッシュ効率、操作の複雑さのトレードオフを常に考慮すること。

すべて明確でしたか？

フィードバックありがとうございます！

セクション 2. 章 1

AIに質問する

何でも質問するか、提案された質問の1つを試してチャットを始めてください

セクション 2. 章 1