ブログ

C++ 応用学習

C++ 発展編 6日目

コンテナ

コンテナとは、いろいろな種類のオブジェクト（要素）データを、効率的に格納し、取り出し、操作するための仕組みが備わった「入れ物」です
C++では、コンテナはクラステンプレートという形で提供されています
これは、どんな種類のデータでも柔軟に入れられるように設計されているため、例えば、整数のコレクションも、文字列のコレクションも、同じ仕組みで作ることができます

コンテナは、中に入っているデータの保存場所を管理してくれます
データには、直接アクセスすることもできますし、イテレータという「ポインターに似た性質をもつ参照オブジェクト」を使って順番にアクセスすることも、メンバ関数でもアクセスすることもできます

C++には、標準で用意されている標準テンプレートライブラリ（STL）という便利なコンテナクラスがたくさんあります

しかし、Windowsのアプリケーションを作る場合など、特にWindowsランタイムという仕組みを使って、C++で作ったデータをJavaScriptやXAML（ユーザーインターフェースを作るための言語）といった他の部分とやり取りしたい場合は、Windowsランタイム専用のコレクションを使う必要があります
これは、Windowsランタイムがデータのやり取りのルールを決めているからです

C++のコンテナには、以下のような種類があります
なお、コンテナの詳細についてはContainers library – cppreference.comを参照ください

シーケンスコンテナ

要素を順序付けて格納します
要素の追加順や特定の位置への挿入順が維持されます

  • std::vector: 動的配列。要素のランダムアクセスが高速
  • std::deque: 双方向キュー。両端からの高速な追加・削除が可能
  • std::list: 双方向リンクリスト。要素の挿入・削除が高速
  • std::forward_list: 単方向リンクリスト（C++11から）。std::listより軽量

以下は、vectorを使用したサンプルプログラムです

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    // int型のvectorを作成
    vector<int> v;

    // 末尾に要素を追加
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    // イテレーターを使って要素にアクセス
    for (auto it = v.begin(); it !＝ v.end(); ++it) {
        cout << *it << " "; // 10 20 30
    }
    cout << endl;

    // インデックスを使って要素にアクセス
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << " " ; // 10 20 30
    }
    cout << endl;

    // 末尾の要素を削除
    v.pop_back();

    // 要素数を表示
    cout << v.size() << endl; // 2

    return 0;
}

アソシエイティブコンテナ

キーに基づいて要素を格納し、要素は常にソートされた状態で管理されます
検索、挿入、削除が高速に行われます

  • std::set: キーのみを格納するセット。重複するキーは許可しない
  • std::multiset: キーのみを格納するマルチセット。重複するキーも許可する
  • std::map: キーと値のペアを格納するマップ。キーは重複しない
  • std::multimap: キーと値のペアを格納するマルチマップ。キーは重複してもよい

以下は、setを使用したサンプルプログラムです

#include <iostream>
#include <set>
using namespace std;

int main()
{
    // int型のsetを作成
    set<int> s;

    // 要素を追加
    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(10); // 重複した要素は無視される

    // イテレーターを使って要素にアクセス
    for (auto it = s.begin(); it !＝ s.end(); ++it) {
        cout << *it << " "; // 10 20 30
    }
    cout << endl;

    // 要素を検索
    auto it = s.find(20);
    if (it != s.end()) {
        cout << *it << " is found" << endl; // 20 is found
    } else {
        cout << "not found" << endl;
    }

    // 要素を削除
    s.erase(20);

    // 要素数を表示
    cout << s.size() << endl; // 2

    return 0;
}

非順序アソシエイティブコンテナ

キーに基づいて要素を格納しますが、ハッシュ関数を使用して要素の位置を決定します
ソートされた順序は保証されませんが、平均的にはアソシエイティブコンテナよりも高速な検索・挿入・削除が可能です

  • std::unordered_set: キーのみを格納する非順序セット
  • std::unordered_multiset: キーのみを格納する非順序マルチセット
  • std::unordered_map: キーと値のペアを格納する非順序マップ
  • std::unordered_multimap: キーと値のペアを格納する非順序マルチマップ

以下は、unordered_mapを使用したサンプルプログラムです

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    // string型のキーとint型の値を持つunordered_mapを作成
    unordered_map<string, int> um;

    // 要素を追加
    um["apple"] = 100;
    um["banana"] = 200;
    um["orange"] = 300;

    // イテレーターを使って要素にアクセス
    for (auto it = um.begin(); it !＝ um.end(); ++it) {
        cout << it->first << ": " << it->second << endl; // apple: 100, banana: 200, orange: 300の順ではないかもしれない
    }

    // キーを使って要素にアクセス
    cout << um["apple"] << endl; // 100

    // 要素を検索
    auto it = um.find("banana");
    if (it != um.end()) {
        cout << it->first << ": " << it->second << " is found" << endl; // banana: 200 is found
    } else {
        cout << "not found" << endl;
    }

    // 要素を削除
    um.erase("orange");

    // 要素数を表示
    cout << um.size() << endl; // 2

    return 0;
}

コンテナアダプタ

既存のコンテナ（シーケンスコンテナがよく使われます）の機能をラップし、特定のインターフェース（操作のセット）を提供するものです
基盤となるコンテナのすべての操作が利用できるわけではなく、アダプタが定義する操作のみが可能です

  • std::stack: LIFO（Last-In, First-Out）のデータ構造
  • std::queue: FIFO（First-In, First-Out）のデータ構造
  • std::priority_queue: 要素に優先順位をつけ、最も優先度の高い要素を常に取得できるデータ構造

以下は、stackを使用したサンプルプログラムです

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    // int型のstackを作成
    stack<int> st;

    // 末尾に要素を追加
    st.push(10);
    st.push(20);
    st.push(30);

    // 末尾の要素を表示
    cout << st.top() << endl; // 30

    // 末尾の要素を削除
    st.pop();

    // 末尾の要素を表示
    cout << st.top() << endl; // 20

    // 要素数を表示
    cout << st.size() << endl; // 2

    return 0;
}

イテレーター

上述しているサンプルプログラムでは、イテレーターを利用して要素にアクセスしています
ここでは、イテレーターについて説明をします

コンテナに保存されたデータを取り出すためには、いくつかの方法があります
例えば、std::vectorのように、要素が順番に並んでいるコンテナでは、配列と同じように添字（インデックス）を使って特定の要素に直接アクセスできます

#include <iostream>
#include <vector>

int main(){
    std::vector<int> ary = {1,2,3,4,5};

    for(int i=0;i<5;i++){
        std::cout << ary[i] << std::endl;
    }

    return 0; 
}

しかし、コンテナの種類によってはデータの格納方法やアクセス方法が異なっているため、添字で直接アクセスすることが効率的でない場合もあります
例えば、std::listは要素がバラバラに配置されていて、要素同士がポインタで繋がっているため、添字でのアクセスは効率が悪いです

そこで登場するのが『イテレーター』です

イテレーターとは、プログラミング言語の機能の一つで、配列のようなデータ構造の要素を順番にアクセスする繰り返し処理を簡潔に記述できる構文やオブジェクトのことです
C++のイテレーターは内部構造の異なるコンテナに対して、要素を一つづつ指し示すための共通のインターフェースを提供できるように設計されたクラス群のことです
イテレーターは、コンテナの中の特定の要素を指し示す『ポインタのようなもの』と考えると理解しやすいでしょう

そして、イテレーターを操作することで、コンテナの中の要素を順番に辿っていくことができます
イテレーターを使うと、コンテナの種類によらず、同じような方法で要素にアクセスできるというメリットがあります

イテレーターの基本的な使い方

イテレーターを使うには、主に以下の手順を踏みます

  1. イテレーターの取得
    コンテナが持つメンバ関数（例えば、begin()やend()）を使って、イテレーターを取得します
  • begin(): コンテナの最初の要素を指すイテレーターを返します
  • end(): コンテナの最後の要素の次を指すイテレーターを返します
  1. イテレーターの操作
    取得したイテレーターを使って、要素を指し示したり、次の要素に進めたりします
  • *it: イテレーターitが指す要素の値を取得します（間接参照演算子）
  • ++it: イテレーターitを次の要素に進めます（インクリメント演算子）
  • –it: イテレーターitを前の要素に戻します（デクリメント演算子）
  1. イテレーターの比較
    イテレーター同士を比較して、同じ要素を指しているかなどを確認します
  • it1 == it2: イテレーターit1とit2が同じ要素を指している場合にtrueを返します
  • it1 != it2: イテレーターit1とit2が異なる要素を指している場合にtrueを返します

たとえば、std::vectorのサンプルプログラムで、各ステップを見ていきます

for (auto it = v.begin(); it != v.end(); ++it) {

v.begin()でコンテナ内の先頭を指すイテレーターを取得します
auto型を使用することで、型の宣言を短く記述しています

it != v.end()

end() で取得するイテレータは最終要素ではなく、 最終要素の1つ先であるためループの終了条件として使用できます

イテレータはコンテナの種類に依存しないため、std::listを使用してもそのまま動作します

#include <iostream>
#include <list>

int main(){
    std::list<int> numbers = {1,2,3,4,5};
    for (auto it = numbers.begin(); it !＝ numbers.end(); ++it) {
        std::cout << *it << std::endl;
    }

    return 0; 
}

範囲for文

C++では、C++11から、範囲for文が導入されました
範囲for文は、配列やコンテナの要素を順番に処理するために設計された構文のことをいいます

範囲for文は以下のように記述します

for(型名 変数名 : 範囲を表す値){

}

たとえば、以下のように記述したプログラムがあります

int value[] = {1,2,3,4,5};
for(int i=0;i<5;i++){
    std::cout << value[i] << std::endl;
}

これを範囲for文で書き換えてみましょう

int value[] = {1,2,3,4,5};
for(int elm : value){
    std::cout << elm << std::endl;
}
for(int elm : value){

範囲for文には繰り返しの回数の指定がありませんが、コンパイラは配列の大きさを知っているので、配列の終了までループが継続されます
int elmには、配列valueの先頭から順に取り出した値が代入されていきます

イテレーターを使用して取り出すプログラムは以下のように記述できます

#include <iostream>
#include <list>

int main(){
    std::list<int> numbers = {1,2,3,4,5};
    for (const auto& it : numbers) {
        std::cout << it << std::endl;
    }

    return 0; 
}

コンテナの場合、begin()およびend()で表されるイテレーターの組を利用して自動的にループが継続されます
範囲for文ではautoキーワードを積極的に使うと便利です
特に要素の型が複雑な場合や、テンプレートを使用している場合に、コードを簡潔に保つことができます
また、範囲for文で要素を扱う際、通常は要素の値がコピーされます
もしループ内で要素を変更したい場合や、大きなオブジェクトをコピーしたくない場合は、参照を使用するとよいでしょう
const auto& itと記述することで、コンテナ内の要素の変更を禁止することもできます

コメント

この記事へのコメントはありません。

関連記事

Python 応用編 4日目

Java 応用編 3日目

Java 応用編 7日目
PAGE TOP