STL



目次
  1. 共通アルゴリズム
    1. 固有関数
      Sitemap | Profile | タグ一覧
      最近の更新
      ドライランのありがたみを改めて知る
      		2024/04/04
      伊豆半島
      		2024/03/31
      お出かけチェックリスト
      		2024/03/29
      Ruby
      		2024/03/27
      Kubernetes
      		2024/03/22
      音楽データをDisplayAudioで聞く
      		2024/03/09
      Redmine
      		2024/02/05
      git
      		2024/02/02
      経済
      		2024/01/08
      どうする家康
      		2023/12/17
      MX-Linux
      		2023/11/06
      國體関連学-休学のご連絡
      		2023/08/13
      Debian
      		2023/08/02
      CentOS
      		2023/06/13
      Dell-XPS13
      		2023/05/23
      ベルト
      		2023/05/18
      SourceForge
      		2023/04/17
      確定申告
      		2023/02/19
      さらば「まぐまぐ」
      		2023/01/09
      風猷縄学
      		2022/11/23


      反復子階層 

      

      
反復子階層
使用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