これは何？
コンテナクラスとかコレクションライブラリとか呼ばれるものの各言語の対応について知りたくなったので、調べた。
コンテナの色々
思いつく限り書いていくと。
- 配列・vector・slice
- リンクリスト
- 双方向リスト
- 単方向リスト
- deque
- ring buffer
- 辞書 / 集合 / マルチ辞書 / マルチ集合
- 順序がないやつ
- 順序があるやつ
- 挿入削除が速いやつ
- 挿入削除が遅いやつ
当然全部網羅とかはありえないわけだけど、これぐらいで。
配列・vector・slice
要素をダラダラ並べた感じ。
インデックスアクセスが速い。末尾への追加もたいてい速い。
末尾以外に追加削除すると時間がかかる。
配列 (Array) と呼ばれることもあるし、vector と呼ばれることも Slice と呼ばれることもある。
List と呼ばれることもある。私はリンクリストを先に想像するのでそう呼びたくはないんだけれども。
リンクリスト
「次はここ」という情報で要素をたどる。
双方向と単方向があって、単方向だと先頭方向にたどることができなくてちょっと不便だけど、その分メモリが少なくて済む。
どこに追加するのも速いけど、インデックスアクセスが遅い。
deque
インデックスアクセスが速い。
先頭または末尾への追加・削除が速い。
先頭や末尾から遠い場所の追加・削除は遅い。
どんどん追加すると適宜メモリ確保されるので、メモリが許す限りどんどん追加できる。
ring buffer
インデックスアクセスが速い。
先頭または末尾への追加・削除が速い。
先頭や末尾から遠い場所の追加・削除は遅い。
どんどん追加してもメモリ確保は行われず、最初に決めたサイズを超えると追加不可能になる（あるいは黙ってぶっ壊れる）。
辞書 / 集合 / マルチ辞書 / マルチ集合
キーと値のペアを保存するものたち。
値が一種類しかない（要素のない構造体とか）場合、あるいはそもそも値がない場合、それは集合とみなせる
キーの重複を許せばマルチ辞書 / マルチ集合。
許さないのなら辞書 / 集合。
順序がないやつ
中身は Hash を使うのが普通。
順序があるやつ - 挿入削除が速いやつ
中身は赤黒木が普通だと思うけどよく知らない。
挿入も削除も検索も、要素数 N で $ O(log N) $ となる。
順序があるやつ - 挿入削除が遅いやつ
中身は配列。
検索は、要素数 N で $ O(log N) $ で速いんだけど、挿入削除は $ O(N) $ で遅い。
挿入削除があまり発生しない状況では赤黒木よりお得。
各言語の対応
各言語の対応を記述するために、一旦名前をつける。
| 前述の名前 | 以降使う名前 |
|---|---|
| 配列・vector・slice | vector |
| リンクリスト・双方向 | dlist |
| リンクリスト・単方向 | slist |
| deque | deque |
| ring buffer | ring |
| 辞書 - 順序なし | uo-map |
| 辞書 - 順序有り・挿入削除が速い | o-map |
| 辞書 - 順序有り・挿入削除が遅い | f-map |
| 集合 - 順序なし | uo-set |
| 集合 - 順序有り・挿入削除が速い | o-set |
| 集合 - 順序有り・挿入削除が遅い | f-set |
| マルチ辞書 - 順序なし | uo-mmap |
| マルチ辞書 - 順序有り・挿入削除が速い | o-mmap |
| マルチ辞書 - 順序有り・挿入削除が遅い | f-mmap |
| マルチ集合 - 順序なし | uo-mset |
| マルチ集合 - 順序有り・挿入削除が速い | o-mset |
| マルチ集合 - 順序有り・挿入削除が遅い | f-mset |
C++
| 種類 | C++ での名前 | 補足 |
|---|---|---|
| vector | std::vector |
|
| dlist | std::list |
|
| slist | std::forward_list |
C++11 以降 |
| deque | std::deque |
|
| ring | boost::circular_buffer |
|
| uo-map | std::unordered_map |
C++11 以降 |
| o-map | std::map |
C++11 以降 |
| f-map |
std::flat_map / boost::flat_map
|
std::flat_map は C++23 以降 かな |
| uo-set | std::unordered_set |
C++11 以降 |
| o-set | std::set |
C++11 以降 |
| f-set |
std::flat_set / boost::flat_set
|
std::flat_set は C++23 以降 かな |
| uo-mmap | std::unordered_multimap |
C++11 以降 |
| o-mmap | std::multimap |
C++11 以降 |
| f-mmap |
std::flat_multimap / boost::flat_multimap
|
std::flat_multimap は C++23 以降 かな |
| uo-mset | std::unordered_multiset |
C++11 以降 |
| o-mset | std::multiset |
C++11 以降 |
| f-mset |
std::flat_multiset / boost::flat_multiset
|
std::flat_multiset は C++23 以降 かな |
この記事のための調査で std::flat_map などの存在を知った。
Java
| 種類 | Java での名前 | 補足 |
|---|---|---|
| vector | ArrayList |
|
| dlist | LinkedList |
|
| slist | ? | |
| deque | ArrayDeque |
|
| ring | ? | |
| uo-map | HashMap |
|
| o-map | TreeMap |
|
| f-map | ? | |
| uo-set | HashSet |
|
| o-set | TreeSet |
|
| f-set | ? | |
| *-mmap | ? | |
| *-mset | ? |
マルチ辞書・マルチ集合 が無いような気がする。
Java ユーザーじゃないので自信ないけど。
C# っていうか .NET Framework
| 種類 | .NET での名前 | 補足 |
|---|---|---|
| vector | List |
|
| dlist | LinkedList |
|
| slist | ? | |
| deque | ? | |
| ring | ? | |
| uo-map | Dictionary |
|
| o-map | SortedDictionary |
|
| f-map | ? | |
| uo-set | HashSet |
|
| o-set | SortedList |
|
| f-set | ? | |
| *-mmap | ? | |
| *-mset | ? |
Java 同様、マルチ辞書・マルチ集合 が無いような気がする。
.NET Framework もあまり使わないので自信ないけど。
Java のほうが名前がわかりやすい気がする（個人の感想です）。
C++/CLI を使えば C++ のコンテナクラスが全部使えるのかもしれない（よくわかってない）けど、それは数えないことにした。
Python3
| 種類 | Python での名前 | 補足 |
|---|---|---|
| vector | list |
言語組み込み |
| dlist | ? | |
| slist | ? | |
| deque | collections.deque |
|
| ring | ? | |
| uo-map | dict |
言語組み込み |
| o-map | ? | |
| f-map | ? | |
| uo-set | set |
言語組み込み |
| o-set | ? | |
| f-set | ? | |
| *-mmap | ? | |
| *-mset | ? |
なぜか deque だけある。
Go 言語
| 種類 | Go での名前 | 補足 |
|---|---|---|
| vector | スライス | 言語組み込み |
| dlist | List |
"container/list" |
| slist | ? | |
| deque | ? | |
| ring | Ring |
"container/ring" |
| uo-map | map |
言語組み込み |
| o-map | ? | |
| f-map | ? | |
| uo-set | ? | |
| o-set | ? | |
| f-set | ? | |
| *-mmap | ? | |
| *-mset | ? |
コンテナクラスは 1.20 とかもっと後で一気に入るんじゃないかと想像してるんだけど、今は貧弱。
でもなぜか ring と dlist だけはある。
まとめ
| コンテナ ＼ 言語とか | C++ | Java | C# | Python | Go |
|---|---|---|---|---|---|
| vector | ✅ | ✅ | ✅ | ✅ | ✅ |
| dlist | ✅ | ✅ | ✅ | ✅ | |
| slist | ✅ | ||||
| deque | ✅ | ✅ | ✅ | ||
| ring | *1 | ✅ | |||
| uo-map | ✅ | ✅ | ✅ | ✅ | ✅ |
| o-map | ✅ | ✅ | ✅ | ||
| f-map | *2 | ||||
| uo-set | ✅ | ✅ | ✅ | ✅ | |
| o-set | ✅ | ✅ | ✅ | ||
| f-set | *2 | ||||
| uo-mmap | ✅ | ||||
| o-mmap | ✅ | ||||
| f-mmap | *2 | ||||
| uo-mset | ✅ | ||||
| o-mset | ✅ | ||||
| f-mset | *2 |
*1 boost にある。
*2 boost にある。C++23 にあるかも。
こうしてみると、C++ はリッチだなと思う。
boost なしでも殆どのデータ構造が揃っている。
逆に、ほとんどまったくなにもない C言語とか大変だったなと思う。
そういえば、ruby もあんまりコレクションクラスがない。なさ過ぎて表にしなかったぐらい。
Rust・Zig あたりも気になるけど、今日のところはこれぐらいで。
Java / C# / Go は、標準ライブラリに限定しなければ誰かが作ったコレクションクラスが使えるんだろうと思うけど、標準もしくは準標準ぐらいのものに入れておいてよ、と思う。