##master-page:ReadingTemplate
#format wiki
#language ja
= 【C++】STL for TopCoder =
 * TopCoderを始めて、最初にSTLの使い方でつまづいたので、最低限必要なものを備忘録を兼ねて簡単に解説します
 * コードとコメントをひと通り読めば、大体の使い方が分かる、ということを目指して書いています
 * 間違いなどありましたら指摘をお願いします
 * 詳しい使い方は http://www.cppll.jp/cppreference/ 等のリファレンス参照

'''更新記録'''
 * 2011/2/16 algorithmのnext_permutationについて追記
 * 2011/2/2 string ,algorithmについて追記(stringのソート)

'''目次'''
<<TableOfContents(2)>>

== vector ==
 * ある型の値を複数もつ
 * 主な用途
  * 可変長配列として
 * 使い方

{{{#!highlight cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
	/*
	 * vector<>の宣言
	 * 空のvector<>が作られる
	 */
	vector<int> v;

	/*
	 * 要素の追加
	 * v.push_back(val)
	 * vectorの最後尾に値が追加される
	 */
	v.push_back(10);
	for (int i = 0; i < 20; i++)
	{
		v.push_back(i);
	}

	/*
	 * vectorの要素数
	 * v.size()
	 */
	cout << "v contains " << v.size() << " integers" << endl;

	/*
	 * 要素へのアクセス
	 * v.at(i)
	 * nのi番目の要素が取り出される
	 */
	int x = v.at(0);
	cout << x << endl;

	/*
	 * 配列のような書き方も出来る
	 */
	for (int i = 1; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	
	return 0;
}
}}}

== string ==
 * 文字列
 * 主な用途
  * 可変長の文字列として
 * 使い方

{{{#!highlight cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	/*
	 * stringの宣言
	 */
	string str;		//空文字列
	string str2("Hello World!");	//初期値あり

	/*
	 * stringの演算子
	 */
	str = "I'm hungry";		//代入
	cout << str << endl;

	char ch = str[2];		//要素（char）へのアクセス（str.at(2)でも可）
	putchar(ch);
	cout << endl;

	str = str + " and thirsty";	//結合（str += " and thirsty"; でも可）
	cout << str << endl;

	if (str == str2)	//比較(完全一致)
	{
		cout << "str is equal to str2" << endl;
	} else {
		cout << "str is NOT equal to str2" << endl;
	}

	str = "abc";
	str2 = "bac";
	if (str < str2)		//比較（辞書順）
	{
		cout << "str is less than str2" << endl;
	} else {
		cout << "str is NO less than str2" << endl;
	}

	/*
	 * stringの文字数
	 * str.size()
	 */
	cout << "str contains " << str.size() << " characters" << endl;	//str.length()も使える

	/*
	 * stringのソート(要<algorithm>)
	 * ASCIIコードでソートされることに注意
	 */
	str = "gfedcbagfedcba";
	sort(str.begin(), str.end());
	cout << str << endl;


	/*
	 * その他、文字列の出現位置の検索、トリムなどの機能もある（詳細は割愛）
	 */
	str = "abcdefg";
	str2 = "cde";
	cout << "found str2 in str (from index of " << str.find(str2) << ")" << endl;

	cout << str.substr(3,3) << endl;

	return 0;
}
}}}

== map ==
 * ある型の値からある型の値への写像
 * 主な用途
  * 連想配列として
 * 使い方

{{{#!highlight cpp
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
	/*
	 * map<,>の宣言
	 * 平衡二分木で実装されているらしい（のでけっこう遅い）
	 */
	map<string,int> m;	//空のmap（この場合stringからintへの対応）

	/*
	 * 要素の追加
	 * おそらくメソッドを使ったほうが早いが、めんどくさいので[]演算子を使う
	 */
	m["one"] = 1;
	m["two"] = 2;
	m["three"] = 3;

	/*
	 * 要素へのアクセス
	 */
	cout << m["two"] << endl;

	/*
	 * 要素の削除
	 * m.erase(key);
	 */
	m.erase("one");

	/*
	 * mapの要素数
	 * m.size();
	 */
	cout << "m contains " << m.size() << " elements" << endl;

	/*
	 * 要素の検索
	 * m.find(key);
	 * keyが存在しない場合に、mapの最後尾へのイテレータが返ってくるので、
	 * keyの有無を確認する場合に使える
	 */
	if (m.find("one") == m.end())
	{
		cout << "one does not exist as a key" << endl;
	}

	/*
	 * 要素の列挙
	 * イテレータを使用して、mapの要素を列挙する
	 */
	m["five"] = 5;
	m["four"] = 4;
	m["ten"] = 10;
	m["eight"] = 8;
	map<string,int>::iterator it;	//イテレータの宣言
	for (it = m.begin(); it != m.end(); ++it)
	{
		cout << it->first << " -> " << it->second << endl;	//ポインタのように使う
	}

	return 0;
}
}}}

== stack,queue,priority_queue ==
 * スタック、キュー、優先度付きキュー
 * 主な用途
  * そのままスタック、キュー、優先度付きキューとして
 * 使い方

{{{#!highlight cpp
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int main() {
        /**
         * stack<>,queue,<>priority_queue<>の宣言
         */
        stack<int> st;
        queue<int> qu;
        priority_queue<int> pqu_desc;   //デフォルトでは降順
        priority_queue<int, vector<int>, greater<int> > pqu_asc;        //昇順のpriority_queue

        /*
         * 要素の追加
         * push(val);
         */
        st.push(1);
        st.push(2);
        st.push(3);

        qu.push(1);
        qu.push(2);
        qu.push(3);

        pqu_desc.push(2);
        pqu_desc.push(3);
        pqu_desc.push(1);

        pqu_asc.push(2);
        pqu_asc.push(3);
        pqu_asc.push(1);

        /**
         * 一番上の要素にアクセス
         * st.top();
         * qu.front();
         * pqu_desc.top();
         *
         * 一番上の要素を取り除く
         * pop();
         *
         * 要素が空か判定（空ならtrue）
         * empty();
         */
        cout << "stack (First In Last Out)" << endl;
        while (!(st.empty()))
        {
                cout << st.top() << endl;
                st.pop();
        }

        cout << "queue (First In First Out)" << endl;
        while (!(qu.empty()))
        {
                cout << qu.front() << endl;
                qu.pop();
        }

        cout << "priority_queue (DESC)" << endl;
        while (!(pqu_desc.empty()))
        {
                cout << pqu_desc.top() << endl;
                pqu_desc.pop();
        }

        cout << "priority_queue (ASC)" << endl;
        while (!(pqu_asc.empty()))
        {
                cout << pqu_asc.top() << endl;
                pqu_asc.pop();
        }
        return 0;
}
}}}

== algorithm ==
 * イテレータを使った各種アルゴリズムの実装
 * 主な用途
  * max,min関数、sortなど
 * 使い方

{{{#!highlight cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int array[8]={4,7,1,2,6,5,8,3};
	vector<int> v;
	for (int i=0; i<8; i++)
	{
		v.push_back(array[i]);
	}
	/**
	 * min,max関数
	 */
	cout << min(5,10) << endl;
	cout << max(5,10) << endl;

	/**
	 * 区間の中で最大/最小の値のイテレータを返す
	 * max_element(from, to)
	 * min_element(from, to)
	 * 区間の最初のイテレータ（ポインタ）と、最後（ソートする最後の要素の次）のイテレータを指定する。
	 */
	cout << *(max_element(array, array + 8)) << endl;
	cout << *(min_element(v.begin(), v.end())) << endl;

	/**
	 * 値を（破壊的に）ソートする
	 * sort(from, to(, comp))
	 * 区間の最初のイテレータと最後のイテレータ（と比較関数のポインタ）を指定する。（デフォルトは昇順）
	 */
	sort(array, array + 8);
	cout << "sort array" << endl;
	for (int i=0; i<8; i++)
	{
		cout << array[i] << " ";
	}
	cout << endl;

	cout << "sort vector" << endl;
	sort(v.begin(), v.end());	//vectorもok
	for (int i=0; i<v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;

	cout << "sort array (DESC)" << endl;
	sort(array, array + 8, greater<int>());	//降順にする
	for (int i=0; i<8; i++)
	{
		cout << array[i];
	}
	cout << endl;

	/*
	 * stringのソート
	 * ASCIIコードでソートされることに注意
	 */
	cout << "sort string" << endl;
	string str = "gfedcbagfedcba";
	sort(str.begin(), str.end());
	cout << str << endl;

	return 0;
}
}}}

=== next_permutation ===
 * 順列を生成する関数
 * 使い方
{{{#!highlight cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(){
	/*
	 * 配列のnext_permutation
	 * next_permutationを実行すると、配列の中身が辞書順で次の順列になる
	 * 一番最後の順列でnext_permutationを実行すると、一番初めの順列に戻る
	 * その際の関数の返り値だけfalseであるので、次のようにして全順列を列挙できる
	 */
	int arr[3]={0,1,2};
	do {
		cout << arr[0] << "," << arr[1] << "," << arr[2] << endl;
	} while (next_permutation(arr ,arr + 3));
	cout << endl;

	/*
	 * vectorのnext_permutation
	 */
	vector<int> v;
	for (int i=0; i<3; i++)
	{
		v.push_back(i);
	}
	do {
		cout << v[0] << "," << v[1] << "," << v[2] << endl;
	} while (next_permutation(v.begin() ,v.end()));
	cout << endl;

	/*
	 * stringのnext_permutation
	 */
	string str="ABC";
	do {
		cout << str << endl;
	} while (next_permutation(str.begin() ,str.end()));

	return 0;
}
}}}

----
[[Category読み物]]