0

Нужно хранить в map только N отсортированных значений.

  • map.size() < N, тогда добавляем элементы.
  • map.size() > N, тогда добавляем новые элементы, удаляя лишние.

Вариант не добавлять новые элементы в map, если достигнут лимит N, не подходит. Идея заключается в том, чтобы всегда хранить актуальные данные, которые обновляются.

Может при каждой операции добавления пробегать итератором и удалять лишние элементы? Как-то так:

map // список с 3 элементами
map.insert(); // 4 элемента
// удаляем все элементы, кроме первых 3х

Но мне такая реализация кажется будет медленной.

Может у кого-то есть другое, более элегантное решение?

5
  • а причем тут QT? 5 июл 2019 в 17:32
  • А какие элементы лишние? Не очень понятно. Любые?
    – vt-egorov
    5 июл 2019 в 17:57
  • @vegorov в qmap значения хранятся в сортированном порядке. Когда ограничиваем размер, должны получить в итоге N отсортированных элементов. Например, при N = 3 и {3, 5, 7, 10} мы получим {3, 5, 7}.
    – trsv
    5 июл 2019 в 19:18
  • @vegorov в qmap значения хранятся в сортированном порядке. Когда ограничиваем размер, должны получить в итоге N отсортированных элементов. Например, при N = 3 и {3, 5, 7, 10} мы получим {3, 5, 7}.
    – trsv
    5 июл 2019 в 19:18
  • Почему? Почему не 3,7,10; не 3,5,10;, не 5,7,10. Критерий какой? Первые N нужны, оставшиеся лишние ?
    – vt-egorov
    5 июл 2019 в 19:57

2 ответа 2

2

Если я правильно понел, вы хотите оставлять первые size элементов. Тогда предложу вариант, например, такой:

template <size_t k, typename K, typename V,
     typename T = std::pair<K, V>>
std::map<K, V>&
inserter(std::map<K, V>& m, const T& p)
{
    m.insert(p);
    if (m.size() > k)
        m.erase(std::next(m.begin(), k), m.end());  
    return  m;
}

и пример использования:

int main() {    
    std::map<std::string, int> map;
    constexpr size_t size = 7;
    int k = 10;
    std::string s("B");
    while (k++ < 20) {
        s += char('A' + rand()% k);
        inserter<size>(map, { s, k });
    }
    // использовать map(имеет не более чем 7 элементов
    return 0;
}
1

Мне кажется вам подойдет QCache, которому можно установить максимальное число элементов, превышая которое ранние элементы перетираются.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.