Я пытаюсь получить пересечение boost::icl::interval_map с данным маленьким boost::icl::interval (который я назову «интервал выбора»). Чаще всего пересечение будет пустым. Но иногда он может содержать интервал (или несколько интервалов, очень редко, поскольку интервал выбора мал).
Я бы ожидал, что сложность этой операции будет O (log (n) + p), где n - количество интервалов в карте, а p - количество интервалов в результате. Поскольку это, вероятно, будет двоичный поиск с последующей итерацией до первого интервала, который больше не пересекает интервал выбора.
В моем случае (небольшой интервал выбора), p <2 практически всегда, поэтому я ожидаю O (log (n)), наравне с простым выбором / поиском. </p>
Но, глядя на документацию Boost , кажется (если я правильно понимаю), что сложность составляет O (n). Правильно ли я понимаю документы, и если да, есть ли у кого-нибудь понимание того, почему это так?