STL



目次
  1. 共通アルゴリズム
    1. 固有関数
      Sitemap | Profile | タグ一覧
      最近の更新
      夢
      		2025/10/21
      お出かけチェックリスト
      		2025/08/30
      韓国
      		2025/08/18
      音楽データをDisplayAudioで聞く
      		2025/08/18
      飛行機はなぜ飛ぶか
      		2025/08/18
      養老孟司
      		2025/08/18
      駅探(3646)
      		2025/08/18
      騙す方が悪いのか・騙される方が悪いのか？
      		2025/08/18
      高麗神社
      		2025/08/18
      鴨川シーワールド
      		2025/08/18
      黒岩一美
      		2025/08/18
      網野善彦
      		2025/08/18
      縄文聖地巡礼
      		2025/08/18
      老荘
      		2025/08/18
      聖方位
      		2025/08/18
      自分のためにやるからこそ、それがチームのためになる
      		2025/08/18
      自転車
      		2025/08/18
      自転車のライトに泣く
      		2025/08/18
      落合史観の用語補足
      		2025/08/18
      落合莞爾
      		2025/08/18


      反復子階層 

      

      
反復子階層
使用Operator
列コンテナ(*)
OAssoc (*2)
Hash (*3)
      入力反復子

      		first != last
      
 ++first
      
 *first
      		


      出力反復子

      		*first = ...



      前方向反復子

      		入力反復子 + 出力反復子


hash<T,U>
      双方向反復子

      		前方向反復子
      
    --first
      		list<T>
set<T>
      multiset<T>
      

      map<T>
      
multimap<T>
   
      		-
      ランダムアクセス反復子

      		双方向反復子
      
    r + n, r - n
      　where r:反復子, n:整数式
      

      r += n, r -= n
      
r - s (r,s: 反復子)
      
r < s, r > s, r <=s, r >=s
      
   
      		T a[n]
      
vector<T>
      
dequelt;T>
         		-
   -
      

      

      (*)

      表において下にあるもの程、上の反復子も使用できる。

      (*2)

      STL の "順序連想コンテナ" のことである。

      (*2)

      STL にはないが、Hash による連想コンテナがあると考えた場合どうなるか

      考えてみたい。
      

      [-] 1. 共通アルゴリズム
      

      

      
関数
T a[n]
vector<T>
deque<T>
list<T>
OAssoc
Hash
      find()

      		O(n)
O(n)
O(n)
O(n)
-
-
      a.find()

      		-
-
-
-
O(log n)
O(1)
      count()

      		O(n)
O(n)
O(n)
O(n)
-
-
      for_each()

      		O(n)
O(n)
O(n)
O(n)
-
-
      search()

      		O(n2)
O(n2)
O(n2)
O(n2)
-
-
      可変列アルゴリズム

      copy()

      		O(n)
O(n)
O(n)
O(n)
-
-
      fill()

      		O(n)
O(n)
O(n)
O(n)
-
-
      generate()

      		O(n)
O(n)
O(n)
O(n)
-
-
      partition()

      		O(n)
O(n)
O(n)
O(n)
-
-
      remove()

      		O(n)
O(n)
O(n)
O(n)
-
-
      replace()

      		O(n)
O(n)
O(n)
O(n)
-
-
      reverse()

      		O(n)
O(n)
O(n)
O(n)
-
-
      swap()

      		O(1)
O(1)
O(1)
O(1)
-
-
      uniq()

      		O(n)
O(n)
O(n)
O(n)
-
-
      Sort アルゴリズム

      sort()

      		O(n log n)
O(n)
O(n log n)
O(n log n)
      集合演算
      

      includes()
      
set_union()
      
set_intersection()
      
set_difference()
      
set_symmetric_difference()
   
      		O(n)
   O(n)
   O(n)
   O(n)
      数値アルゴリズム

      accumulate()
      

      partial_sum()
      
adjacent_difference()
      
innser_product()
   
      		
   
   
   
      

      

      [-] 2. 固有関数
      

      列コンテナに対する共通アルゴリズムは、全て同じ計算量である。しかし、以下の表に示すような違いがある。これがまさに、個々のコンテナクラスが存在する理由である。

      

      
関数
T a[n]
vector<T>
deque<T>
list<T>
OAssoc
Hash *3
       
push_front()
-
-
O(1)
O(1)

-
      push_back()

      		-
O(1)
O(1)
O(1)

-
      pop_back()

      		?
?
?
?

-
      insert()

      		-
O(n+m)
O(n+m) (*1)
O(1) (*2)
O(log n)
O(1)
      erase()

      		?
?
?
?
O(log(n+m))
O(1)
      operator[]

      		O(1)
O(1)
O(1)
-
O(log n)
O(1)
      

      

      *1

      先頭または末尾の近い方の端までの距離に比例した時間がかかる。従って、

      vector より少し速い。
      *2

      任意位置での挿入／削除が速いのが list の特徴である！

      *3

      Hash の特徴は、前後関係を維持しないが定数時間で検索・挿入ができる点である。

      

      






      


      


      
Generated by juli 2.3.2