OrderdDictが要素数に応じてパフォーマンスが劣化していくのは仕方ないんじゃないかな。実際に標準ライブラリに入ったときにどれくらいになるかはともかく、自分で作るしかないよりは、選べる方がいいんじゃないかな。とにかくLinkedListくらいは入ってほしい。