C,C++/STL

STLとは?

STLとは, Standard Template Library の略で, プログラミング界においてよく使われる言葉です。

標準C++において用意されている非常に便利なものです。

STLいろいろ

STLには, 次のような超便利なものがあります。

• <stack>
  • stack
• <queue>
  • queue
  • priority_queue
• <deque>
  • deque
• <list>
  • list
• <vector>
  • vector
• <map>
  • map
• <set>
  • set
• <algorithm>

説明(stack,vector)は, リンクしてあるのでそれをクリックしていただければと思います。

algorithm

set

stack

再帰DFSよりスタックDFSのほうが関数呼び出しがない分おそらく高速。だがスタックに突っ込むデータ型(pairなど)を作る手間を考えると再帰型のほうが書きやすい。また経路などのスタックトレースをしたい場合は状態を別のコンテナで管理する必要あり(再帰型は戻る時に作れる)。

queue

BFSの簡単な例として2次元座標を対象としたものを以下に示す(queue以外の部分はあくまで一例)。

queue<int> q;
q.push(0), q.push(0); //開始状態を投入
while(!q.empty()){
  int x = q.front(); q.pop();
  int y = q.front(); q.pop();

  //If (x, y) == 終了状態, 何かして break;

  //...

  //For Next State (nx, ny)
  //  If (nx, ny)に移動可能, q.push(nx), q.push(ny);
}

utility