🫥

CPP MODULES 08 : Templated containers, iterators, algorithms

に公開
C++
module
container
iterator
temprate
tech

Exercise 00: Easy find

C++98でのeasyfind課題 – STLを活用して効率的なプログラムを実装しよう

概要

この課題では、C++98におけるテンプレートプログラミングとSTL（標準テンプレートライブラリ）を活用して、特定の整数をコンテナ内で見つける関数テンプレートeasyfindを実装します。課題の目的は、STLコンテナ（vector、listなど）やアルゴリズムを適切に使用し、C++の基本的な機能を駆使して効率的で読みやすいコードを書くことです。

課題の要件

  • テンプレート関数easyfindを実装し、整数を保持するコンテナから指定された値を見つける。
  • 見つからない場合は、例外を投げるか適切なエラーメッセージを返す。
  • STLのコンテナとアルゴリズムをできるだけ活用すること。
  • 実装した関数をテストするためのプログラムを作成すること。

重要なポイント

  1. STLのコンテナとアルゴリズムの活用:

    • この課題では、std::vectorやstd::listのようなSTLコンテナを使用することで、効率的なデータ操作を行います。また、std::findなどのSTLアルゴリズムを利用することで、複雑なロジックを簡潔に実装できます。

  2. テンプレートプログラミング:

    • テンプレート関数は、異なる型のデータに対して共通の処理を記述できる強力な機能です。easyfind関数は、Tという型パラメータを使用して、任意の整数コンテナに対応できるよう設計されています。

  3. 例外処理:

    • 見つからない場合に例外を投げることで、エラー処理を適切に行います。これにより、呼び出し側でエラーをキャッチして、プログラムを柔軟に制御できます。例外処理は堅牢なコードを書く上で不可欠です。

C++の動的配列とリスト

プログラムの構成

  • easyfind.hpp:

    • easyfind関数テンプレートを定義し、STLのstd::findを使って指定された値を検索します。見つからなければstd::runtime_error例外を投げます。

  • main.cpp:

    • easyfind関数の動作をテストするため、std::vectorやstd::listを使って、正常系と異常系の両方をテストします。見つかった場合は値を出力し、見つからない場合は例外をキャッチしてエラーメッセージを表示します。

実装コード

easyfind.hpp:

#ifndef EASYFIND_HPP
#define EASYFIND_HPP

#include <algorithm>
#include <iterator>
#include <exception>
#include <iostream>

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    typename T::iterator it = std::find(container.begin(), container.end(), value);
    if (it == container.end()) {
        throw std::runtime_error("Value not found in the container");
    }
    return it;
}

#endif

main.cpp:

#include "easyfind.hpp"
#include <vector>
#include <list>
#include <iostream>

int main() {
    std::vector<int> vec;
    for (int i = 1; i <= 10; ++i) {
        vec.push_back(i);
    }

    try {
        std::vector<int>::iterator it = easyfind(vec, 5);
        std::cout << "Value found in vector: " << *it << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }

    try {
        std::vector<int>::iterator it = easyfind(vec, 15);
        std::cout << "Value found in vector: " << *it << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }

    return 0;
}

学べるポイント

  1. STLの基礎:

    • std::vectorやstd::listなどのSTLコンテナを活用することで、効率的なデータ構造の利用方法を学べます。
    • std::findのようなアルゴリズムを使用することで、簡潔なコードで強力な操作が可能になります。

  2. テンプレートプログラミング:

    • template <typename T>の書き方や、コンテナに依存しない汎用的な関数の実装方法を学べます。

  3. 例外処理の実践:

    • C++のtry-catchブロックを使って、例外を処理し、プログラムの堅牢性を向上させる方法を体験できます。

  4. C++98の制約:

    • C++98の範囲内で標準ライブラリを活用する方法を学び、よりモダンなC++と比較した際の理解が深まります。

まとめ

この課題を通じて、C++98におけるSTLのコンテナとアルゴリズムの活用、テンプレートプログラミング、そして例外処理の基礎を学ぶことができます。easyfindの実装とテストは、STLの強力さを理解し、エンジニアとして効率的なプログラムを構築するための第一歩となります。

Exercise 01: Span

C++98でのSpanクラス実装 – 効率的なSTLの活用とアルゴリズムの実践

概要

この課題は、C++98の範囲でSpanクラスを実装し、効率的に整数の範囲（スパン）を管理し、最小および最大のスパンを見つけることを目的としています。STL（標準テンプレートライブラリ）を活用することで、コンテナ操作やアルゴリズムを用いた効率的なプログラミングのスキルを身につけることができます。

課題の要件

  1. Spanクラスの実装:

    • N個の整数を格納できるクラスを作成する（Nはコンストラクタで指定）。
    • 数値を追加するaddNumber()メンバ関数を実装し、既にN個の整数が格納されている場合は例外を投げる。
    • 最小スパンを求めるshortestSpan()と最大スパンを求めるlongestSpan()メンバ関数を実装し、要素が1つ以下しかない場合は例外を投げる。

  2. 大量の要素を効率的に追加する:

    • イテレータ範囲を使って複数の要素を一度に追加するメンバ関数を実装。

  3. STLのコンテナとアルゴリズムの活用:

    • STLのvectorやalgorithmヘッダを活用して、要素の追加やスパンの計算を効率的に行う。

実装のポイント

  1. std::vectorの使用:

    • std::vectorは動的な配列として機能し、要素を格納するためのメインコンテナとして使用します。可変長のデータ構造であり、格納の順序を保持するため、今回のような課題に適しています。

  2. std::sortによる並べ替え:

    • shortestSpan()メソッドでは、全要素をソートした上で、隣接する要素間の最小差を計算するためにstd::sortを使用します。ソート後、ループを用いて最小差を求めます。

  3. std::min_elementとstd::max_element:

    • longestSpan()メソッドでは、コンテナ内の最小値と最大値を見つけるためにstd::min_elementとstd::max_elementを使用し、それらの差を求めることで最大スパンを計算します。

  4. 例外処理:

    • 数値の追加が上限を超えた場合や、要素数が不足している場合に例外を投げることで、エラー状態を適切にハンドリングします。これにより、コードの堅牢性が向上します。

  5. イテレータの使用:

    • イテレータを用いて範囲指定で数値を追加するメソッドを実装し、STLの柔軟な機能を活用しています。これにより、大量の数値を一度に効率的に追加できます。

学べるポイント

  1. STLコンテナの操作:

    • std::vectorを用いた動的な配列操作や、要素の追加・管理方法を学びます。

  2. STLアルゴリズムの活用:

    • std::sort、std::min_element、std::max_elementといったSTLアルゴリズムを使用することで、複雑なロジックを簡潔かつ効率的に実装できます。

  3. 例外処理と安全なコード:

    • 適切なエラーハンドリングを行うことで、安全で堅牢なプログラムの実装方法を学べます。例外処理を用いたエラーメッセージの表示や、エラー時のプログラムの制御方法も理解できます。

  4. イテレータ範囲の活用:

    • イテレータを使った範囲指定での要素追加により、STLの高度な機能を学び、効率的なプログラムを書くスキルを身につけます。

  5. C++98の特性を理解:

    • C++98の範囲でSTLを活用することにより、モダンC++との違いを理解し、より新しい標準への移行時に役立ちます。

プログラムの全体像

  • Spanクラス:

    • N個の整数を格納するためのクラス。
    • addNumber()メソッドで単一の数値を追加。
    • イテレータ範囲で複数の要素を追加するメソッドも実装。
    • 最小・最大のスパンを求めるメソッドを実装。

  • 例外の処理:

    • コンテナが満杯になった場合や、スパンを計算する要素数が足りない場合に例外を投げ、適切にエラー処理を行う。
    • C++のテンプレート関数は、ヘッダファイルで完全に定義されている必要があります。Span.hppの中でテンプレート関数の定義も含めるか、.tppファイルを使ってインクルードする必要があります。

この課題を通じて、C++98のSTLのコンテナ操作、アルゴリズムの活用、そして例外処理に関するスキルを強化できます。これらは日々の開発において非常に重要なスキルであり、効率的で安全なプログラムを構築するための基礎を提供します。

Exercise 02: Mutated abomination

C++98でのMutantStackクラス実装 – イテレータ機能を持つスタックを作ろう

概要

C++のstd::stackはLIFO（Last In, First Out）のデータ構造を提供し、標準ライブラリの中でも便利なコンテナの一つです。しかし、std::stackはイテレータを提供していないため、スタック全体を直接走査することはできません。この課題では、std::stackを拡張してイテレータ機能を持つMutantStackクラスを実装します。このクラスは通常のstd::stackの機能に加えて、イテレータを使用してスタックを走査することができます。

重要なポイント

  1. std::stackの特徴:

    • std::stackはコンテナアダプタで、デフォルトではstd::dequeを基底コンテナとして使用しています。std::stackはpush、pop、top、sizeといったメンバ関数を提供していますが、イテレータは提供していません。

  2. イテレータの追加:

    • MutantStackクラスではstd::stackを継承し、内部のコンテナにアクセスすることで、イテレータを提供します。
    • this->cはstd::stackが保持している基底コンテナにアクセスするためのプロテクトメンバで、begin()やend()メソッドを定義することでイテレータを提供します。

  3. クラスの型エイリアス:

    • std::stackが使用している基底コンテナの型を利用し、iterator、const_iterator、reverse_iteratorなどの型エイリアスを定義して、MutantStackが持つべきイテレータを簡単に提供できるようにしています。

  4. テストの実施:

    • 実装をテストするために、MutantStackクラスと標準のstd::listを比較し、同様の操作で出力が一致することを確認します。これにより、MutantStackの実装が正しく動作することを保証します。

実装方法

MutantStackクラスは、以下のようにしてstd::stackを継承し、イテレータを提供するためのメソッドを追加します。

template <typename T>
class MutantStack : public std::stack<T> {
public:
    typedef typename std::stack<T>::container_type::iterator iterator;
    typedef typename std::stack<T>::container_type::const_iterator const_iterator;
    typedef typename std::stack<T>::container_type::reverse_iterator reverse_iterator;
    typedef typename std::stack<T>::container_type::const_reverse_iterator const_reverse_iterator;

    iterator begin() {
        return this->c.begin();
    }

    iterator end() {
        return this->c.end();
    }

    const_iterator begin() const {
        return this->c.begin();
    }

    const_iterator end() const {
        return this->c.end();
    }

    reverse_iterator rbegin() {
        return this->c.rbegin();
    }

    reverse_iterator rend() {
        return this->c.rend();
    }

    const_reverse_iterator rbegin() const {
        return this->c.rbegin();
    }

    const_reverse_iterator rend() const {
        return this->c.rend();
    }
};

main.cppでのテスト

main.cppでは、MutantStackクラスを使用してスタックを操作し、スタック全体をイテレータで走査できることを確認します。また、std::listを使って同じテストを行い、結果が一致することを検証します。

int main() {
    MutantStack<int> mstack;
    mstack.push(5);
    mstack.push(17);
    std::cout << "Top element: " << mstack.top() << std::endl;
    mstack.pop();
    std::cout << "Size after pop: " << mstack.size() << std::endl;
    mstack.push(3);
    mstack.push(5);
    mstack.push(737);
    mstack.push(0);

    std::cout << "MutantStack contents: ";
    for (MutantStack<int>::iterator it = mstack.begin(); it != mstack.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 同様の動作をstd::listでテスト
    std::list<int> lst;
    lst.push_back(5);
    lst.push_back(17);
    lst.pop_back();
    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(737);
    lst.push_back(0);

    std::cout << "List contents: ";
    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

学べるポイント

  1. STLコンテナの継承と拡張:

    • std::stackを拡張し、機能を追加することで、STLのコンテナをカスタマイズして特定のニーズに合わせる方法を学べます。

  2. イテレータの概念:

    • イテレータを使用することで、コンテナの要素を順番に処理する方法を学び、STL全体に共通するイテレータの利便性を理解できます。

  3. テンプレートプログラミング:

    • クラステンプレートを使用して任意の型に対応するクラスを実装することで、ジェネリックプログラミングの基本を学びます。

  4. STLの内部構造への理解:

    • std::stackの内部のコンテナにアクセスし、それを利用して新たな機能を追加する方法を通じて、STLのデザインパターンや内部構造への理解が深まります。

まとめ

この課題を通じて、STLコンテナの拡張方法、イテレータの追加、テンプレートクラスの設計を学ぶことができます。MutantStackは、std::stackの限界を補完する形で作成され、標準ライブラリのコンテナのカスタマイズ方法を理解するための素晴らしい練習になります。これにより、C++プログラムにおける効率的で拡張性のある設計が身につきます。

Discussion