C++プログラマへの道 #9 - シーケンスコンテナ

C++DSA

Last Edited: 9/27/2024

このブログ記事では、C++における標準配列、ベクトルなどのシーケンスコンテナを紹介します。

C++ Seq Con

コンテナは、複数のオブジェクトを格納するオブジェクトであり、クラステンプレートとして実装され、さまざまな便利なメソッドを備えています。 本記事では、要素が順番に格納されるシーケンスコンテナについて説明します。

標準配列

標準配列は、通常扱う配列とは異なり、size()、begin()、end()、empty()、at()、および [] 演算子などのメソッドにアクセスできるクラステンプレートです。

#include <array>
 
using namespace std;
 
int main() {
    // std::array<dtype, num_elements>
    array<int, 3> arr = {1, 3, 2};
 
    cout << "Size of arr: ";
    cout << arr.size() << endl;
 
    cout << "arr[2]: ";
    cout << arr[2] << endl; // arr.at(2) alternatively
 
    cout << "It starts with " << arr.front();
    cout << " and ends with " << arr.back() << "." << endl;
 
    array<int, 3>arr2;
    arr2.fill(4);
    arr.swap(arr2);
    cout << "arr[0] is now" <<arr.at(0) << endl;
 
    return 0;
}

実際のデータは data() メソッドを使用してアクセスでき、スタック上の連続した領域に格納されています。 標準配列の要素を反復処理し操作する際には、イテレータオブジェクトを使用することが推奨されます。 これは、データの格納方法に関係なく、要素をどのように反復処理するかの詳細を抽象化する参照オブジェクトです。

int main () {
    array<int, 3>arr = {1, 3, 2};
    
    cout << "arr: ";
    for (array<int, 3>::iterator i = arr.begin(); i != arr.end(); i++) {
        cout << " " << i;
    }
    cout << endl;
 
    // Alternative 1: Auto
    cout << "arr: ";
    for (auto i = arr.begin(); i != arr.end(); i++) {
        cout << " " << i;
    }
    cout << endl;
 
    // Alternative 2: 範囲指定のforループ
    cout << "arr: ";
    for (auto i : arr) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
}

auto キーワードを使用すると、イテレータは自動的に識別されるため、構文を短縮できます。 すべての要素を反復処理する場合、範囲指定のforループを使うと便利です。 また、sort(c.begin(), c.end()) のように、<algorithm> パッケージで提供されるソート機能など、 すでに多くのコンテナ操作が用意されています。

ベクトル

標準配列は便利ですが、そのサイズを指定し固定する必要があります。より柔軟性を持たせるために、ベクトルを使用できます。ベクトルは動的配列を使用し、静的配列に代わるものです。これは、記事 Road to C Programmer #8 - Linked Listで説明した ArrayList とよく似ており、 動的に割り当てられた連続メモリを使って高速なインデックス操作ができ、さらに多くの機能を提供します。

#include <vector>
 
int main () {
    vector<int> vec;
    vec.assign(5, 1); // Fill 1 for 5 times
    vec.push_back(5); // Push 5 at the back
    vec.insert(vec.begin(), 5); // Insert 5 at the beginning
    vec.pop_back(); // Remove the last element
    vec.resize(10); // Resize vec to store 10 ints
    vec.shrink_to_fit(); // Resize to fit all the elements (to 6)
    cout << vec[0] << endl; 
 
    cout << "vec: ";
    for (auto i : vec) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
}

ベクトルは動的に割り当てられた配列を使用するため、resize() や shrink_to_fit() といったメンバー関数にアクセスできます。 前回の記事で説明したように、連続したメモリはインデックス操作には効果的ですが、挿入や削除にはメモリのシフトやヒープ内の別のメモリ領域に再割り当てが必要になる場合があります。

リスト

C++ が提供する標準リストは、双方向リンクリストのクラステンプレートであり、各要素は前後のノードへのポインタを格納します（単方向リンクリストは forward_list として実装されています）。

#include <list>
 
int main () {
    list<int> li;
    li.push_front(10); // Add node to the front
    li.push_back(5); // Add node to the back
    li.insert(li.begin(), 1); // Inser 1 at the beginning
    li.sort();
 
    cout << "li: ";
    for (auto i : li) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
};

メモリのシフトやノードの再割り当てがないため、挿入と削除は通常高速です。しかし、 連続したメモリではないため、[] 演算子を使用できないことに加え、 要素のインデックス指定やサイズのカウントが遅く、キャッシュミスの確率も高くなります。

デック

ベクトルとリストには両方の利点が見られますが、それらをどのように組み合わせることができるでしょうか？ デック（deque）は、各ノードを小さな連続配列にすることで、ベクトルとリストを組み合わせます。これにより、 キャッシュヒットの確率が高まり、挿入と削除時のメモリシフトや再割り当てを最小限に抑えられます。

#include <deque>
 
int main () {
    deque<int> deq;
    deq.assign(5, 1); // Fill 1 for 5 times
    deq.push_back(5); // Push 5 at the back
    deq.insert(vec.begin(), 5); // Insert 5 at the beginning
    deq.pop_back(); // Remove the last element
    deq.resize(10); // Resize vec to store 10 ints
    deq.shrink_to_fit(); // Resize to fit all the elements (to 6)
    cout << deq[0] << endl;
 
    cout << "vec: ";
    for (auto i : deq) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
}

サポートされる操作はベクトルとほぼ同じですが、デックは前後の両方から挿入と削除が可能です。 また、デックは連続したメモリが保証されなくても [] 演算子が使用できます。デックは、 インデックス番号とその場所をマッピングするテーブルを追跡するため、便利ですが、 ベクトルよりも遅く、メモリ使用量が多くなる傾向があります。

結論

配列、ベクトル、リスト、デックはそれぞれ固有の利点と欠点を持っています。配列はサイズが既知である場合に効率的ですが、 挿入や削除には多くのシフトが必要です。ベクトルはより柔軟ですが、依然として配列と同様にシフトの問題があり、 メモリの再割り当てが必要になることがあります。リストは挿入や削除時にシフトや再割り当てが不要ですが、 インデックス指定やサイズ取得は遅く、煩雑です。デックは全体的に良好なパフォーマンスを発揮しますが、 メモリ使用量が多くなりがちです。

これらの特性を理解することは、どのシーケンスコンテナを使用すべきかを判断する上で重要です。 ただし、どれを選ぶにしても、パフォーマンスを測定することが大切です。幸いなことに、 シーケンスコンテナのインターフェースはほぼ同一であり、コードを最小限に変更するだけで異なるソリューションをテストすることができます。 （クラスやクラステンプレートの利点がここに見て取れます。）次の記事では、別の種類のコンテナについて引き続き説明します。

リソース

TOPに戻る↑