std::multimap получает два диапазона

Я использую C++ std::multimap, и мне приходится перебирать два разных ключа. Есть ли эффективный способ сделать это, кроме создания двух диапазонов и отдельного цикла по этим диапазонам?

Вот как я это делаю сейчас:

std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range;
std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range2;

// get the range of String key
range = multimap.equal_range(key1);
range2 = multimap.equal_range(key2);

for (std::multimap<String, Object*>::iterator it = range.first; it != range.second; ++it)
{
    ...
}
for (std::multimap<String, Object*>::iterator it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}

c++ range iterator std multimap
person Kaiser Wilhelm    schedule 07.09.2011    source источник
comment
почему вы считаете, что это неэффективно?   -  person Andriy Tylychko    schedule 07.09.2011
comment
Я впервые использую мультикарты, поэтому я не слишком хорошо с ними знаком. Я буду делать много работы в этих циклах, и мне было интересно, есть ли другая операция, где вы могли бы получить два диапазона одновременно или что-то в этом роде.   -  person Kaiser Wilhelm    schedule 07.09.2011
comment
Можете ли вы привести пример ключей, где ключи перекрываются, но не равны друг другу? Может быть, мой мозг сырой, но кажется, что простая проверка на равенство ключей сделает это. Для меня это имеет больше смысла, если у вас есть отдельные нижняя и верхняя границы для каждого запроса.   -  person Tom Kerr    schedule 07.09.2011
comment
это отличный пример, когда один typedef может убрать большую половину кода и сделать код значительно более читабельным: typedef std::multimap<String, Object*>::iterator Iter   -  person Andriy Tylychko    schedule 07.09.2011

Ответы (3)


arrow_upward
3
arrow_downward

Код, с которого вы начали, самый простой.

Если вы действительно хотите выполнить итерацию по двум диапазонам в одном и том же цикле, вы можете создать собственный итератор, который принимает два диапазона итераторов, выполняет итерацию по первому до тех пор, пока он не будет выполнен, а затем переключается на второй. Это, вероятно, больше проблем, чем оно того стоит, так как вам нужно будет реализовать все элементы итератора самостоятельно.

Редактировать: я слишком много думал об этом; легко просто изменить две петли в одну.

for (std::multimap<String, Object*>::iterator it = range.first; it != range2.second; ++it)
{
    if (it == range.second)
    {
        it = range2.first;
        if (it == range2.second)
            break;
    }
    ...
}
person Mark Ransom    schedule 07.09.2011
comment
Я тоже думал об этом. Однако должны ли эти два ключа быть рядом друг с другом, чтобы это работало? Например, если у меня есть 3 ключа, и я хочу перебрать 1-й и 3-й, не будет ли он включать в себя 2-й? Или эти операторы if это исправляют? - person Kaiser Wilhelm; 07.09.2011
comment
@Kaiser, операторы if обрабатывают переход от первого диапазона ко второму. Они могут даже выйти из строя. Единственное, что они не могут сделать, это пересечься; если range2 включает range.second, то вы получите бесконечный цикл. - person Mark Ransom; 07.09.2011
comment
АА, вижу. Мой диапазон2 статичен, а диапазон1 всегда будет другим. Они никогда не должны пересекаться правильно? Так как multimap сортирует его при вставке? - person Kaiser Wilhelm; 07.09.2011
comment
@Kaiser, пока ключи разные и вы используете equal_range, как в своем вопросе, диапазоны не будут пересекаться. Я также проверил, чтобы ваши итераторы range2 не были признаны недействительными при вставке: stackoverflow. com/questions/6438086/iterator-invalidation-rules - person Mark Ransom; 07.09.2011

arrow_upward
3
arrow_downward

Boost делает это, конечно. Использование Boost.Range и его функции join даст вам то, что вы хотите. Дополнительные сведения см. в разделе Увеличение библиотеки диапазонов: последовательное обход двух диапазонов.

person deft_code    schedule 07.09.2011
comment
Спасибо, Boost кажется действительно мощным. К сожалению, моя компания старая школа и ненавидит все новое... Думаю, им придется довольствоваться неэффективностью. - person Kaiser Wilhelm; 07.09.2011
comment
на этот раз дело не в эффективности, а в удобстве - person Andriy Tylychko; 07.09.2011

arrow_upward
0
arrow_downward

Если у вас есть доступ к C++-11 (Visual Studio 10+, gcc-4.5+) и вам разрешено его использовать, auto это настоящая жемчужина:

// get the range of String key
auto range = multimap.equal_range(key1);
auto range2 = multimap.equal_range(key2);

for (auto it = range.first; it != range.second; ++it)
{
    ...
}
for (auto it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}

В любом случае, я бы просто проверил ключи и выполнил второй цикл, только если key2 != key1. Проверка итераторов каждый раз в цикле требует определенных затрат.

std::set_difference первого диапазона из второго может упростить код. Может быть, std::set_union два диапазона и вставить через back_inserter в набор, чтобы получить только одну копию?

Некоторые эксперименты могут быть в порядке. Не забудьте поставить свое первое предположение в миксе. Это может удивить вас, потому что у него все в порядке с точки зрения скорости. Если диапазоны, как правило, не очень длинные и/или операция цикла не является дорогостоящей, возможно, это не стоит головной боли дополнительной бухгалтерии.

person emsr    schedule 07.09.2011