c++ - 一定時間内に 2 つのコンテナーを追加する

Question

一定の (または少なくとも最小限の線形) 時間で 2 つのコンテナーを追加する方法を探しています。

リンクされたlists マージに気付きましたが、要素を並べ替えているようです。コンテナを別のコンテナに再リンクするためのコンテナ/メソッドはありませんか（たとえば、のようにlist1.last_element.next = list2.first_element）？

Answer 1

std::list::spliceメソッドを使用できます。

std::list<int> list1;
std::list<int> list2;

list1.splice(list1.end(), list2, list2.begin(), list2.end());

list2このコードは、 の内容を の末尾に追加しlist1ます。

Dietmar Kuhl が述べたように、メソッドは挿入する範囲内の要素をカウントする必要があります。

[list2.begin(), list2.end())

したがって、範囲を指定すると、複雑さは線形になります。ただし、リスト全体を追加したいことがわかっている場合は、簡単に行うことができます

list1.splice(list1.end(), list2);

間に合いO(1)ます。