C++STL容器まとめ(二)——関連容器及び容器アダプタ

C++STL容器まとめ(二)

関連容器

概要

関連コンテナタイプ

set

map

コンテナアダプタ

stack

queue

priority_queue

関連コンテナ
概要
set,multiset,map,multimapは非線形のツリー構造であり,具体的には比較的効率的な特殊なバランス二叉ルックアップツリーである赤黒ツリー構造を採用している.
関連コンテナの4つのコンテナクラスは同じ原理を使用するため、彼らのコアのアルゴリズムは一致しているが、それらの応用にはいくつかの違いがあり、まずそれらの違いを説明する.
setは、集合とも呼ばれ、実際には要素の集合であるが、その中に含まれる要素の値は一意であり、一定の順序で配列されており、集合中の各要素は集合中のインスタンスと呼ばれている.内部はチェーンテーブルで組織されているため、挿入時にはvectorよりも速いが、検索と末尾に追加されるのはvectorより遅い.
Multisetは、多重集合であり、その実現方式はsetと似ているが、集合中の要素が一意であることを要求しない.すなわち、集合中の同じ要素が複数回現れることができる.
mapは、「キー値」関係の1対1のデータ記憶能力を提供する.その「キー」はコンテナ内で繰り返してはならず、一定の順序で並べられています(実際にはsetもキー-値関係の記憶と見なすことができますが、キーだけが値を持っていません.mapの特殊な形式です).チェーンテーブル方式で格納されるため、チェーンテーブルのメリットとデメリットも継承されます.
Multimapは、mapの原理と基本的に似ており、コンテナ内で「キー」が一意でなくてもよいことを可能にしています.
関連容器の特徴は明らかで、順序容器に対して、以下のいくつかの主要な特徴がある.

その内部実装は非線形の二叉木構造を採用し、具体的には赤黒樹の構造原理で実現されている.

setとmapは要素の一意性を保証し、mulsetとmulmapはこの属性を拡張し、要素が一意でないことを許可することができる.

要素は規則的な集合であり、デフォルトでは挿入時に昇順に並べられます.

以上の特徴に基づいて、

関連コンテナの要素への挿入と削除操作はvectorよりも速い.vectorは順序記憶であり、関連コンテナはチェーン記憶であるからである.リストより遅いのは、同じチェーン構造であってもリストは線形であり、関連コンテナはツリー構造であり、1つの要素を変更することはリストよりも他の要素の変動が多く、ソートされているため、挿入と削除のたびに要素を並べ替える必要があります.

関連コンテナの要素の検索操作はvectorより遅いがlistよりずっと速い.vectorはシーケンスの連続記憶であり、もちろん及ばないが、チェーン式のlistに比べて速いのはlistが1つずつ検索しているためであり、検索時間は容器の大きさに比例しているが、関連容器検索の複雑さは基本的にLog(N)であり、例えば1000個のレコードがあれば、最大10回、100000個のレコードを検索し、最大20回検索する.容器が大きいほど、関連容器のlistに対する優位性が現れる.

使用上setはvector,deque,listの最大の特徴はsetが内部ソートされていることであり,これはクエリ上vectorに劣るがlistよりはるかに強い.

はmapを使用する機能に取って代わることができず、「キー値」関係のデータを保存し、このキー値関係はクラス配列の方式を採用している.配列は数値型の下付き文字で要素をインデックスする位置であり、mapは文字型キーワードで要素をインデックスする位置である.上mapの使用においても、他のコンテナではできないデータを下付きで検索できる配列操作が提供されています.もちろんsetも含まれています.

関連コンテナタイプ
キーワード順に要素を保存
name
description
map
関連配列;キーワードの保存-値ペア
set
キーワード取値、すなわちキーワードのみを保存するコンテナ
multimap
キーワードが繰り返されるmap
multiset
キーワードの繰り返し可能set
むじゅんしゅうごう
name
description
unordered_map
ハッシュ関数で組織されたmap
unordered_set
ハッシュ関数で組織されたset
unordered_multimap
ハッシュ組織のmap;キーワードの繰り返し
unordered_multiset
ハッシュ組織のset;キーワードの繰り返し
set
c++stlコレクション(Set)は、ソートされたオブジェクトを含む関連コンテナです.set/multisetは、所定のソート基準に基づいて要素を自動的にソートします.両者の違いは、前者は要素の重複を許さず、後者は許容することである.

要素の値を直接変更することはできません.それは元の正しい順序を乱すため、要素の値を変更するには古い要素を削除する必要があります.新しい要素

を挿入します.

は、直接アクセス要素の操作関数を提供せず、反復器による間接アクセスのみが可能であり、反復器の観点から、要素値は定数

である.

要素比較動作は、型別が同じ容器(すなわち、要素とソート基準が同じでなければならない)

にのみ使用できる.
一般的な操作

pair<iterator,bool> insert (const value_type& val); //Extends the container by inserting new elements, effectively increasing the container size by the number of elements inserted.

const_iterator find (const value_type& val) const; //Searches the container for an element equivalent to val and returns an iterator to it if found, otherwise it returns an iterator to set::end.
iterator find (const value_type& val);

iterator  erase (const_iterator position);
size_type erase (const value_type& val);

size_type count (const value_type& val) const; //Searches the container for elements equivalent to val and returns the number of matches.
iterator upper_bound (const value_type& val); //Returns an iterator pointing to the first element in the container which is considered to go after val.
iterator lower_bound (const value_type& val); //Returns an iterator pointing to the first element in the container which is not considered to go before val 
pair<iterator,iterator> equal_range (const value_type& val); //Returns the bounds of a range that includes all the elements in the container that are equivalent to val.

map
ヘッダファイルは反復器の場合、keyを変更することなく実値を変更できます.

key_compare key_comp() const; //Returns a copy of the comparison object used by the container to compare keys.
value_compare value_comp() const; //Returns a comparison object that can be used to compare two elements to get whether the key of the first one goes before the second.

iterator find (const key_type& k);

begin()         //    map      
clear(）        //      
count()         //           
empty()         //  map     true
end()           //    map      
equal_range()   //           
erase()         //      
find()          //      
get_allocator() //  map    
insert()        //    
key_comp()      //      key   
lower_bound()   //    >=          
max_size()      //             
rbegin()        //      map        
rend()          //      map        
size()          //  map      
swap()           //    map
upper_bound()    //    >          
value_comp()     //      value   

コンテナアダプタ
STLには、スタックスタック、キューqueue、優先度priorityの3つのアダプタがあります.queue .
アダプタはコンテナのインタフェースであり、それ自体が直接要素を保存することはできません.要素を保存するメカニズムは、アダプタを「コンテナを保存し、このコンテナはすべての要素を保存する」と見なす別の順序のコンテナを呼び出すことです.
STLで提供される3つのアダプタは、ある順序の容器によって実現することができる.デフォルトではstackとqueueはdequeコンテナに基づいて実装され、priority_Queueはvectorコンテナに基づいて実現される.もちろん、アダプタを作成するときに特定のインプリメンテーションコンテナを指定することもできます.アダプタを作成するときに、2番目のパラメータに特定の順序コンテナを指定すると、アダプタのデフォルトのインプリメンテーションを上書きできます.
アダプタの特徴により、1つのアダプタはいずれの順序のコンテナでも実現できるわけではありません.
スタックstackの特徴は後進先出であるため、関連する基本コンテナは任意の順序コンテナであってもよい.これらのコンテナタイプ構造はスタックの操作を要求することができ、push_を提供するからである.back 、pop_backとback操作;
キューqueueの特徴は、アダプタが関連付けられたベースコンテナにpop_を提供する必要があることです.frontは動作するためvector容器に確立できない.
優先キューpriority_Queueアダプタはランダムアクセス機能を要求するためlistコンテナには確立できません.
stack
ヘッダファイル
一般的な操作

void push (value_type&& val); //Inserts a new element at the top of the stack, above its current top element. 
reference& top(); //Returns a reference to the top element in the stack. 
void pop(); //Remove top element
void swap (stack& x) //Exchanges the contents of the container adaptor (*this) by those of x.

queue
ヘッダファイル

empty()
size()
front()
back()
push()
emplace()
pop()
swap()

priority_queue
priority_queue呼び出しSTLの中のmake_heap(), pop_heap(), push_Heap()アルゴリズム実装.
テンプレート宣言には3つのパラメータがあります:priority_Queue STLではデフォルトでvectorが使用されています.比較方式のデフォルトはoperator<であるため、宣言時に後の2つのパラメータをデフォルトにすると、優先キューは大トップスタックであり、キューヘッダ要素が最大となる.

empty()
size()
top()
push()
emplace()
pop()
swap()

//           
#include 
#include 
 
using namespace std;
 
struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}
};
 
struct cmp{
    bool operator() ( Node a, Node b ){
        if( a.x== b.x ) return a.y> b.y;
         
        return a.x> b.x; }
};
 
int main(){
    priority_queue<Node, vector<Node>, cmp> q;
     
    for( int i= 0; i< 10; ++i )
    q.push( Node( rand(), rand() ) );
     
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
     
    getchar();
    return 0;
}