C++テンプレートと標準ライブラリ勉強日記

きっかけは、図書館で借りた「標準C++ライブラリチュートリアル＆リファレンス(ASCII)」でした。
はじめの方にテンプレートが載っているのですが・・・忘れた・・・というか、わからない・・・というか、わかっていたのか？・・・型汎用性くらいだけはなんとか・・・

はじめのサンプルとしては、以下のようなものが有名なようです。

1. ２つの引数の大きい方を返すMAX関数
2. ２つの引数の交換をするSWAP関数

実装時の注意　（チュートリアル＆リファレンスよりP30）

ヘッダファイルでインライン関数を使って実装する方法しかない。
(exportを使って、実装部と分離する方法もあるが、一般的ではないらしい)

//関数テンプレート max と swap
#include <iostream>

template <typename T>
inline const T& max(const T& a, const T& b)
{
	return a < b ? b : a;
}

template <typename T>
inline void swap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}

int main(void)
{
	int a=4, b=5;
	std::cout << "a= " << a << " b= " << b << std::endl;

	std::cout << max(a,b) << std::endl;			//大きい方を表示
	swap(a,b);						//交換

	std::cout << "a= " << a << " b= " << b << std::endl;
	return 0;
}

実行結果
a= 4 b= 5
5
a= 5 b= 4

このあたりは、見れば思い出せる・・・
次回以降は、Stroustrup著のプログラミング言語C++第3版を参考にしていく予定。

Stroustrup著プログラミング言語C++第3版。P388
標準ライブラリを利用した語数計算プログラムですが、出力コードが載っていないので、自分で書き足してみました。イテレータを使ってFOR文でまわしてます。
for_eachなどで出力すればスマートなのでしょうが、わからないんです。

//標準ライブラリを利用したテンプレートの使用例：語数計算
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(void)
{
	string buf;
	map<string, int> m;
	while (cin >> buf) m[buf]++;
	
	for ( map<string, int>::iterator ite = m.begin(); ite != m.end(); ++ite) {
		cout <<"key: " << (*ite).first << "\t語数: " << (*ite).second << endl;
	}
	return 0;
}

実行は標準入力からキー入力してCTRL+Zで中断すると、KEYと語数が出力されます。

実行例はファイルをリダイレクトしています。

実行例（実行ファイル名 < 読み込みファイル名）
D:\C++実験>template2 < template2.cpp
key: != 語数: 1
key: "  語数: 2
key: "\t語数:   語数: 1
key: #include   語数: 3
key: (  語数: 1
key: (*ite).first       語数: 1
key: (*ite).second      語数: 1
key: (cin       語数: 1
key: ++ite)     語数: 1
・・・・
以下続く

mapなどの連想配列はPerlをやったら、ピンとくるようになった。
今日は、関数オブジェクトなどで行き詰った記憶がよみがえった・・・
C++は難しいなあ

Stroustrup著プログラミング言語C++第3版。P388
宣言の外で定義する記述方法が書いてある。しかし、テンプレートはヘッダファイルにインライン関数で書かれるため、このように書くことは、あまり無さそうだ。
コードの例は、11章のStringクラスを使っている。
このあとも出てきそうなので、必要な部分を作りながら、確認していくことにした。

Stringクラスを書くのは大変なので、Stringクラスの内部にあるSrepクラス(構造体)を作ることにした。
Srep構造体とStringクラスはP347に載っている。

1. 実際の型(char*)で記述する。
2. テンプレート化する。

//Srep構造体。テンプレートにする前にchar型で記述
//csrep.h
#ifndef CSREP_H_TEMPLATE_20040814_SUNA
#define CSREP_H_TEMPLATE_20040814_SUNA

struct Srep {
		char* str;		//要素へのポインタ
		int size;		//要素の数
		int count;		//参照カウンタ
		
	//コンストラクタ、デストラクタ
	Srep(int isize, const char* istr)
	{
		count = 1;
		size = isize;
		str = new char[size+1];
		strcpy(str, istr);
	}
	~Srep() { delete[] str; }
private:
	//コピーの禁止(コピーコンストラクタとコピー代入演算子を禁止する)
	Srep(const Srep& );
	Srep& operator=(const Srep&);
};
#endif //CSREP_H_TEMPLATE_20040814_SUNA

//テンプレートにする前にchar型で記述
#include <iostream>
#include "csrep.h"
using namespace std;

int main(void)
{
	char* input= "こんにちは、ぼくどらえもn";
	Srep n(strlen(input), input);
	
	cout << n.str << endl;
	cout << "サイズ：" << n.size << endl;

	return 0;
}

以下、テンプレート化したもの。定義を宣言の外に書いた。

//Srep構造体。テンプレート化
//csrep.h
#ifndef CSREP_T_H_TEMPLATE_20040814_
#define CSREP_T_H_TEMPLATE_20040814_

template <typename C>
struct Srep {
		C* str;		//要素へのポインタ
		int size;		//要素の数
		int count;		//参照カウンタ
		
	//コンストラクタ、デストラクタ
	Srep(int isize, const C* istr);
	~Srep();
private:
	//コピーの禁止(コピーコンストラクタとコピー代入演算子を禁止する)
	Srep(const Srep& );
	Srep& operator=(const Srep&);
};
//定義
template<typename C> Srep<C>::Srep(int isize, const C* istr)
{
	count = 1;
	size = isize;
	str = new char[size+1];
	strcpy(str, istr);
}
template<typename C> Srep<C>::~Srep() { delete[] str; }

#endif //CSREP_T_H_TEMPLATE_20040814_

//テンプレート実行ファイル
#include <iostream>
#include "csrep_t.h"
using namespace std;

int main(void)
{
	char* input= "こんにちは、ぼくどらえもn";
	Srep<char> n(strlen(input), input);
	
	cout << n.str << endl;
	cout << "サイズ：" << n.size << endl;

	return 0;
}

実行例はテンプレート化前と同じ。

Stroustrup著プログラミング言語C++第3版。P390
テンプレート引数の文はちょっとわかりづらい。
Buffer<char, 10> とBuffer<char, 20>は違う型になるようだ。

ネットワークプログラミングの勉強をしてたら、バイトオーダーが気になったので、 アドレス配置を知るために書いてみた。ビット表記をするのにbitsetを使った。

//byteorder.cpp bitsetを使う。ネットワークバイトオーダー
//2004/8/15 
#include <iostream>
#include <iomanip>
#include <bitset>
#include <winsock2>
using namespace std;

int main(void)
{
	union uIP {
		unsigned long lv;
		unsigned char v[4];
	};

	uIP ip;
	ip.lv = 0xc0a8000f;		//192.168.0.15の16進数表記
	for (int i=0; i < 4; ++i) {
		bitset<8> bit = ip.v[i];
		cout << i <<" ：アドレス0x" << (int)&(ip.v[i])
			<< " 値:" << setw(4) << (int)ip.v[i]
			<< ": ビット列:" << bit << endl;
	}
	cout << " 16進:0x" << hex << setw(8) << setfill('0') << ip.lv << endl;

	bitset<32> order(ip.lv);
	cout << "CPUの並び:"  << order << endl;

	bitset<32> netorder(htonl(ip.lv));
	cout << "network　:" << netorder << endl;
		
	return 0;
} 

実行例
0 ：アドレス0x1244980 値:  15: ビット列:00001111
1 ：アドレス0x1244981 値:   0: ビット列:00000000
2 ：アドレス0x1244982 値: 168: ビット列:10101000
3 ：アドレス0x1244983 値: 192: ビット列:11000000
 16進:0xc0a8000f
CPUの並び:11000000101010000000000000001111
network　:00001111000000001010100011000000

IPアドレスとして、192.168.0.15を入れた。
IPアドレスは、上位アドレスから順に配置され、上位アドレスから読み込んでいる。
ネットワークバイトオーダーに変換すると、バイト配置が逆になった。
ネットワークバイトオーダーでは、ビットの読み方向も反対になるので、
newwork:11110000000000000001010100000011を反対から読むことになるようだ。

Stroustrup著プログラミング言語C++第3版。をもとに進めようとしているが、 サンプルコードが省略されているので、非常に進めづらい。
P405のVectorのswapを試そうと思ったがやっていることがよくわからず・・・苦しい。力不足だなあ

テンプレートの基本的なところは、大体わかったとおもうので、明日からはC++標準ライブラリチュートリアル＆リファレンスを読んでいくつもり。

P29のmax関数は、日記の初めの方でやった。

bitset<8>とbitset<16>は違う型になる。P30

代入や比較を行う場合には、適切な型変換関数を定義する必要がある。

デフォルトのテンプレート引数。P31

template <class T, class container = vector<T> > class MYC
初めのTが、その次のvector<T>に渡される。

typenameキーワード。P31

typename T::subtype
subtypeが型であることを示す。typenameが無いと、メンバのように解釈され、メンバ変数のように扱われる。
これは、知らなかった。または忘れていた。
subtypeを型か数値かを判別できないらしい。

メンバテンプレート。P32

メンバ関数を関数テンプレートにする場合、仮想関数であってはならない。デフォルト引数を持つこともできない。
テンプレートコンストラクタは、暗黙的な型変換が可能になるように提供される。
この辺はちょっとよくわからない。

以下、２章は読み飛ばし。3章の例外処理に進む。

言語、ライブラリの全ての例外クラスは、exceptionクラスを基本クラスとする。P46

例外クラスは、次の3種類に分類される。
1.言語をサポートするための例外。
2.標準ライブラリのための例外。
3.プログラムのスコープの外で発生するエラーのための例外。
exceptionクラスのヘッダファイルは<exception>。

言語をサポートするための例外。P47

bad_allocクラス <new>ヘッダファイル

newが失敗した時に送出。

bad_castクラス <typeinfo>ヘッダファイル

dynamic_castによる型変換が失敗した時に送出。

bad_typeidクラス <typeinfo>ヘッダファイル

typeid演算子の引数が0またはNULLポインタであるときに送出。

bad_exceptionクラス <exception>ヘッダファイル

予期しない例外の時に送出。例外指定に違反した時など。
例外指定：f() throw(E); //E型の例外だけを送出する例外指定。
このときに関数内部で、EA型の例外が送出された時、例外指定違反となる。
例外指定違反の場合、unexpected()関数が呼び出され、unexpected()の内部でterminate()を呼び出しプログラムを終了させる。
f() throw(E, std::bad_exception); のように、bad_exceptionが含まれる時にEA型の例外指定違反があった場合、unexpected()はbad_exceptionを送出する。

標準ライブラリのための例外。P48

logic_errorクラスから派生する。関数の引数チェックのために使われるらしい。

invalid_argumentクラス

不正な引数。よくわからない。

length_errorクラス

許可される最大サイズを超えるような処理の試みを通知する。

out_of_rangeクラス

引数の値が有効範囲外であることを通知する。

domain_errorクラス

定義域エラー？わからない。

ios_base::failureクラス <ios>ヘッダファイル

入出力のエラー、EOFによってストリームの状態が変化する時に送出。

プログラムのスコープの外で発生するエラーのための例外。P48

runtime_errorクラスから派生する。

range_errorクラス

内部演算における範囲エラーを通知する。

overflow_errorクラス

数値演算のオーバーフローを通知する。

underflow_errorクラス

数値演算のアンダーフローを通知する。 ヘッダファイルが記述されていないものは、<stdexcept>で定義されている。

標準ライブラリ自体は、range_error, out_of_range, invalid_argumentの例外を送出する。
コードの移植性のためにも、標準の例外クラスだけを使うべき。

ユーザーが送出できる標準の例外 P50

logic_errorクラスとその派生クラス
runtime_errorクラスとその派生クラス
ios_base::failureクラス

使い方
throw std::out_of_range(const stirng& s)
sにwhat()で呼び出されるメッセージを格納できる。

例外は、使ったことがない。
次回は第4章。

pair構造体<utility>

sutructなので、first, secondは、パブリックメンバ変数

コンストラクタで =int()などの初期化が行われる。P54

デフォルトコンストラクタは、pair():first(T1()),second(T2()){}
なので
pair<int, double> p;
とすると、int(),double()が呼ばれる。どちらも0で初期化される。

コピーコンストラクタは暗黙の型変換を提供する。P55（テンプレートコンストラクタ）

template <class U, class V>
pair(const pair<U,V>& p):first(p.first), second(p.second){}

引数の型が一致しない時はこのコピーコンストラクタが呼び出され、
引数の型が一致する時は、組み込みのコピーコンストラクタが呼ばれる。

テンプレートコンストラクタの確認
pairはstd::pairと名前がかぶるので、sun名前空間で定義した。

//C++チュートリアル＆リファレンスのP55 
//テンプレートコンストラクタの確認
//2004/8/18
#include <iostream>
using namespace std;

namespace sun{
template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;

	T1 first;
	T2 second;
	pair(const T1& a, const T2& b) : first(a), second(b) {
	cout << "D引数コンストラクタ" << endl;
	}
	pair()
	  : first(T1()), second(T2()) {
	cout << "Dデフォルトコンストラクタ" << endl;
	}
/*	コメントアウト。組み込みのコピーコンストラクタを使う。
	pair(const pair& p) 
	  : first(p.first), second(p.second){
		cout << "コピーコンストラクタ" <<  endl;
	}
*/
	template <class U, class V> pair(const pair<U,V>& p) 
	  : first(p.first), second(p.second){
		 cout << "テンプレートコンストラクタ" <<  endl;
	}
};
}

int main(void)
{
	sun::pair<int, double> p;
	cout << "同じ型" << endl;
	sun::pair<int, double> p1 = p;
	cout << "違う型" << endl;
	sun::pair<int, float> p2 = p;
	return 0;
}

実行例
Dデフォルトコンストラクタ
同じ型
違う型
テンプレートコンストラクタ

違う型の時には、テンプレートコンストラクタが呼ばれている。
コピーコンストラクタのコメントアウトをはずすと、同じ型の時、このコピーコンストラクタが呼ばれた。

make_pair

暗黙の型変換には、テンプレートコンストラクタが呼ばれている。

//C++チュートリアル＆ライブラリのP56 
//make_pair
//2004/8/18
#include <iostream>
#include <utility>
using namespace std;
namespace sun{
template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;

	T1 first;
	T2 second;
	pair(const T1& a, const T2& b) : first(a), second(b) {
	cout << "D引数コンストラクタ" << endl;
	}
	pair()
	  : first(T1()), second(T2()) {
	cout << "Dデフォルトコンストラクタ" << endl;
	}

	pair(const pair& p) 
	  : first(p.first), second(p.second){
		cout << "コピーコンストラクタ" <<  endl;
	}

	template <class U, class V> pair(const pair<U,V>& p) 
	  : first(p.first), second(p.second){
		 cout << "テンプレートコンストラクタ" <<  endl;
	}
};
/* make_pair関数 */
	template <class T1, class T2>
	pair<T1, T2> make_pair(const T1& x, const T2& y) {
		return pair<T1, T2>(x, y);
	}
}

void f(sun::pair<int,double>) {
	cout << "function f" << endl;
}
int main(void)
{
	cout << "引数:int,double 一時オブジェクトを作成" << endl;
	f(sun::make_pair(4,5.6));
	cout << "\n引数:int,int 一時オブジェクトをさらに型変換している。" << endl;
	f(sun::make_pair(4,5));
	cout << "\n引数:int,double(型指定)" << endl;
	f(sun::pair<int,double>(4,5));
	cout << "\n引数:int,float(型指定) これも型変換している。" << endl;
	f(sun::pair<int,float>(4,5));
	return 0;
}

実行結果
引数:int,double 一時オブジェクトを作成
D引数コンストラクタ
function f

引数:int,int 一時オブジェクトをさらに型変換している。
D引数コンストラクタ
テンプレートコンストラクタ
function f

引数:int,double(型指定)
D引数コンストラクタ
function f

引数:int,float(型指定)
D引数コンストラクタ
テンプレートコンストラクタ
function f

auto_ptr <memory> P57

auto_ptrはMoreEffectiveC++で出てきたが、さらっと読むだけしかできなかった。
auto_ptrはC++3rdP430にものっている。
例外処理の、delete処理の面倒をなくすもの

auto_ptrの初期化 P59

std::auto_ptr<ClassA> ptr1(new ClassA) //OK
std::auto_ptr<ClassA> ptr2 = new ClassA //エラー
上は明示的な型変換、下は暗黙の型変換を行う。暗黙の型変換には失敗する。

auto_ptrのコピー代入演算子は、所有権の移動を行う。P60

ポインタの移動が行われ、コピー前のauto_ptrはNULLを指す。
コピー代入演算子は、auto_ptr型を受け取らなければならず、通常のポインタは代入できない。

const auto_ptr

オブジェクトの所有権移動を行いたくなければ、const auto_ptrとして宣言する。

auto_ptrは配列に使うことはできない。

auto_ptrが、所有するオブジェクトに対して呼び出すのはdeleteであり、delete[]ではない。
かわりにコンテナクラスを使う。

auto_ptrはコンテナの要素としての条件を満たしていない。

標準コンテナの要素として、代入できない。
標準に準拠する環境では、コンパイル時にエラーなる。

auto_ptr_refのあたりは特殊な型変換だということだが、今の自分のレベルでは、何をやっているのかわからない。後で考えよう。以下引用

auto_ptrクラスの残り(補助型のauto_ptr_refとこれを使う関数群)は、 コピーコンストラクタと代入演算を定数ではないauto_ptrには使用可能にし、 定数のauto_ptrには使用できないようにするという少しトリッキーな変換を行う。 (詳細については、61ページの注意点を参照)続いて簡単に説明するが、要件は次の２つである。

1. auto_ptrを関数との間でrvalueとして渡すことが可能であること。 auto_ptrはクラスであるため、コンストラクタを使ってこの処理を行わなければならない。
2. auto_ptrがコピーされるときは、ソース側のポインタの所有権を獲得することが重要である。 つまり、コピーではソース側のauto_ptrの変更が要求される。

通常のコピーコンストラクタはrvalueをコピーできるが、そのためにはコピーコンストラクタの引数をconstオブジェクトの参照として宣言する。(補足:auto_ptr(const auto_ptr & a)) 通常のコンストラクタを使ってauto_ptrをコピーするには、 実ポインタを含むデータメンバをmutableで宣言し、コピーコンストラクタで変更されるようにする。 しかし、このように宣言すると、実際にはcosntで宣言されているauto_ptrをコピーするコードの記述が可能になり、状態が変化しない定数として宣言しているのに所有権が渡されてしまう。(補足:const auto_ptrなのに所有権が渡されてしまう。)

代わりに、rvalueをlvalueに変換する仕組みを探そう。単純に参照型へ変換する演算子変換関数ではうまくいかない。 オブジェクトをオブジェクトそのものの型に変換するために演算子変換関数が呼び出されることはないからだ(参照の属性は型に含まれていないことを思い出してほしい)。 そこで、「lvalueへの変換」機能を提供するためにauto_ptr_refクラスが導入された。 この機能は、オーバーロードとテンプレート引数の推測の微妙な違いに依存する。この２つの機能の違いは一般的なプログラミングツールとして使うには微妙すぎるが、auto_ptrクラスを正しく動作させるには十分である。

コンパイラが、定数ではないauto_ptrと定数のauto_ptrを区別しなくても、驚かないでほしい。しかし、コンパイラがその違いを実装していないと、auto_ptrのインターフェイスの危険性が大きくなる。この場合、間違って所有権を譲渡することが多くなる。

numeric_limits <limits> P75

これの定数は、整数型<climits><limits.h>
浮動小数点型は<cfloat><float.h>で、記述されている。

補助関数 P81

max, min <algorithm>

template <class T> max(const T& a, const T& b)
template <class T> min(const T& a, const T& b)

max, min 比較の式を与える。<algorithm>

template <class T, class Compare> max(const T& a, const T& b, Compare comp)
template <class T, class Compare> min(const T& a, const T& b, Compare comp) <algorithm>

swap <algorithm>

値を直接交換する代わりに、swap()を呼び出すことによりパフォーマンスが大幅に向上することがある。ユーザー定義型にもswapの特別バージョンを実装するべき。

比較演算子 <utility>

==と<を定義すれば、!=, >, <=, >=は、std::rel_ops名前空間で定義される。
これは楽そうだ。

<cstddef>

NULL	cでは、void* 0,c++では、整数の0
size_t	サイズの単位。bccでは、unsigned int
ptrdiff_t	ポインタの差をあらわす型。bccではint
offsetof()	（構造体、または共用体のメンバのオフセット）の定義。 bccではoffsetof( s_name, m_name ) (_SIZE_T)&(((s_name _FAR *)0)->m_name)

bcc32では、最終的にはNULLは_null.hで定義されていた。

<cstdlib>

exit(int)	プログラムを終了する。 静的なオブジェクトの削除、バッファのフラッシュ、入出力チャンネルのクローズを完全に行う。 atexit()で登録された関数の実行を行う。
EXIT_SUCCESS	プログラムの正常終了。bccでは0
EXIT_FAILURE	プログラムの異常終了。bccでは1
abort()	プログラムを中断する。後処理を行うことなく、即座にプログラムを終了させる。)
atexit(void (*f)())	終了時に関数を呼び出す。

exitも、abortも、任意の関数からmain()に戻らずにプログラムを終了させる。
スタックのアンワインドが行われないため、ローカルオブジェクトの破棄は行われない。

//cstdlib 2004/8/20
#include <iostream>
//#include <cstdlib>
using namespace std;
void endfunc() {
	cout << "おしまい" << endl;
}

int main(void)
{
	atexit(endfunc);
	return 0;
}

実行すると、「おしまい」が出力される。
<iostream>をインクルードすれば、<cstdlib>がインクルードされるようだ。

次章はいよいよSTL。

STLの中心のコンポーネントはコンテナ、反復子、アルゴリズム。
ほかのコンポーネントは、アダプタ、関数オブジェクト(functor)など。
STLの概念は、データと演算を分離することに基づいている。オブジェクト指向の本来の考え方と矛盾する。
任意の種類のコンテナを任意の種類のアルゴリズムと結びつけることができるため、柔軟性が高くなる。

コンテナ

シーケンスコンテナ

vector, deque, list

連想コンテナ

set, multiset, map, multimap

vector

• ランダムアクセス可能
• 配列の最後に要素を追加削除する処理は高速。
• 配列の最初、途中に要素を追加削除する処理は、要素の移動のために時間がかかる。

push_back(x)

配列の末尾に挿入。

size()

配列の要素数を返す。

提供されていない関数

push_front(x)。パフォーマンスの低下を招く関数は提供されない。

deque

• 両端待ち行列
• 配列の先頭と末尾最後に要素を追加削除する処理は高速。
• 配列の途中に要素を追加削除する処理は、要素の移動のために時間がかかる。

push_front(x)

配列の先頭に挿入。

push_back(x)

配列の末尾に挿入。

size()

配列の要素数を返す。

list

• 双方向リンクリスト
• ランダムアクセスを提供しない。要素の探索は、リンクをたどる
• 配列の途中に要素を追加削除する処理はvector,dequeよりも速い。

push_back(x)

配列の先頭に挿入。

pop_front(x)

配列の先頭の要素を削除する。値を返さない。

front(x)

配列の先頭の要素の値を取得する。

bool empty()

要素が空かどうかを返す。

提供されない演算子

[]

文字列

• コンテナとして使用できるのは、文字列クラスbasic_string<>, string, wstring など

通常の配列

• メンバ関数がないためSTLのコンテナではないが、アルゴリズムを使うことができる。

連想コンテナ

• 要素を自動的にソートする。ソートのための独自の比較関数を提供できる
• 一般に2分木として実装される。各要素は、１個の親と２個の子を持つ。
• 要素のアクセスには、反復子が必要。

set <set>

要素が値によって、ソートされている。各要素は必ず１度だけで重複は許されない。

multiset <set>

重複が許されるset

map <map>

キーと値のペアを要素とする。キーの重複は許されない。

multimap <map>

キーの重複が許されるmap。辞書としても使用できる。

連想コンテナの関数

insert(x)

要素の挿入(make_pair関数を使っている。)
例：coll.insert(make_pair(5,"tagged"));

[] (map)

mapobj[キー] = 値 で代入。キーに対する値の取得ができる。
存在しないキーを指定してもエラーにはならない。

常にソートした状態で使いたい時は、set、multisetを使えということか。

コンテナアダプタ

• 基本コンテナを使って実装されているコンテナ。

stack

スタック。LIFO

queue

キュー。FIFO

反復子 （イテレータ）

• const_iteratorは読み取り専用のイテレータ
• ループ処理では、前置インクリメントを使う。後置インクリメントは遅くなる。

基本的な演算子

*, ++, ==, !=, =

基本的な関数

begin(), end(); 範囲が空のとき、begin()と、end()は等しい。

反復子のカテゴリ

双方向反復子（list, set, multiset, map, multimap）
ランダムアクセス反復子（vector, deque, string）

連想コンテナのイテレータの動きは2分木のとおりがけ順。

アルゴリズム

アルゴリズムは、反復子を使う、グローバル関数である。オブジェクト指向プログラミングのパラダイムではなく、関数型プログラミングのパラダイムである。
欠点：使用方法がわかりにくい。コンテナとアルゴリズムに組み合わせのできないものもある

//C++チュートリアル＆リファレンスのP108あたり
//vectorとアルゴリズム 2004/8/21
#include <iostream>
#include <vector>
#include <algorithm>

//出力関数
template <typename T>
void print(const std::vector<T> & v, const std::string s ="")
{
	std::cout << "要素の出力。要素数：" << v.size() << " : " << s <<std::endl;
	for (std::vector<T>::const_iterator ite = v.begin(); ite != v.end(); ++ite) {
		std::cout << *ite << " , " ;
	}
	std::cout << std::endl;
}

int main(void)
{
	std::vector<int> coll;
	std::vector<int>::iterator pos, pos1;
	coll.push_back(11);
	coll.push_back(12);
	coll.push_back(13);
	coll.push_back(14);
	coll.push_back(15);

	print(coll, "初期値");
	
	pos = std::min_element(coll.begin(), coll.end());
	std::cout << "min:" << *pos << std::endl;
	pos1 = std::max_element(coll.begin(), coll.end());
	std::cout << "max:" << *pos1 << std::endl;

	std::swap(*pos, *pos1);
	print(coll, "最小と最大を交換");

	coll[1] = 22;
	print(coll, "2番目書き換え");
	
	std::sort(coll.begin(), coll.end());
	print(coll, "並べ替え");
	
	pos = std::find(coll.begin(), coll.end(),13);
	std::reverse(pos, coll.end());
	print(coll, "13を探して、13以降を逆順並べ替え");
	
	++*pos;
	print(coll, "13のあった位置の数値を1増やす。");
	
	return 0;
}

実行結果
要素の出力。要素数：5 : 初期値
11 , 12 , 13 , 14 , 15 , 
min:11
max:15
要素の出力。要素数：5 : 最小と最大を交換
15 , 12 , 13 , 14 , 11 , 
要素の出力。要素数：5 : 2番目書き換え
15 , 22 , 13 , 14 , 11 , 
要素の出力。要素数：5 : 並べ替え
11 , 13 , 14 , 15 , 22 , 
要素の出力。要素数：5 : 13を探して、13以降を逆順並べ替え
11 , 22 , 15 , 14 , 13 , 
要素の出力。要素数：5 : 13のあった位置の数値を1増やす。
11 , 23 , 15 , 14 , 13 , 

２つの要素の探索プログラム。(P113上)
P113下にcompose_f_gx_hxがあるが、今は意味がわからないので何もしてない。P309に出てくる。

//C++チュートリアル＆ライブラリのP108
//vectorとアルゴリズム
//2004/8/21
#include <iostream>
#include <vector>
#include <algorithm>

//出力関数
template <typename T>
void print(const std::vector<T> & v, const std::string s ="")
{
	std::cout << "要素の出力。要素数：" << v.size() << " : " << s <<std::endl;
	for (std::vector<T>::const_iterator ite = v.begin(); ite != v.end(); ++ite) {
		std::cout << *ite << " , " ;
	}
	std::cout << std::endl;
}

//P113 ２つの要素の探索、どちらが前にあるかわからない。
//end()だった場合、間接参照してはならないため、注意する。
template <typename T>
void find2element(const std::vector<T>& co, const T& fn1, const T& fn2)
{
	std::vector<T>::const_iterator posf1, posf2;
	posf1 = std::find(co.begin(), co.end(), fn1);
	posf2 = std::find(co.begin(), posf1, fn2); //[begin, posf1)で探索
	if (posf2 != posf1) {
		std::cout << fn2 << "は、" << fn1 << " より前にあります。 " <<std::endl;
	} else {
		posf2 = std::find(posf1, co.end(), fn2); //[posf1, end)で探索
		if (posf2 != posf1) {
			std::cout << fn2 << "は、" << fn1 << " より後ろにあります。 " <<std::endl;
		} else {
			std::cout << fn2 << "は、" 
				<< fn1 << " と同じ位置にあります。(同じ数値か、end)" <<std::endl;
		}
	}
}

int main(void)
{
	std::vector<int> coll;
	std::vector<int>::iterator pos, pos1;
	coll.push_back(11);
	coll.push_back(12);
	coll.push_back(13);
	coll.push_back(14);
	coll.push_back(15);
	coll.push_back(14);

	std::cout << "*** 2つの要素の探索 ***" << std::endl;
	print(coll);
	find2element(coll, 13, 15);
	find2element(coll, 11, 13);
	find2element(coll, 14, 14);
	find2element(coll, 15, 30);
	find2element(coll, 30, 15);
	find2element(coll, 30, 32);
	return 0;
}

実行結果
*** 2つの要素の探索 ***
要素の出力。要素数：6 : 
11 , 12 , 13 , 14 , 15 , 14 , 
15は、13 より後ろにあります。 
13は、11 より後ろにあります。 
14は、14 と同じ位置にあります。(同じ数値か、end)
30は、15 より後ろにあります。 
15は、30 より前にあります。 
32は、30 と同じ位置にあります。(同じ数値か、end)

複数の範囲 P114

equal(co1.begin(), co1.end(), co2.begin())

co1とco2の要素を最初から１つずつ比較する。要素の数はco1から間接的に指定される。

copy(co1.begin(), co1.end(), co2.begin())

要素のコピー。 注意：co2に十分な要素数があることが必要である。
要素数が確保できてない場合、範囲外の間接参照は未定義の動作になる。

resize(x)

xの要素数を確保する。
多すぎた場合はサイズが減るのかな？以下確認のコード。サイズが減る。
EffectiveSTLにあったのはアロケータが減るかどうかという話だったかな・・・？

//C++チュートリアル＆リファレンスのP114あたり
//resize() 2004/8/21
#include <iostream>
#include <vector>

//出力関数
template <typename T>
void print(const std::vector<T> & v, const std::string s ="")
{
	std::cout << "要素の出力。要素数：" << v.size() << " : " << s <<std::endl;
	for (std::vector<T>::const_iterator ite = v.begin(); ite != v.end(); ++ite) {
		std::cout << *ite << " , " ;
	}
	std::cout << std::endl;
}

int main(void)
{
	std::cout << "配列の要素を5個確保し、push_backで5個追加する。" << std::endl;
	std::vector<int> coll(5);
	coll.push_back(11);
	coll.push_back(12);
	coll.push_back(13);
	coll.push_back(14);
	coll.push_back(15);

	print(coll, "初期値");
	coll.resize(7);
	print(coll, "要素数を7に変更resize(7)。");
	
	return 0;
}

実行結果
配列の要素を5個確保し、push_backで5個追加する。
要素の出力。要素数：10 : 初期値
0 , 0 , 0 , 0 , 0 , 11 , 12 , 13 , 14 , 15 , 
要素の出力。要素数：7 : 要素数を7に変更resize(7)。
0 , 0 , 0 , 0 , 0 , 11 , 12 , 

次は反復子アダプタ

反復子アダプタ

挿入反復子

back_inserter(container)

push_back()を呼び出す。
copy(co1.begin(), co1.end(), back_inserter(co2))

front_inserter(container)

push_front()を呼び出す。
copy(co1.begin(), co1.end(), front_inserter(co2))

inserter(container, pos)

insert()を呼び出す。
copy(co1.begin(), co1.end(), inserter(co2, co2.begin()))

ストリーム反復子

istream_iterator<string>(cin)

cinで標準入力から、文字列を入力。cin >> stringを実行する。
istream_iterator<string>()は、デフォルトコンストラクタを呼び出す。ストリーム末尾反復子を生成する。つまりそれ以上読み取ることができない位置を示す。
と、書いてあるけど、良くわからない。ストリームってのがわかってない・・・。今はEOFと同じようなもんだと思っておく。

ostream_iterator<string>(cout, "\n")

cout << で標準出力へ、区切り文字をつけて、文字列を出力。

//C++チュートリアル＆リファレンスのP119あたり
//ストリーム反復子 2004/8/22
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

//出力関数
template <typename T>
void print(const std::vector<T> & co, const std::string s ="")
{
	std::cout << "要素の出力。要素数：" << co.size() << " : " << s <<std::endl;
	copy(co.begin(), co.end(),
		std::ostream_iterator<int>(std::cout, " , "));
	std::cout << std::endl;
}

int main(void)
{
	std::vector<int> co;
	copy(std::istream_iterator<int>(std::cin),
		std::istream_iterator<int>(), back_inserter(co));
	print(co, "");

	return 0;
}

実行結果
要素の出力。要素数：3 : 
123 , 456 , 789 , 

標準入力の止め方をどうすればいいのかわからなかった。CTRL+R　エンターなどと適当にやったらうまくいった。

逆反復子 P121

rbegin(), rend()

逆になるので、rbegin()は最後の要素、rend()は最初の要素の前を指す。

未定義の動作に注意。

end(), rend()の間接参照は未定義。（要素がない）

アルゴリズムの操作 P122

要素の削除

remove()は削除をするが、サイズを変えない。

削除後の最後のイテレータを返す。
サイズを変更したい時は、co.erase(remove(co.begin(), co.end(), 45), co.end());
と組み合わせる必要がある。

distance()は反復子の個数を返す。

distance(co.begin(), co.end())で要素のサイズになる。

未定義の動作に注意。

end(), rend()の間接参照は未定義。（要素がない）

操作のアルゴリズムと連想コンテナ P126

要素の削除、順序の変更、要素の変更を行うアルゴリズムは連想コンテナを出力先に指定できない。

要素の変更を行うアルゴリズムを連想配列に対して行うと、要素の値や位置の変更が可能になるため、ソートされた状態ではなくなってしまうから。
ソートの順序を守るため、連想コンテナの反復子は、定数の値（またはキー）のための反復子として宣言されている。

要素の削除を行うためには、メンバ関数のerase()を呼び出す

アルゴリズムのremoveを呼び出すことはできない。

//C++チュートリアル＆リファレンスのP127あたり
//連想コンテナの要素の削除 2004/8/22
#include <iostream>
#include <set>
#include <algorithm>

//出力関数
template <typename T>
void print(const std::multiset<T> & co, const std::string s ="")
{
	std::cout << "要素の出力。要素数：" << co.size() << " : " << s <<std::endl;
	copy(co.begin(), co.end(),
		std::ostream_iterator<T>(std::cout, " , "));
	std::cout << std::endl;
}

int main(void)
{
	std::multiset<int> co;
	for (int i = 11; i < 20; ++i) {
		co.insert(i);
	}
	co.insert(12);

	print(co, "初期値");

	std::set<int>::iterator ite = find(co.begin(), co.end(), 17);
	std::cout << "17 から最後までの距離。distance:" 
			<< std::distance(ite, co.end()) << std::endl;

	co.erase(ite, co.end());	//17から最後まで削除
	int num = co.erase(12);	//12を削除
	
	std::cout << "削除した要素数:" << num << std::endl;
	
	print(co, "");
	return 0;
}

実行結果
要素の出力。要素数：10 : 初期値
11 , 12 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 
17 から最後までの距離。distance:3
削除した要素数:2
要素の出力。要素数：5 : 
11 , 13 , 14 , 15 , 16 , 

リストlistに対しては、メンバ関数のremoveが用意されている。

アルゴリズムのremove+eraceを使うよりも、メンバ関数のremoveを使用したほうがパフォーマンスが高い。 co.remove(2) //値が2の要素をすべて削除する。 この場合、eraseはいらない。

同じ機能を持つ場合、メンバ関数の方がパフォーマンスが高い。

アルゴリズムを使用しても、警告などがでないため、ユーザーがメンバ関数を知っておく必要がある。

ユーザー定義の汎用関数 P128

PRINT_ELEMENT関数は今まで作ったprint関数と似ている

//C++チュートリアル＆リファレンスのP129あたり
//ストリーム反復子 2004/8/22
#include <iostream>
#include <vector>
#include <algorithm>

//出力関数
template <typename T>
void print(const T & co, const std::string s ="")
{
	typename T::const_iterator pos;
	std::cout << s;
	for (pos = co.begin(); pos != co.end(); ++pos) {
		std::cout << *pos << ' ';
	}
	std::cout << std::endl;
}

int main(void)
{
	std::vector<int> co;
	for (int i = 11; i < 16; ++i) {
		co.push_back(i);
	}

	print(co, "初期値:");
	return 0;
}

関数オブジェクト

関数オブジェクトとは

関数オブジェクトとは

関数のようにふるまうオブジェクト

関数のふるまいとは

括弧を使って引数を渡して呼び出すことができるもの

関数オブジェクトの作成

operator()を定義すればよい。

//C++チュートリアル＆リファレンスのP134あたり
//関数オブジェクト 2004/8/23
#include <iostream>
#include <vector>

//関数オブジェクト
class CPrint {
	public:
	void operator() (int e) const {		//括弧の定義
		std::cout << e << ' ';
	}
};

int main(void)
{
	std::vector<int> co;
	for (int i = 11; i < 16; ++i) {
		co.push_back(i);
	}
	
	std::for_each(co.begin(), co.end(), CPrint());
	std::cout << std::endl;
	
	return 0;
}

呼び出し時には括弧をつけている

関数オブジェクトの呼び出し

CPrint::operator()(*act)を呼び出している。

//for_eachの定義
namespace std {
	template <class Iterator, class Operation>
	Operation for_each (Iterator act, Iterator end, Operation op)
	{
		while (act != end) {
			op (*act);
		}
		return op;
	}
}

関数オブジェクトの長所

関数オブジェクトは「スマート関数である」

クラスのメンバを持つことができる。つまり状態をもつことができる。
ある関数オブジェクトが表現する同じ関数が、同時に別の状態を持つことが可能となる。 これは通常の関数では不可能なことである。 関数オブジェクトは、実行時に呼び出す前に初期化できるというメリットもある。

関数オブジェクトはそれぞれ型を持つ

通常の関数が別の型を持つのは、シグネチャが異なる時に限られる。 しかし、関数オブジェクトであれば、たとえシグネチャが同じでも別の型を持つことができる。

・・・よくわからない

関数オブジェクトは、たいてい通常の関数より高速である

テンプレートという概念を使うと、コンパイル時に定義される詳細が多くなるため、最適化がより強力に行われるのが普通である。 したがって、通常の関数ではなく関数オブジェクトを渡すと、パフォーマンスが向上することが多い。

・・・これもよくわからない

スマートな関数オブジェクトの例

なんだ？この使い方は・・・！テンプレート引数に数値を代入。

//C++チュートリアル＆リファレンスのP136あたり
//関数オブジェクト テンプレート引数に数値を代入？？？ 2004/8/23
//コンパイル時に加算する数値がわかっている場合 2004/8/23
#include <iostream>
#include <vector>

//関数
template <int val>
void add(int & num)
{
	num += val;
}

//関数オブジェクト
class CPrint {
	public:
	void operator() (int e) const {		//括弧の定義
		std::cout << e << ' ';
	}
};

int main(void)
{
	std::vector<int> co;
	for (int i = 11; i < 16; ++i) {
		co.push_back(i);
	}
	
	std::for_each(co.begin(),co.end(), CPrint());
	std::cout << std::endl;

	std::for_each(co.begin(),co.end(), add<10>);	//10を加算

	std::for_each(co.begin(),co.end(), add<20>);	//20を加算

	std::for_each(co.begin(),co.end(), CPrint());
	std::cout << std::endl;
	
	return 0;
}

実行結果
11 12 13 14 15 
41 42 43 44 45 

・・・誤解

for_eachに渡しているobj()はoperator()ではなく、コンストラクタだった。
だんだん混乱してきているが、じっくり行こう！

//C++チュートリアル＆リファレンスのP134あたり
//関数オブジェクト 2004/8/23
#include <iostream>
#include <vector>

//関数オブジェクト 加算
class AddValue {
private:
		int val;
public:
	AddValue(int v):val(v) { }		//コンストラクタで初期化する。
	void operator() (int& e) {
		e += val;
	}
};
//関数オブジェクト 出力
class CPrint {
	public:
	void operator() (int e) const {		//引数はコンテナの値になる。
		std::cout << e << ' ';
	}
};

int main(void)
{
	std::vector<int> co;
	for (int i = 11; i < 16; ++i) {
		co.push_back(i);
	}
	
	std::for_each(co.begin(), co.end(), CPrint());
	std::cout << std::endl;

	//AddValue::operator()(*act) *actはco.beginでインクリメントしていく
	//AddValue(10)は一時オブジェクトのコンストラクタ。
	std::for_each(co.begin(), co.end(), AddValue(10));
	
	std::for_each(co.begin(), co.end(), CPrint());
	std::cout << std::endl;
	return 0;
}

std::for_each(co.begin(), co.end(), AddValue(10));
は、一時オブジェクトを使わないで、
AddValue ad(10);
std::for_each(co.begin(), co.end(), ad);
のように書ける。

事前定義の関数オブジェクト

less<T> greater<T>

setを昇順で並べ替えるコンテナ：set<int, less<int> > co
降順で並べ替えるコンテナ：set<int, greater<int> > co

negate<T>

正を負に、負を正にする。正と負の逆転

multiplies<T>(a,b)

a*b 値を掛ける。引数が2つ必要

equal_to<T>(a,b)

a==b の判定を行う。

mem_fun_ref(&T::function)

Tのメンバ関数functionを呼び出す。

例

grater, negate, multiplies, equal_to

//C++チュートリアル＆リファレンスのP141あたり
//関数オブジェクト 2004/8/23
#include <iostream>
#include <set>
#include <deque>

//関数オブジェクト 出力
class CPrint {
	public:
	void operator() (int e) const {		//引数は、コンテナの値になる。
		std::cout << e << ' ';
	}
};
//出力関数
template <typename T >
void print(const T & co, const std::string s ="")
{
	std::cout << "要素の出力。要素数：" << co.size() << " : " << s <<std::endl;
	copy(co.begin(), co.end(),
		std::ostream_iterator<T::value_type>(std::cout, " , "));
	std::cout << std::endl;
}

int main(void)
{
	std::set<int, std::greater<int> > co;
	std::deque<int> cot;

	for (int i = 1; i <= 9; ++i) {
		co.insert(i);
	}
	print(co, "初期値");
	
	//正負の変換
	transform( co.begin(), co.end(),
			back_inserter(cot), std::negate<int>());
	print(cot, "正負の符号反転");
	cot.clear();

	//変換元のコンテナの値を最初の引数、２番目の引数とする。（二乗）。
	transform( co.begin(), co.end(), co.begin(),
			back_inserter(cot), std::multiplies<int>());
	print(cot, "multiplies計算後：二乗a*a");
	cot.clear();

	//変換元のコンテナの値を最初の引数、10を２番目の引数とする。
	transform( co.begin(), co.end(), 
			back_inserter(cot), bind2nd(std::multiplies<int>(), 10));
	print(cot, "multiplies計算後：10*a");
	

	//変換元のコンテナの値が70と等しいものを42に変換。
	replace_if( cot.begin(), cot.end(), bind2nd(std::equal_to<int>(), 70), 42);
	print(cot, "70を42に変換");
	
	
	return 0;
}

実行結果
要素の出力。要素数：9 : 初期値
9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 
要素の出力。要素数：9 : 正負の符号反転
-9 , -8 , -7 , -6 , -5 , -4 , -3 , -2 , -1 , 
要素の出力。要素数：9 : multiplies計算後：二乗a*a
81 , 64 , 49 , 36 , 25 , 16 , 9 , 4 , 1 , 
要素の出力。要素数：9 : multiplies計算後：10*a
90 , 80 , 70 , 60 , 50 , 40 , 30 , 20 , 10 , 
要素の出力。要素数：9 : 70を42に変換
90 , 80 , 42 , 60 , 50 , 40 , 30 , 20 , 10 , 

transform(変換元の最初, 変換元の最後, 変換元２の最初, 変換先, 演算)
transform(変換元の最初, 変換元の最後, 変換先, 演算)
２つでてきた。

bind2nd のふるまい。P142

1. bind2ndコンストラクタは演算と、２番目の引数を内部の値として格納する。
2. アルゴリズムがbind2nd()を呼び出す。
3. bind2nd()はアルゴリズムから渡された要素を最初の引数、内部に格納した値を２番目の引数として演算を呼び出す。
4. 結果を返す

bind2ndとか出てきて難しい。じっくり！
bind2ndで呼び出される演算関数は引数２つに対応してないといけないんだな。

コンテナの要素

コンテナの要素の条件

コピーコンストラクタによるコピーが可能でなければならない

また、生成されるコピーは元の要素と等しくなければならない。
コピーコンストラクタは頻繁に呼び出されるので、パフォーマンスが重要である。 オブジェクトのコピーに時間がかかるならば、参照のセマンティックスを持つコンテナを使うことによってオブジェクトのコピーを回避できる。

代入演算子による代入が可能でなければならない。

要素はデストラクタによる破棄が可能でなければならない。

デストラクタはprivateであってはならない。
デストラクタで例外を送出してはならない。

デフォルトコンストラクタが利用可能で無ければならない。

（定義がなければ、自動的に生成される。）

一部のコンテナでは、==演算子による等価性のテストが定義されていなければならない。

要素を検索する場合に必要となる。

連想コンテナでは、ソートの基準となる演算を提供しなければならない。

デフォルトは、less<>関数オブジェクトで<演算子が呼び出される。

値のセマンティックスと参照のセマンティックス

セマンティックスの意味を調べてみた。
semantics 意味論。反意語は、シンタックス(xml)
それぞれのトランザクションが、どのような処理を行うかを、トランザクションの「セマンティックス（意味論）」と呼ぶことがあります。
基本データ型と同じセマンティックス（この場合「意味」というよりも「動作」に近い感じがする。）

値のセマンティックスだけをサポートしようとする姿勢の長所

要素のコピーは単純である。
参照はエラーの原因となりやすい。 (存在しないオブジェクトを参照しないように注意する必要がある。参照の循環が発生する可能性もあり、それにも対処する必要がある。)

同、短所

パフォーマンスが低下する可能性がある。
コピーが不可能な場合がある。
同一のオブジェクトを複数のコンテナで同時に管理できない。

STLの標準のライブラリでは、参照のセマンティックスはサポートされていない。
参照のセマンティックスをサポートするには、参照カウンタ付のスマートポインタを使うと良い。
スマートポインタによって値の変更が行われる場合。要素の順序が不正になる可能性がある。これは、望ましくない。
auto_ptrはコピーを行わないので、つかえない。

STLのエラーと例外

エラー処理

STLの設計上の目標は、最大のセキュリティより最大のパフォーマンスである。 エラーのチェックには時間がかかるため、エラーチェックはほとんどない。

• 有効な反復子を使う。他の演算（挿入、削除、再割り当て）によって無効になることがある。
• 末尾の反復子の呼び出しはできない。
• 範囲の指定では、最初の反復子から２番目の反復子まで到達可能でなければならない。
• 複数の範囲の指定。２番目の範囲の指定では、最初の範囲の要素数が必要である。
• 出力先に十分な要素数があること。そうでなければ、挿入反復子を使う。

STLの模範的バージョンにSTLportがある。

例外処理

標準で、例外を送出する場合があることを要求される関数は、vectorとdequeのat()だけで、[]の演算子をチェックする。
そのほかには、bad_allocなどの通常の例外が起こる可能性があることを要求している。

ノードをベースとするコンテナは、要素の構築に失敗した場合、コンテナは前の状態のままになる。
単独および複数の要素の消去は、成功が保証されている。

vector, dequeは、要素の構築に失敗した場合、前の状態に復旧しない。
復旧するには、挿入する場所以降の要素をコピーしなければならない。 ノードをベースとするコンテナは、要素の構築に失敗した場合、コンテナは前の状態のままになる。
単独および複数の要素の消去は、成功が保証されている。

コミット、ロールバック機能を持つコンテナ。
• list（sort(), unique()を呼び出さないこと。）


• 連想コンテナ（複数の要素を挿入する関数を呼び出さないこと。）

要素のコピーを作ることは、常にコストが高くなる。

STLにないコンポーネントは、ハッシュテーブルとして実装されるコンテナ

５章が終了・・・次回は6章

コンテナの共通演算

配列の要素で初期化

int arr[] = {11,12,13,14,15,16};
std::set<int> co1(arr,arr+sizeof(arr)/sizeof(arr[0]));
vectorでやろうとしたらうまくいかなかった。

標準入力を使って初期化

//正しい
std::deque<int> c((std::istream_iterator<int>(std::cin)),
			(std::istream_iterator<int>()));

//あやまり。関数宣言になる。
std::deque<int> c(std::istream_iterator<int>(std::cin),
			std::istream_iterator<int>());

下は、dequeが戻り型、１番目の引数の名前がcin、２番目の引数の名前がない、関数になる。
よくわからん・・・
vectorで、範囲指定コンストラクタを呼ぼうとしたらうまくいかなかった。
関数を呼んでいるみたいだから、同じようなことが起こっているのだろうか。

swapと代入。

代入は、代入元のコピー、代入先の古い要素の削除をするので、コストが高い。
swapは、コンテナの内部データだけを交換するので効率的である。

vector

サイズ

//C++チュートリアル＆リファレンスのP158あたり
//vector 2004/8/24
#include <iostream>
#include <vector>

//出力関数
template <typename T>
void print(const T & co, const std::string s ="")
{
	std::cout << s <<std::endl;
	copy(co.begin(), co.end(),
		std::ostream_iterator<T::value_type>(std::cout, " , "));
	std::cout << std::endl;
}

int main(void)
{
	std::vector<int> co;		//デフォルトコンストラクタ
	std::cout << "代入前。empty:" << co.empty() << std::endl;
	std::cout << "代入前。max_size:" << co.max_size() << std::endl;
	std::cout << "代入前。capacity:" << co.capacity() << std::endl;

	for (int i = 1; i <= 9; ++i) {
		co.push_back(i);
	}
	print(co, "デフォルトコンストラクタに値を代入");
	std::cout << "代入後。empty:" << co.empty() << std::endl;
	std::cout << "代入後。max_size:" << co.max_size() << std::endl;
	std::cout << "代入後。capacity:" << co.capacity() << std::endl;
	std::cout << "size:" << co.size() << std::endl;

	return 0;
}

実行結果
代入前。empty:1
代入前。max_size:1073741823
代入前。capacity:0
デフォルトコンストラクタに値を代入
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 
代入後。empty:0
代入後。max_size:1073741823
代入後。capacity:256
size:9

capacity()

現在のメモリに格納できる要素の数。
capacityを超過したら、vectorは内部メモリの再割り当てを行わなければならない。（時間がかかる） 再割り当てを行うと、参照、ポインタ、反復子すべてが無効になる

reserve()

上記の再割り当てを防ぐためには、初期化時にサイズを引数として渡す。
vector<int> co(10);・・・など。
しかし、コンストラクタがよばれるため、単にメモリの確保が目的ならreserve()を使うべき。
一度確保した格納メモリは、減ることは無い。

要素数が非常に少ない場合、メモリが無駄になる。

実装では、実行例のとおり、ある程度のメモリを確保しているため。

vectorの格納メモリサイズを小さくしたい場合。

swapすれば、現在の要素の数に応じたメモリサイズが再割り当てされる。
std::vector<T>(co).swap(co);

//C++チュートリアル＆リファレンスのP155あたり
//vector 格納メモリの割り当てswap 2004/8/24
#include <iostream>
#include <vector>

int main(void)
{
	std::vector<int> co;		//デフォルトコンストラクタ
	co.reserve(8);
	std::cout << "代入前。capacity:" << co.capacity() << std::endl;

	for (int i = 1; i <= 9; ++i) {
		co.push_back(i);
	}
	std::cout << "9個代入後。capacity:" << co.capacity() << std::endl;
	std::cout << "size:" << co.size() << std::endl;

	std::vector<int>(co).swap(co);
	std::cout << "swap後。capacity:" << co.capacity() << std::endl;
	return 0;
}

実行結果
代入前。capacity:8
9個代入後。capacity:16
size:9
swap後。capacity:9

メンバ関数のリファレンス

この本はリファレンスがわかりやすくまとまってていいなあ。全部写そうかと思ったけど、大変そうだったので、やめた。

通常の配列、例外。

通常の配列のようにvectorの要素を連続するメモリに配置しなければならないという明確な規定は無い。

しかし、これを保証する意図はあり、問題の報告にしたがって修正される予定である。
&v[i] == &v[0] + i となる。

例外処理

• push_back()によって要素が挿入されて例外が発生した場合、この関数は何も効果を与えない。
• insert()は、要素のコピーの演算(コピーコンストラクタと代入演算子)が例外を送出しなければ、例外を送出しない。
• pop_back()は例外を送出しない。
• erase()とclear()は要素のコピーの演算(コピーコンストラクタと代入演算子)で例外を送出しない要素を使う場合、演算は成功または効果なしのどちらかである。 このような要素は、POD(Plain Old Data)でなければならない。 PODとは、C++に固有の機能を使わない型で、たとえば、通常のC言語の構造はすべてPODである。

デストラクタが例外を送出しないという条件に基づいている。

vector<bool>

ブール型の要素を持つ、vectorの特別バージョン

• 各要素に1ビットだけを使い、サイズを1/8にする。
• 要素の演算を1ビット単位にするため、通常の演算よりも遅くなることもある。
• 固定サイズのビットフィールドが必要な時には、bitsetを使うほうが良い。
• 特別な演算

  co.flip()	bool型の要素の全てを反転させる。(すべてのビットの補数を求める。)
  m[idx].flip()	インデックスの要素のビットを反転させる。
  m[idx] = val;	インデックスの要素にvalを代入する。（1ビット）
  m[idx] = m[idx2]	インデックスの要素にm[idx2]を代入する。

deque

• 複数のメモリブロックを使う。
• 先頭と末尾以外で要素を挿入または削除する場合、dequeの要素を参照するポインタ、参照、反復子は、すべて無効となる恐れがある。
• 未使用になったメモリブロックが解放され、dequeのメモリのサイズが小さくなることがある。
• 途中に要素を挿入または、削除すると、比較的時間がかかる。
• 反復子はランダムアクセス反復子
• capacity()とreserve()は無い。
• push_front()とpop_front()をもつ。

例外処理

• bush_back(), push_front()による要素の挿入で例外が発生した場合、これらの関数は何の効果も与えない。
• pop_back()とpop_front()は、例外を送出しない。

list

• ランダムアクセスではない。任意の要素へのアクセスには時間がかかる。
• 要素の挿入と削除はどの位置でも高速。
• 要素の挿入と削除が行われても、他の要素のポインタ、参照、反復子は無効にならない。
• listでは例外処理のサポートにより、ほとんどの演算は、成功または効果無しのいずれかになる。
• [], at()がない。
• メモリ容量の調整、再割り当てが不要。
• 要素の移動のためのメンバ関数を持つ。同じ名前のアルゴリズムよりも高速なバージョンである。
• アクセス関数はfront(), back()だけ。
• 挿入削除関数はdeque()のすべての関数 + remove(val)「valの値を持つ全ての要素を削除」 ,remove_if(op) 「op(elem)が真であると削除」
• 例：ある値をもつ最初の要素だけを削除する時はerace()とfindアルゴリズムを使う。
  pos = find(co.begin(), co.end(), val);
  if (pos != co.end()) {
  co.erase();
  }
• 例：偶数の要素すべてを削除する。
  list.remove_if（not1(bind2nd(modulus<int>(),2)))
• 特別な演算

co.unique();	同じ値を持ち、連続する要素が重複する場合。重複を取り除く。
c1.splice(pos, c2);	c2のすべての要素をc1の、posの位置の手前に移す。
sort();	<演算子でソート。
c1.merge(c2);	ソートされている２つこのコンテナでc2の要素を全てc1にマージする。
reverse()	すべての要素の順序を逆転させる。

例外処理

• 例外の安全性をもっとも強力にサポートしているのがlistである。
• 代入の演算と、sort()を呼び出さず、要素の比較が例外を送出しない場合には、listはトランザクションセーフである。

set,multiset <set>

ソートの基準

反対称性

<演算子では、x < y が真の場合、y < x は偽になる。

推移性

<演算子では、x < y が真かつ、z < y が真の場合、z < x は真になる。
これは叙述関数にも当てはまる。

非反射性

x < xは、常に偽である。

機能

検索が速い。２分木を用いて実装されることが多い。

要素の値を直接変更できない。反復子によるアクセスは定数になる。

２つの要素の等価性

if (!(elem1 < elem || elem2 < elem1))

• ソートの基準として渡す引数が一つですむ。
• 要素の型で、==演算子を提供する必要がない。
• 等価性について相反する定義が可能である。(==のふるまいが式の中と異なっていてもかまわない。)ただしこれはトラブルの原因になりかねない。

2004/8/26図書の返却期限になったのでP185までで一旦終了。

set,multiset <set>

特別な検索

//C++チュートリアル＆リファレンスのP187あたり
//set 2004/9/11
#include <iostream>
#include <set>

int main(void)
{
	std::multiset<int> co;
	for (int i = 1; i < 8; ++i) {
		co.insert(i);
	}
	
	co.insert(3);
	co.insert(3);
	
	std::cout << "count(3):" << co.count(3) << std::endl;
	
	std::cout << "lower_bound(3):" << *co.lower_bound(3) << std::endl;
	std::cout << "upper_bound(3):" << *co.upper_bound(3) << std::endl;
	std::cout << "equal_range(3):" << *co.equal_range(3).first << " "
			<< *co.equal_range(3).second << std::endl;
	return 0;
}

*upper_boundは次に大きい要素が入っている位置の要素を返しているから気をつけて！

Generic Programmingに書き込むようにした。

入力用のメンバ関数

• getの戻り値の型はtraits::int_type, EOFは、traits::eof()
• istreamでは、getの戻り値の型はint, EOFは、EOFとなる
• get(char& c)文字をcに格納する。

• getはデリミタの手前で止まる。
• getlineはデリミタも読み込むが、格納文字列には含まない。
• getlineは文字数以上の行を読み取ると、failbitを設定する。さらに読み込むためには、clear()によって解除する必要がある。
• readは読み取り中にEOFに達した場合、eofbit、failbitの両方のフラグが立つ。
• readsomeはストリームバッファにある文字をすべて読み取る。読み取り中にEOFに達した場合、eofbit、failbitのどちらも設定されない。エラーとはみなされない。