テンプレートと STL

〜 Template and Standard Template Library 〜

Template and STL

〜 Template and Standard Template Library 〜

概要 Abstract
このページ(章)ではプログラムの「ひな型」であるテンプレートと, C++ に標準で用意されているテンプレートのライブラリ STL (Standard Template Library) について解説する. STL はベクタ(動的な配列)やリストと言った基本的なデータ構造を汎用的な形で実装しており,これらを使いこなせば, new や delete によるメモリ管理がほとんど不要になるほか,自分でデータ構造を一から書く必要がなくなるため,コード量が激減する.なお,テンプレートは C++ のみで使え, C では使えない.
In this page (chapter), explain about template which is "model" of program, and template library prepared as default in C++ STL (Standard Template Library). STL implements basic data structure such as vector (dynamic array) and list by general-purpose form, and if you have a good use of these, most of the memory managements by new and delete become needless and it is not necessary to write data structure from the beginning by yourself, so quantity of coding decreases sharply. In addition, template is usable only in C++, and si not usable in C.
目次 Table of contents

テンプレート Template

C++ は型つき言語であるため,処理が同じでも,型ごとに関数やクラスを作る必要がある場合がある.これを, 関数やクラスの「ひな型 (template)」を用意し,そのひな型から型に合った関数やクラスを生成すれば ,コードの重複を軽減できる.このようなしくみを, テンプレート と呼ぶ.

Because C++ is language with type, it is necessary to create function and class by every type even process is the same. If you Prepare "model (template)" of function and class to generate function and class in accord with type from the model, then you can reduce repetition of code. Call such a structure as template.

テンプレートにはテンプレート関数とテンプレートクラスの2種類がある.それぞれ関数のひな型とクラスのひな型であり,以下で順に解説する.

As for template, there are two kinds of template function and template class. These are models of function and models of class, and we explain it in the following sequentially.

テンプレート関数 Template function

テンプレート関数とは関数のひな型で,

Template function is model of function, and

  template <typename T>
  T function (const T &val1, double val2)
  {
    T r_val;
    T x, y;
    ...
    return r_val;
  }

のような記述をする.これは,関数 function の T 型に関するテンプレートを作るという意味で,この関数の宣言および関数の実装部では, T をひとつの型として使用できる.このようにして function を作れば, T を int とした function を生成することや, double とした function を生成することができる.つまり, T は「型のパラメタ」だと言える.

are described as this. This means that, create template about the Model T of function function. ANd you can use T as one type in declaration of this function and implementation part of function. If create function in this way, you can generate function which assumed T as int/double. In other words, T is "parameter of type".

作成したテンプレートを int 型として使うには, function<int>(15,2.0) などのように,関数名の後ろに <int> をつける.関数の引数は,その後に書く.ただし, 関数の引数から int が自明な場合は <int> を省略できる .この場合,引数の 15 から T=int が自明なので, function(15,2.0) と省略しても構わない.

To use created template as int type, use <int> behind function name like function<int>(15,2.0). Write argument of function afterwards. But, if int is self-evident from argument of function, you can omit <int>. In this case, because T=int is self-evident from 15 of argument, you may omit it as function(15,2.0).

例: Example:

  #include <iostream>
  using namespace std;
  template <typename T>
  T square(const T &val)
  {
    T ret = val*val;
    return ret;
  }

  int main(int argc, char**argv)
  {
    cout << "10^2 = " << square<int>(10) << endl;
    cout << "2.5^2 = " << square<double>(2.5) << endl;
    cout << "3^2 = " << square(3) << endl;
    return 0;
  }

結果

Result

10^2 = 100
2.5^2 = 6.25
3^2 = 9

これは二乗する関数をテンプレート関数にしたもので,テンプレートを使わなければ, int や double , float のそれぞれに対して square を定義しなければならない.関数の中身がもっと複雑になれば,よりコードを削減できる.

This is template function of function to square, and if you do not use template, you must define square for each int, double, float. If the contents of function are complicated more, you can reduce code more.

二つ以上の型をパラメタとしてテンプレートを作るには,

To create template as parameter is more than two types.

  template <typename T1, typename T2>

とする.関数本体の宣言と定義は T1 , T2 を使って書けばよい.使い方は function<int,double> などとする.

do as this. For declaration and definitions of the main body of function, you should write it using T1, T2. Use it as function<int,double>.

テンプレートクラス Template class

テンプレートクラスとはクラスのひな型である.型をパラメタにしてクラスを作るだけで,基本的にテンプレート関数と変わらない.テンプレートクラスの作り方はクラスの定義の前に template<typename T> を置くだけでよく,使い方はクラス名の後に <型> をつけるだけ,後は通常のクラスと同じ使い方ができる,という簡単なものだ.

Template class is model of class. It only create class with type as parameter, and is not different from template functions basically. How to make template classes is to have only to put template<typename T> before definitions of class, and how to use is to only use <type> after class name. You can use it as same as regular class other than that. It is simple.

テンプレートの例:

Example of template:

  #include <iostream>
  using namespace std;
  template <typename T>
  class Point
  {
  private:
    T x,y;
  public:
    Point (const T& x0, const T& y0)
        : x(x0), y(y0) // 初期値の代入
      {
        cout<<"("<<x<<", "<<y<<") の座標クラスを定義しました."<<endl;
      };
    void move (const T& dx, const T& dy)
      {
        x+=dx;
        y+=dy;
        cout<<"("<<x<<", "<<y<<") に移動しました."<<endl;
      };
  };

  int main(int argc, char**argv)
  {
    Point<int> p1(3,4);
    p1.move(2,2);
    Point<double> p2(0.5, 3.4);
    p2.move(-2.0,-10.0);
    return 0;
  }

結果

Result

 (3, 4) の座標クラスを定義しました.
 (5, 6) に移動しました.
 (0.5, 3.4) の座標クラスを定義しました.
 (-1.5, -6.6) に移動しました.

クラス Point は座標を記憶するクラスである.座標を int で定義する場合にも double で定義する場合にも対応させたいとき,それぞれについてクラスを作るよりも,上のようにテンプレートクラスを作って,そこから生成させた方が重複するコードが減る.

Class Point is class memorizing coordinate. If you want to handle when you define coordinate by int or define it by double, Create template class like above rather than create class about each, and create from it, then you can decrease duplicated code.

STL: Standard Template Library

STL はベクタ(動的な配列)やリストと言った基本的なデータ構造を汎用的な形,つまりどんな型のベクタやリストでも生成できるように,テンプレートクラスとして実装したライブラリである.ほかに,ソートなどのアルゴリズムもテンプレート関数として実装されている.これらのクラスや関数を使いこなすことで,面倒でデバッグのしにくいメモリの動的確保や開放をする必要がなくなったり,複雑なデータ構造(グラフなど)を簡単に作ったり,基本的なアルゴリズムを自分で実装する必要がなくなったりする.

STL is libraries implemented as template class to create basic data structure such as vector (dynamic array) and list even general-purpose form, in other words any type of vector and list. Otherwise, algorithms such as sort are implemented for template function, too. By having a good use of these classes and functions, it is not necessary to perform dynamic securing of memory which debug is difficult or release, and you can create complicated data structure (including graph) briefly, and it is not necessary to implement basic algorithm by yourself.

参考文献 Reference literature

以下では STL の基礎と簡単な例を解説するが,より STL を深く知りたい場合は,以下のソースを参照するとよい.

We explain the basics of STL and simple example in the following, but you should refer to the following sources when you want to learn STL deeply more.

  • ハーバート・シルト: STL 標準講座 -標準テンプレートライブラリを利用したC++プログラミング,翔泳社, 1999. Herbert Schildt: STL standard lecture - C++ programming using standard template library, Shoeisha, 1999.
  • STL Containers - C++ Reference, http://www.cplusplus.com/reference/stl/
    「STL 標準講座」は STL を勉強する標準的な本, "STL Containers - C++ Reference" は STL のリファレンスとして,クラスのメンバ検索とか関数の引数を調べるなどの用途で使える.
    "STL standard lecture" is as Standard book to study STL, and "STL Containers - C++ Reference" is as reference of STL. They can be used to search class member and examine function argument etc.

コンテナクラス Container class

コンテナクラスとは,ベクタ (vector) やリスト (list) などのデータ構造をテンプレートクラス化したものである.ほかにもいくつかのコンテナがあるが,以下では基本的で重要なこれらふたつを解説する.

Container class is that, sata structure such as vector (vector) and list (list) become template class. Otherwise, there are several containers. In the following, explain these two of basic and important.

ベクタ: vector Vector: vector

ベクタ (vector) とは動的な配列のことである.特徴は,配列と同じで メモリ空間上に連続に配置されている こと.このため,次のメリットとデメリットがある.

Vector is dynamic array. Its characteristic is that, it is placed onsecutively on memory space like array. Therefore, there are following merit and demerit.

  • メリット Merit
    • 連続に(先頭から順に)値を読み書きするのが極めて高速 It is extremely high-speed to read and write value for consecutive (from the head sequentially)
    • n 番目の要素に定数時間で (n に比例せずに) アクセスできる you can access it in fixed time (not in proportion to n) to n joint element
  • デメリット Demerit
    • 途中に挿入するためには,全要素数に比例した時間が必要 To insert it on the way, time proportional to total number of element is required.
    • 要素を追加するとき,連続しているメモリ領域を確保する必要があるため,データの再配置が行われる.これに,全要素数に比例した時間が必要.ただしこれを考慮して,メモリは余分に確保されている When adding element, it is necessary to secure continuing memory area, so relocation of data is performed. In this, time proportional to total number of element is required. But in consideration of this, extra memory is secured.

重要

Important

STL のベクタを使う前に,一度各自でベクタおよび次節のリストを実装してみることを奨める.これによって,ベクタやリストがなぜ上記のような性質を持つか理解できるだけでなく,メモリ管理のどのような点に注意すればよいかが理解できる.

ベクタは,

Vector

  #include <vector>

でライブラリを読み込んで,

reads library by this,

  vector<TYPE> a;

のように定義して使う.ここで TYPE はベクタの型で, int, double のような基本型のほか,自分で定義した構造体やクラスと言った複合型でもよい.さらに,ベクタであっても構わない. vector のサンプルプログラム:

then use it as this. Here, TYPE is type of vector, and it can be compound type such as structure, class which you defined, other than base type such as int, double. In addition, it can be vectors. Sample program of vector:

  #include <iostream>
  #include <vector>  // STL vector を使う
  #include <algorithm>  // STL アルゴリズムを使う
  using namespace std;
  template <typename T>
  void print_vector (const vector<T> &x) // vector x の中身を出力する
  {
  for(typename vector<T>::const_iterator itr(x.begin()); itr!=x.end(); ++itr)
      cout<<" "<<*itr;
    cout<<endl;
  }
  int main(int argc, char**argv)
  {
    vector<int> a(5);  // 要素数 5 のベクタを定義
    a[0]=1;  // 配列のように代入
    for(int i(1); i<5; ++i)
      a[i]=2*a[i-1];
    print_vector(a);
    int sum=0;
    // ポインタの変わりのイテレータを使って for ループを回す
    for(vector<int>::iterator itr(a.begin()); itr!=a.end(); ++itr)
      sum+=*itr;  // itr はポインタのように使える
      a.push_back(sum);  // a の末尾に sum を追加
      print_vector(a);
    reverse(a.begin(),a.end());  // a の順序を入れ換える STL のアルゴリズム
    print_vector(a);
    return 0;
  }

結果

Result

  1 2 4 8 16
  1 2 4 8 16 31
  31 16 8 4 2 1

プログラムで出てきた イテレータ(反復子) とは,ベクタクラスに対してポインタと同じ働きをするように定義されたクラスである.

iterator (replicator) in the program is defined class to work as same as pointer for vector class.

  • vector<int>::iterator itr : vector<int> 型のイテレータ vector<int>:: iterator itr : Iterator of vector<int> type
  • vector<int>::const_iterator itr : vector<int> 型の定数イテレータ (*itr に代入できない) vector<int>:: const_iterator itr : Constant iterator of vector<int> type (Cannot assign it to *itr)
  • a.begin() : a の先頭の要素へのイテレータを返す関数 a.begin() : Function to return iterator to top element of a
  • a.end() : a の末尾の要素へのイテレータを返す関数 a.end(): Function to return iterator to bottom element of a

イテレータを使う理由は,

Reason to use iterator is,

  • 連続に(順番に)アクセスする場合に,インデクスを使ったアクセスよりも高速 It has higher-speed than access using index when to access consecutively (in turn).
  • STL アルゴリズムで共通化ができる.例えば copy アルゴリズムで,リストの要素をベクタにコピーできるようになる Commonization is enabled in STL algorithm. For example, for copy algorithms, Element of list can be copied to vector. etc..

などだ.イテレータは list など,ほかのコンテナクラスでも定義されている.

Iterator is defined even in other container classes including list.

リスト: list List

ベクタと違って,リスト (list) はメモリ空間上に連続に配置されず, バラバラに置かれている .このバラバラのデータには 順序 があって,この順序にしたがって,各データは(少なくとも) 次のデータへのポインタ を持っている.このため,先頭のデータからすべてのデータをたどることができる.このようなデータ構造のことを一般的に リスト構造 と呼び,STLのリストコンテナ (list) はその汎用的な実装である.

Unlike vector, List (list) is not placed consecutively on memory space, but placed separately. These scattered data have order, and according to this order, each data (at least) have pointer to the following data. Therefore, we can search all data from top data. Usually, call such a data structure list structure, and list container (list) of STL is the general-purpose implementation.

リストは,そのデータ構造から,次のメリットとデメリットがある.

List has following merit and demerit from the data structure.

  • メリット Merit
    • 途中に要素を挿入する操作が定数時間で (n に比例せずに) 完了できる Operation to insert element in on the way can be completed by constant time (Without being in proportion to n)
    • 同様に,要素を追加するのも定数時間で完了する Similarly, it is completed by constant time to add element
    • 連続に(先頭から順に)値を読み書きするのがそこそこ高速. vector よりは,ポインタのインクリメントがある分,やや遅い It is high-speed reasonably to read and write value consecutively (from the head sequentially). It is slightly late than vector as there is increment of pointer.
  • デメリット Demerit
    • n 番目の要素にアクセスするとき, n に比例した時間が必要 When you access element of n joint, time proportional to n is required

ベクタ:vector の特徴と比較してみよう.どちらの方が効率的かは,アプリケーションに依存する.

Compare it with characteristics of vector. It depend on application which is more effective.

リストは,

For list,

  #include <list>

でライブラリを読み込んで,

read library in this, and

  list<TYPE> a;

のように定義して使う.ここで TYPE はベクタの型で, int, double のような基本型のほか,自分で定義した構造体やクラスと言った複合型でもよい.さらに,リストやベクタであっても構わない.

define as this to use. Here, TYPE can be type of vector, base type such as int, double, compound type such as structure and class you defined. In addition, list and vectors is OK.

list のサンプルプログラム:

Sample program of list:

  #include <iostream>
  #include <list>  // STL list を使う
  #include <algorithm>  // STL アルゴリズムを使う
  using namespace std;
  template <typename T>
  void print_list (const list<T> &x) // list x の中身を出力する
  {
    for(typename list<T>::const_iterator itr(x.begin()); itr!=x.end(); ++itr)
      cout<<" "<<*itr;
    cout<<endl;
  }
  int main(int argc, char**argv)
  {
    list<int> a;  // list を定義
    for(int i(0); i<5; ++i)
    a.push_back(i*i);  // a の末尾に i*i を追加
    print_list(a);
    int sum=0;
    // ポインタの変わりのイテレータを使って for ループを回す
    for(list<int>::iterator itr(a.begin()); itr!=a.end(); ++itr)
      sum+=*itr;  // itr はポインタのように使える
    a.push_back(sum);  // a の末尾に sum を追加
    print_list(a);
    reverse(a.begin(),a.end());  // a の順序を入れ換える STL のアルゴリズム
    print_list(a);
    return 0;
  }

結果

Result

  0 1 4 9 16
  0 1 4 9 16 30
  30 16 9 4 1 0

list は vector とほとんど同じインターフェイスを提供していることがわかる.ただし list は, vector のような配列アクセス (a[5] など) ができない.これはリストのデータがメモリ空間上に連続して配置されていないためだ.

You can find that list is providing interface almost same as vector. But in list, array access(including a[5]) such as vector cannot be used. That is because data of list are not placed on memory space in succession.

アルゴリズム Algorithm

STL はソートなどのアルゴリズムを汎用的に使えるようにした,テンプレート関数も提供している. vector の例で使った reverse も STL アルゴリズムのひとつだ.便利なものが多いので,

For STL, template function, to use algorithms such as sort universally, is provided. reverse which you used in example of vector is one of the STL algorithms. Because there are many convenient things,

などを調べてみるとよい.

You should examine as this.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-03-15 (金) 11:19:42 (1952d)