c++ - セットと両端キューに挿入するにはどうすればよいですか

Question

連続した整数の範囲をセットに挿入し、デキューの最後にあるセットの新しい要素ごとに、反復と同じ順序で挿入する必要がある C++ 関数があります。以下は、それぞれが O(log(n)) である挿入が繰り返されるため、およそ O(log(n) * n) であるソリューションです。O(n) ソリューションを取得したいと思います。ヒントの反復位置を取る set::insert() を使用したいのですが、そうすると、アイテムが既にセットに含まれているかどうかを一定時間で判断する方法がわかりません。

#include <deque>
#include <set>

void
insertUnique(const int beginOffset,
             const int endOffset,
             std::set<int> &sent,
             std::deque<int> &recent)
{
  for (int offset = beginOffset; offset < endOffset; ++offset) {
    const bool inserted = sent.insert(offset).second;

    if (inserted) {
      recent.push_back(offset);
    }
  }
}

これを O(n) にリファクタリングし、関数の引数を変更せずに同じ作業を行う方法はありますか? イテレータのヒントを挿入し、アイテムが挿入されたかどうかを知る方法はありますか?