From 18b0c16b6348fcb4bc52455e217cb5d4722f2831 Mon Sep 17 00:00:00 2001 From: Martin Kronbichler Date: Fri, 30 Jun 2023 11:34:12 +0200 Subject: [PATCH] Avoid quadratic complexity in IndexSet::add_ranges --- source/base/index_set.cc | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) diff --git a/source/base/index_set.cc b/source/base/index_set.cc index f51d30ddfb..cf73cf524b 100644 --- a/source/base/index_set.cc +++ b/source/base/index_set.cc @@ -388,8 +388,15 @@ IndexSet::pop_front() void IndexSet::add_range_lower_bound(const Range &new_range) { - ranges.insert(Utilities::lower_bound(ranges.begin(), ranges.end(), new_range), - new_range); + // if the inserted range is already within the range we find by lower_bound, + // there is no need to do anything; we do not try to be clever here and + // leave all other work to compress(). + const auto insert_position = + Utilities::lower_bound(ranges.begin(), ranges.end(), new_range); + if (insert_position == ranges.end() || + insert_position->begin > new_range.begin || + insert_position->end < new_range.end) + ranges.insert(insert_position, new_range); } -- 2.39.5