STLメモ

C++

これは何？

STLの概要が理解できたので、メモります

STLの利点・弱点

利点
  • 実装量の低下
弱点

コンテナ

データの集合を管理するテンプレート

  • 特徴別にいろんなコンテナがある
  • 使い道に応じてテンプレートを選ぶ必要がある
順序コンテナ
  • vector
    • ランダムアクセス
    • 末尾へのアクセスが高速
  • deque
    • ランダムアクセス
    • 先頭、末尾へのアクセスが高速
    • 前後以外にデータを追加・削除する場合は、vectorに分がある
  • list
    • ランダムアクセス不可
    • 先頭、末尾への挿入が高速
連想コンテナ
bitset
  • boolの配列
  • ビット演算向け
コンテナ・アダプタ
  • stack
    • vector,list,dequeでstackを実現
  • queue
    • list,dequeでstackを実現
どれを選べばいいの？

επιστημη大先生が書いた、この辺りが参考になるかと

あと、こっちも

イテレータ

コンテナ種類に依存することなく、中身にアクセスするための共通のインターフェース
基本的には、以下の機能を持つ

  • operator != で比較
  • operator* でイテレータがさす要素を参照
  • operator++ でコンテナの次の要素にアクセス
    • operator* とか、operator++ でポインタライクな挙動が出来るけど、中身はポインタでなくても良い
イテレータの種類

アルゴリズムにより、使用するイテレータが5種類に分かれている
そういったクラスがあるのではなく、条件を満たしていればなんでもOK
(ダックタイピング的ですな)
例えば、ForwardIteratorを入れるべきところに、RamdomAccessIteratorを入れてもOK
(どちらもForwardIteratorの条件を満たしているため)

  • InputIterator
    • 入力のみが可能、要素の参照のみ(read only)、単方向(operator++のみ)
  • OutputIterator
    • 出力のみが可能、要素への代入のみ(write only)、単方向(operator++のみ)
  • ForwardIterator
    • 代入、参照可、単方向(operator++のみ)
  • BidirectionalIterator
    • 代入、参照可、双方向(operator++、operator--)
    • ForwardIterator に operator-- を追加
    • list::iterator、set::iterator、map::iterator
  • RamdomAccessIterator
    • ポインタと同様のインターフェース

関数オブジェクト

アルゴリズムに、任意の処理を行わせる際に用いるオブジェクト
アルゴリズムに実行させたい処理を格納したoperator()を持つ
処理をオブジェクトにすることで、実行する処理を動的に定義できて、柔軟
よく使われるのは、以下の2つ

単項叙述関数(Predicate)

イテレータの中身を引数にもち、戻り値が bool である関数オブジェクト
検索(std::find)等に使用される

二項叙述関数(Compare)

2つのイテレータの中身を引数に取り、a > b の時に true を返す関数オブジェクト
ソート(std::sort)等に使用される

関数オブジェクトの作り方
  • 関数ポインタを渡す
bool func( const int i ){ return i > 30 };

std::vector< int > vec;
// 値が30以上であるイテレータを検索する
// find_ifに渡す関数オブジェクトは単項叙述関数
std::find_if( vec.begin(), vec.end(), &func );

struct ST_FUNC
{
	bool operator() ( const int i ){ return i > 30 };
};

ST_FUNC stFunc;
std::vector< int > vec;
std::find_if( vec.begin(), vec.end(), stFunc );

std::mem_fun_refを使うとイテレータの持つインスタンスで任意の引数が void のメソッドを呼び出すことができる

class Test
{
	int i
	TEST( const int i )
	: i( i )
	{};
	bool func( void ) const { return this->i > 30 };
};

std::vector< Test > test;
std::find_if( vec.begin(), vec.end(), std::mem_fun_ref( &Test::func ) );


std::mem_fun_ref は、引数にクラスのメソッドの参照を持つ、関数オブジェクト
operator() 上にて、イテレータの中身であるクラスのインスタンスを使って、引数で受けたクラスのメソッドを実行する

  • 引数があるクラスメソッドを無理やり使う

std::bind2nd、std::bind1stで引数が1つのメソッドを無理やり引数がvoidのメソッドに変換できる

class Test
{
	int i
	TEST( const int i )
	: i( i )
	{};
	bool func( const int i ) const { return this->i > i };
};

std::vector< Test > test;
std::find_if( vec.begin(), vec.end(), std::bind2nd( std::mem_fun_ref( &Test::func ), 30 ) );

std::bind2ndは、引数が2つの関数オブジェクトを引数1つの関数オブジェクトに変換するテンプレート(関数アダプタ)
1番目の引数に、変換する引数2つの関数オブジェクトを入れて、2番目の引数に引数2つの関数オブジェクトに入れる引数を入れる(ややこしい…)
単項叙述関数に引数を渡して、動的に判断基準を変えたい時等に使用する
std::bind1stは、一番目の引数を固定にする。今の所使い道が思いつかないので詳細は省略

アルゴリズム

イテレータに対して、任意の操作を実行する為のテンプレート関数
いろいろあるので、使いそうなものだけ紹介
関数オブジェクトについては、次章で説明

Function for_each(InputIterator first, InputIterator last, Function f);

InputIterator find(InputIterator first, InputIterator last, const T& value);
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value);
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred);

OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);

void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • クイックソート、Compareでは、二項叙述関数を指定する
  • stable_sortならば、同一の値の順序は保持されたままソートされる
ForwardIterator remove(Forwarditerator first, ForwardIterator last, const T& value);
ForwardIterator remove_if(Forwarditerator first, ForwardIterator last, Predicate pred);
  • 削除。value が一致するか(remove)、単項叙述関数の戻り値が true である要素を全て削除する
  • コンテナにも、erace(Forwarditerator first, ForwardIterator last)がある 
Bidirectionaliterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
  • 区分け。単項叙述関数の戻り値が true である要素と、そうでない要素に分ける
  • 区分けした分かれ目のイテレータを返す
アルゴリズムの組み合わせ

戻り値がイテレータであるアルゴリズムを他のアルゴリズムの引数に入れることで、複雑な処理を行える


例：関数単項叙述関数 func の戻り値がfalseであるイテレータを全て削除する

std::vector<int> vec
// vecの要素を first から last まで消去
vec.erase(
	// func の戻り値がfalseものは、vecの後ろに集められ、その先頭のイテレータを返す
        std::partition(
                vec.begin(),
                vec.end(),
                &func
        ),
        deq.end()
);


だいたいこんな感じ
気が向いたら、適当にはしょってる所とか、随時修正していきます

参考リンク