D言語には言語仕様に動的配列や連想配列が存在しており便利ですが、
もう少し色々なデータ構造を使いたいですよね。
DにはC++のSTLコンテナのような「std.container」が標準ライブラリに存在します。
調べつつ使ってみたものをいくつか紹介します。
#Array (std.container.array)
動的配列のコンテナ。C++のstd::vectorに相当します。
ランダムアクセスが可能で、Dの配列を置き換えることも可能です。
Dの動的配列と違うところは、このコンテナで確保されたメモリはGCに依存しないで独自に管理されます。
Array(T)構造体が破棄されるタイミングでメモリも一緒に解放されます。
ファイルや画像のバッファ等巨大なメモリを一時的に確保する際に使えそうですね。
import std.container;
import std.stdio;
void main()
{
Array!(int) c;
// 末尾に5を追加
c ~= 2;
// 末尾に5を追加
c.insertBack(5);
writeln(c.length); // => 2
writeln(c[1]); // => 5
// 末尾の要素を1つ削除
c.removeBack();
writeln(c.length); // => 1
// 要素数を2000にする
c.length = 2000;
writeln(c.length); // => 2000
}
#SList (std.container.slist)
単方向な連結リスト。
要素の追加にinsertFront、削除にremoveFront。
Rangeを使えば途中の追加、削除も高速に行えます。
import std.container;
import std.stdio;
import std.range;
void main()
{
SList!(int) c;
// 要素を追加していく
foreach (e; [5, 8, 3, 4, 1, 8, 9, 12]) {
c.insertFront(e);
}
eachWriteln(c); // 12,9,8,1,4,3,8,5
// 2個取り出す
c.removeFront(2);
eachWriteln(c); // 8,1,4,3,8,5
// 列挙しつつ5以下の要素を削除
for (auto r = c[]; !r.empty; ) {
if (r.front <= 5) {
r = c.linearRemove(r.take(1));
} else {
r.popFront();
}
}
eachWriteln(c); // 8,8
}
void eachWriteln(T)(T c)
{
foreach (e; c) {
write(e, ",");
}
writeln("");
}
#DList (std.container.dlist)
双方向な連結リスト。C++のstd::listに相当。
要素の追加にinsertBack,insertFront、削除にremoveBack,removeFront
Rangeを使えば途中の追加、削除も高速に行えます。
import std.container;
import std.stdio;
import std.range;
void main()
{
DList!(int) c;
// 要素を追加していく
foreach (e; [5, 8, 3, 4, 1, 8, 9, 12]) {
c.insertBack(e);
}
eachWriteln(c); // 5,8,3,4,1,8,9,12
// 先頭から2個取り出す
c.removeFront(2);
eachWriteln(c); // 3,4,1,8,9,12
// 5以下の要素を2倍にする
for (auto r = c[]; !r.empty; r.popFront()) {
if (r.front <= 5) {
r.front = r.front * 2;
}
}
eachWriteln(c); // 6,3,8,4,2,1,8,9,12
}
void eachWriteln(T)(T c)
{
foreach (e; c) {
write(e, ",");
}
writeln("");
}
#RedBlackTree (std.container.rbtree)
赤黒木アルゴリズムの二分木コンテナ。C++のstd::setに相当。
常にソートされており、検索、追加は高速に行うことができます。
こいつは他のコンテナとは違ってクラスなので、使う際にはnewする必要があります。
import std.container;
import std.stdio;
import std.range;
void main()
{
auto c = new RedBlackTree!(int);
// 要素を追加していく
foreach (e; [5, 8, 3, 4, 1, 8, 9, 12]) {
c.insert(e);
}
eachWriteln(c); // 1,3,4,5,8,9,12
// 8の要素を削除
c.removeKey(8);
eachWriteln(c); // 1,3,4,5,9,12
// 5未満の要素を表示
eachWriteln(c.lowerBound(5)); // 1,3,4
}
void eachWriteln(T)(T c)
{
foreach (e; c) {
write(e, ",");
}
writeln("");
}
#あとがき
この辺のコンテナは標準ライブラリに存在することを知らなくて、
自分で実装してしまうケースが結構あったりします（実際に実装してしまったことがある）
std.algorithm等はRangeに対して処理を行う機能が多いため、自分で実装するよりは
std.containerのものを使用したほうが後々楽ができると思います。
この記事はアドカレ用に調べて書いたものです。使う用途としては一例程度に留まっていますので、
極めたい方はググったりするなり、std.containerのリファレンスを見てください。