学ぶシーケンスコンテナ：ベクター、デック、リスト

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

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)
}

List

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
}

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

注意

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

すべて明確でしたか？

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

セクション 1. 章 1

AIに質問する

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

セクション 1. 章 1