Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?

Например дано множество N: set<int> array;
Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.:
1. Итератор указывающий на первое число больше чем 99;
2. Итератор указывающий на первое число больше чем 7999.
(вроде правильно)

Вроде просто, но что-то ничего толкового в голову не приходит.
Специализированный "доморощенный" бинарный поиск aka велосипед?
Из algorithm подойдет что-нибудь?


Спасибо!

Здравствуйте, kvasya, Вы писали:


K>Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?

K>Например дано множество N: set<int> array;
K>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.:
K>1. Итератор указывающий на первое число больше чем 99;
K>2. Итератор указывающий на первое число больше чем 7999.
K>(вроде правильно)

вызывать у сет'а метод lower_bound, от начала до конца, потом upper_bound от полученного итератора до конца

Здравствуйте, Sni4ok, Вы писали:

S>Здравствуйте, kvasya, Вы писали:


K>>Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?

K>>Например дано множество N: set<int> array;
K>>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.:
K>>1. Итератор указывающий на первое число больше чем 99;
K>>2. Итератор указывающий на первое число больше чем 7999.
K>>(вроде правильно)

S>вызывать у сет'а метод lower_bound, от начала до конца, потом upper_bound от полученного итератора до конца

Думается это именно то, что мне нужно по условию задачи. Буду учить матчасть.

Спасибо

Здравствуйте, kvasya, Вы писали:

K>Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?

K>Например дано множество N: set<int> array;
K>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.:
K>1. Итератор указывающий на первое число больше чем 99;
K>2. Итератор указывающий на первое число больше чем 7999.
K>(вроде правильно)

Если пренебречь микрооптимизациями, то:

std::set<int>::const_iterator lowIter = array.lower_bound(100);
std::set<int>::const_iterator highIter = array.lower_bound(8000);

Это потребует 2*log(n) операций. Можно написать собственный алгоритм, который будет искать оба значения сразу, и «раздваиваться», только когда оба конца окажутся в разных половинах рассматриваемого интервала, но он будет эффективнее не более чем в два раза.

Здравствуйте, Sni4ok, Вы писали:

K>>Например дано множество N: set<int> array;
K>>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.:
K>>1. Итератор указывающий на первое число больше чем 99;
K>>2. Итератор указывающий на первое число больше чем 7999.
K>>(вроде правильно)

S>вызывать у сет'а метод lower_bound, от начала до конца, потом upper_bound от полученного итератора до конца

Есть мнение, что собственный метод set::lower_bound по всему множеству будет быстрее, чем общий алгоритм std::lower_bound по подмножеству. Из-за специфической организации std::set’а: собственный метод пойдёт в точности по узлам дерева, а общий алгоритм — как попало.

Здравствуйте, kvasya, Вы писали:


K>Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?

set<int> xs;
set<int>::const_iterator
    i = xs.upper_bound(k), // *(i-1) <= k < *i
    j = xs.lower_bound(q); // *(j-1) < q <= *j

for_each(i,j, do_what_you_want);

Здравствуйте, Кодт, Вы писали:

немножко оптимизации...

set<int> xs;
set<int>::const_iterator
    i = xs.upper_bound(k), // *(i-1) <= k < *i
    j = (i==xs.end())?i:xs.lower_bound(q); // *(j-1) < q <= *j

for_each(i,j, do_what_you_want);