要約

$O(\log N)$ で挿入・削除する方法

std.container.rbtree.RedBlackTree を利用する

以下の方法では $ O(N) $になってしまう。

std.algorithm.mutation.remove()
スライスと配列の結合(~)を使った方法

単純な queue を実装する場合は、先頭の要素を取得・削除するだけでいいので std.range.primitives.popFrontで十分。
参考: popFornt

計算回数が O(N) になる方法について

`std.algorithm.mutation.remove()`

こんな書き方。

import std;

void main() {
    int[] array = [1, 2, 3, 4, 5, 6];
    array = array.remove(2); // array = [1, 2, 4, 5, 6]
}

remove() 後の配列は使えないので、再代入する必要がある。
array.remove(2) 直後(再代入前)のarrayは[1, 2, 4, 5, 6, 6] と削除された分を前に詰めた配列に変更されている。そのときの処理で $O(N)$ のループがあるらしい。
詳細は、以下のコードにある。
std.algorithm.mutation.d

スライスと配列の結合(`~`)を使った方法

import std;

void main() {
    int[] array = [1, 2, 3, 4];
    array = array[0..2] ~ array[3..$]; // array = [1, 2, 4]
    array = array[0..1] ~ 5 ~ array[1..$]; // array = [1, 5, 2, 4]
}

スライスを取る操作は$O(1)$であるが、後ろ側のスライスを結合する際に$O(N)$の時間がかかってしまっているらしい。

計算回数 O(log N) にするにはどうするか

RedBlackTree を使う。

赤黒木という二分木構造がある。

例えば以下のようにできる。
テンプレート引数の true は同じ値の重複を許すことを意味する。
（デフォルトは false なので、この引数を指定しないと木の要素のうち同じ値は1つだけになる。）
実行例のように、重複する要素を削除するときは1つだけ削除される。

import std;

void main() {
    
    auto tree = redBlackTree!(true, int)();

    foreach(_; 0..20) {
        int n = uniform(0, 10);
        tree.insert(n);
    }

    writeln("## Insert 完了 ##");
    tree.length.writeln;
    tree[].writeln;

    writeln("## 0を1つ削除 ##");
    tree.removeKey(0);
    tree.length.writeln;
    tree[].writeln;

}

実行例.txt

## Insert 完了 ##
20
[0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 3, 4, 6, 6, 6, 6, 7, 7, 8, 8]
## 0を1つ削除 ##
19
[0, 0, 0, 0, 0, 2, 2, 2, 2, 3, 4, 6, 6, 6, 6, 7, 7, 8, 8]

本当に $O(\log N)$ で挿入・削除ができているのか確かめてみる。
さっきのコードのループを$10^5$回に増やして時間を計測する。

（仮に1回の挿入・削除に $O(N)$ かかっていれば、N回ループを回しているので全体の計算回数は $O(N^2) \sim 10^{10}回$ となり、現実的な実行時間にならない。）

import std;

void main() {
    
    auto tree = redBlackTree!(true, int)();

    auto insertStart = Clock.currTime();

    foreach(_; 0..10e5) {
        int n = uniform(0, 10);
        tree.insert(n);
    }

    auto insertEnd = Clock.currTime();

    writeln("## INSERT完了 ##");
    writeln(insertEnd - insertStart);

    auto removeStart = Clock.currTime();

    foreach(i; 0..10e5) {
        int n = i.to!int % 10;
        tree.removeKey(n);
    }

    auto removeEnd = Clock.currTime();

    writeln("## REMOVE完了 ##");
    writeln(removeEnd - removeStart);

}

実行結果.txt

## INSERT完了 ##
323 ms and 341 μs
## REMOVE完了 ##
226 ms and 932 μs

良さげ。

まとめ

AtCoderのコンテストで、remove で1回、スライスの結合で1回TLEを出しました。
$N \sim O(10^5)$ 回くらいのループの中で array.sum() を使って、予期せずTLEを出したこともあるので、組み込み関数の中での計算回数を失念しがちです。
使う関数全ての公式ドキュメントを読むのは非現実的だとしても、利用する関数の中でどんな処理をしているか（計算回数、副作用 etc）を意識しておかないといけないなと思います。

参考

RedBlackTree/redBlackTree - multiple declarations - D Programming Language