STLを活用しよう

この記事は熊本高専Advent Calendar2017 3日目の記事です.


数か月ぶりの投稿になります.民です.最近書いてなかったので僕が言えたことではないですがみんなブログ書きませんね.そもそも存在を忘れていそう

用途にもよりますが皆さんプログラミング言語は主に何を使用しているでしょうか?
僕は主にC++とHaskellを使っていて,新入生に対してもC言語を教えているので今回はC++のSTLについてお話しようと思います.

STLとは?

STLとは,Standard Template Libraryの略で,C++の標準ライブラリの1つになります.ヘッダファイルをインクルードすることで使うことができます.
しかしここで注意してほしいのは,Cの標準ライブラリのように関数名だけを書くだけでは駄目で,std名前空間を指定する必要があります.名前空間については説明が面倒なのでC++の参考書を読むなりググるなりしてください.

今回はSTLの中でも自分が特に便利だと思うものを紹介します.今回はあくまで紹介なので使い方に関しては参考書読(ry

~アルゴリズム系~

・std::sort

algorithmヘッダをインクルードすることで使用することができます.
概要としては名前そのままで,引数の範囲をソートします.
クイックソート(C++11以降ではイントロソート)で実装されており,計算量はO(N log N).

・std::next_permutation

algorithmヘッダをインクルードすることで使用することができます.
順列を生成してくれます.ただしソートされている必要があります.計算量は最大O(N).

・std::lower_bound

algorithmヘッダをインクルードすることで使用することができます.
指定された要素以上の値が現れる最初の位置のイテレータを取得することができます.いわゆる二分探索みたいなものです.計算量はO(log N).

・std::upper_bound

algorithmヘッダをインクルードすることで使用することができます.
指定された要素より大きい値が現れる最初の位置のイテレータを取得することができます.std::lower_bountと同じく二分探索みたいなものです.計算量はO(log N).

~データ構造系~

・std::vector

個人的にダントツで使ってます.重いけど便利.
vectorヘッダをインクルードすることで使用することができます.
いわゆる動的配列と言われるもので,可変長配列として実装されています.配列の動的確保と何が違うかというと,vector自体がストレージを管理しているため,自動的に領域が確保されます.

 ・各要素への添字アクセス(定数時間)
 ・全要素の両方向の走査(線形時間)
 ・末尾への要素の追加・削除(償却定数時間)
という点で優れているのが特徴です.いろいろなメンバ関数があるのでぜひ触ってみましょう.

・std::map

mapヘッダをインクルードすることで使用することができます.
キーとそれに対応する値を格納するデータ構造,いわゆる連想配列といわれるもので,二分木(赤黒木)で実装されています.
こちらにもさまざまなメンバ関数が存在します.

・std::priority_queue

queueヘッダをインクルードすることで使用することができます.
いわゆる優先度付きキューといわれるものになります.

 

以上,本当にざっと紹介しただけでしたがSTLはかなりの数が存在し,正直列挙できるような量ではありませんのでその都度調べたりしましょう.
これを機にSTLや標準ライブラリに対して興味を持ってもらえたらなと思います.
アルゴリズムだったりデータ構造だったりを一から実装していくのもアリですが,ライブラリに存在するものは積極的に活用していくことしていくことをおすすめします.

 

次は高専プロコンの振り返りとかをAdventCalendarも兼ねて誰か書いてくれるはず…書いてくれるよね?
 

 

 

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です