deque:
list(双方向リスト)への挿入/削除は場所によらず高速だが、各要素に次/前を指す参照が付随するのでメモリ食い。
方やvector(可変長配列)は解放端が末尾にのみあるため、末尾からの距離が離れるほど遅くなる(最悪ケースは先頭要素の追加/削除)
可変長配列のバリエーションであるdequeは先頭と末尾に解放端を持つ。
したがって先頭/末尾要素の挿入/削除が高速。
はじっこを二つ持ったキューであることから Double Ended QUEue と名付けられた。
#include <cliext/algorithm>
#include <cliext/deque>
using namespace System;
using namespace System::Collections::Generic;
using namespace cliext;
int main() {
deque<String^> d(gcnew array<String^> { L"two", L"four" });
d.push_front(L"ONE"); // アタマに追加
d.push_back(L"FIVE"); // ケツに追加
// "four"の手前に追加
d.insert(find(d.begin(), d.end(), gcnew String(L"four")), L"THREE");
for each ( String^ item in d ) {
Console::WriteLine(item);
}
return 0;
}