計算速度整理(データ構造):C++
データ構造の勉強をしているのですが解説記事は複数あるのでこちらでは計算速度についてまとめます。
map
宣言
map<Keyの型, Valueの型> 変数名;
操作など
| 操作 | 記法 | 計算量 |
|---|---|---|
| 値の追加 | 変数[key] = value; | O(log N) |
| 値の削除 | 変数.erase(key); | O(log N) |
| 値へのアクセス | 変数.at(key) | O(log N) |
| 所属判定 | 変数.count(key) | O(log N) |
| 要素数の取得 | 変数.size() | O(1) |
set
宣言
set<値の型> 変数名;
操作など
| 操作 | 記法 | 計算量 |
|---|---|---|
| 値の追加 | 変数.insert(値); | O(log N) |
| 値の削除 | 変数.erase(値); | O(log N) |
| 所属判定 | 変数.count(値) | O(log N) |
| 要素数の取得 | 変数.size() | O(1) |
| 最小値の取得 | *begin(変数) | O(1) |
| 最大値の取得 | *rbegin(変数) | O(1) |
queue
宣言
queue<型> 変数名;
操作など
| 操作 | 記法 | 計算量 |
|---|---|---|
| 要素の追加 | 変数.push(値); | O(1) |
| 先頭要素の削除 | 変数.pop(); | O(1) |
| 先頭要素へのアクセス | 変数.front(); | O(1) |
| 要素数の取得 | 変数.size() | O(1) |
stack
宣言
stack<値の型> 変数名;
操作など
| 操作 | 記法 | 計算量 |
|---|---|---|
| 要素の追加 | 変数.push(値); | O(logN) |
| 最大要素の削除 | 変数.pop(); | O(logN) |
| 最大要素へのアクセス | 変数.top(); | O(1) |
| 要素数の取得 | 変数.size() | O(1) |
priority_queue
宣言
priority_queue<型> 変数;
操作など
| 操作 | 記法 | 計算量 |
|---|---|---|
| 値の追加 | 変数.push(); | O(1) |
| 先頭要素の削除 | 変数.pop(); | O(1) |
| 次のへのアクセス | 変数.top(); | O(1) |
| 要素数の取得 | 変数.size() | O(1) |
deque
宣言
deque<値の型> 変数名;
操作など
| 操作 | 記法 | 計算量 |
|---|---|---|
| 先頭要素の追加 | 変数.push_front(値); | O(1) |
| 末尾要素の追加 | 変数.push_back(値); | O(1) |
| 先頭要素の削除 | 変数.pop_front(); | O(1) |
| 末尾要素の追加 | 変数.pop_back(); | O(1) |
| 先頭要素へのアクセス | 変数.front(); | O(1) |
| 末尾要素へのアクセス | 変数.back(); | O(1) |
| i番要素へのアクセス | 変数.at(i); | O(1) |
| 要素数の取得 | 変数.size() | O(1) |
