Есть ли способ найти количество ключей в многокарточном Inline?

multimap"s size сообщает количество значений, которые он содержит. Меня интересует количество ключей в нем. Например, учитывая multimap<int, double> foo Я хотел бы иметь возможность сделать это:

const auto keyCount = ???

Один из способов получить это - использовать forпетля на нуле инициализирована keyCount:

for(auto it = cbegin(foo); foo != cend(foo); it = foo.upper_bound(foo->first)) ++keyCount;

Это, однако, не позволяет мне выполнить операцию в строке. Так что я не могу инициализировать const auto keyCount,

Решением может быть лямбда или функция, которая оборачивает это forпетля, такая как:

template <typename Key, typename Value>
size_t getKeyCount(const multimap<Key, Value>& arg) {
    size_t result = 0U;

    for(auto it = cbegin(foo); foo != cend(foo); it = foo.upper_bound(foo->first)) ++result;
    return result;
}

Но я надеялся на то, что предусмотрено стандартом. Существует ли такая вещь?

Источник

3 ответа

Решение

1- й, multimap не содержит ключевой счет наивно. Таким образом, ваш вопрос заключается в том, как использовать что-то из библиотеки алгоритмов, чтобы найти счет. Вы поместили 2 ограничения, которые исключают все в библиотеке:

  1. Должен использоваться в строке, поэтому должен быть возвращен счетчик, а не итератор
  2. Должен выполнять как минимум так же хорошо, как upper_bound используется в лямбде, которая имеет временную сложность: O (log n)

1 оставляет нас с: count, count_if, for_each, а также большинство алгоритмов в числовой библиотеке

2 исключает рассмотрение всех из них, поскольку каждый из них имеет временную сложность: O (n)

Как таковой твой getKeyCount предпочтительнее любого другого варианта, который стандарт поставляет.

Просто комментарий о другом варианте, который может быть представлен: обслуживание keyCount всякий раз, когда что-то добавляется или удаляется из foo это может показаться работоспособным, но требует проверки перед каждой вставкой, если вставленный ключ существует, и проверки после каждого удаления, если удаленный ключ все еще существует. Помимо этого, существует также вопрос об опасности многопоточной неработоспособности и потери читабельности кода, когда неясно, что это keyCount должны поддерживаться вместе с foo, В конечном итоге это плохая идея, если подсчет ключей не берется значительно чаще, чем foo обновляется.

Источник

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

Источник

Нет, в стандарте нет встроенного для этого. Учтите, что ваша функция подсчета работает, потому что мультикарта внутренне отсортирована. Типичные реализации, такие как libstdC++, используют красно-черные деревья для внутреннего представления. Вам нужно пройтись по дереву, чтобы сосчитать все (уникальные) ключи. Это неизбежно.

Источник
Другие вопросы по тегам