Хм. Предложение: Делаешь функтор-обертку над интом. В конструкторе - зануляешь, в operator() возвращаешь rvalue на инт. Тип так: class my_int { int val = 0; public: my_int() = default; ~my_int() = default; int& operator()() { return val; }; } Дальше делаешь template<typename T> class mycounter : public std::vector<std::pair<<T, my_int>> { public: void sort() { std::sort(begin(), end(), [](const value_type& left, const value_type& right) { return left.second() < right.second(); }); }; } На этом всё. Из минусов, перед перебором надо вызывать метод sort. В коде могут быть ошибки, набирал с телефона, но думаю идея понятна?
Спасибо за ответ, идея понятная. Вот только мне нужно что бы объекты не дублировались внутри контейнера(то есть быстрый поиск по ключу и уже изменение его значения).
А, тем более херню предложил...
Можно попробовать положить все в один вектор, и сортировать в зависимости от потребностей. И держать контейнер отсортированным так, чтобы было быстрее делать те операции, которые чаще нужны. Если, например, заранее известно, что сначала в контейнер делается много insert, а после этого уже только одни mostCommon, то можно после завершения добавления элементов переключить сортировку, и больше не трогать. https://godbolt.org/z/PWf5x9cd4
Спасибо, очень красивый код. Почему по умолчанию не использовать map вместо vector?
Если вектора хватает, стараюсь им пользоваться. Оно компактно в памяти лежит, а не разбросано по всей куче.
экономный вариант без лишнего копирования ключей может выглядеть так: #include <QDebug> #include <QList> #include <QString> #include <map> #include <span> #include <vector> class Histogram { using CounterMap = std::map<QString, int>; CounterMap m_counter; mutable bool m_invalidated = false; mutable std::vector<CounterMap::const_iterator> m_order; public: void append(QString key) { m_counter[std::move(key)]++; m_invalidated = true; } std::span<CounterMap::const_iterator> top(size_t n = 0) const { if (m_invalidated) { reorder(); } if (!n) { n = m_counter.size(); } return std::span(m_order.begin(), n); } private: void reorder() const { m_order.clear(); m_order.reserve(m_counter.size()); for (auto&& it = m_counter.begin(); it != m_counter.end(); ++it) { m_order.emplace_back(it); } std::sort(m_order.begin(), m_order.end(), [](auto&& a, auto&& b) { return b->second < a->second; }); m_invalidated = false; } }; int main(int, char*[]) { Histogram historam; QList<QString> keys { "one", "two", "three", "one", "three", "one" }; for (auto&& key : keys) { historam.append(key); } auto&& top = historam.top(); for (auto&& e : top) { qDebug() << e->first << e->second; } }
О спасибо, и про гистограммы помните) вопрос по коду, что это: decltype(m_order)().swap(m_order); почему просто не m_order.clear();?
это старый трюк освободит память вектора, clear может оставить ее. но здесь это не принципиально. сейчас после clear можно вызвать shink_to_fit - это будет эквивалентный этому трюку код. давайте я уберу, чтобы не смущало
ну зачем же убирать, буду учиться, может встречу в коде и буду знать что оно делает) а так спасибо)
а еще вопрос, у меня Qt5.15.2 MinGW64, в qmake пишу CONFIG += c++latest # c++2a а std::span все равно не находит. Что делаю не так?
значит g++ в mingw64 старичек и не понимает span
Немного оффтоп: я почитал про span и немного недогнал, а чем он лучше, например, вектора ссылок?
вектора ссылок не бывает
Ладно, справедливо. Заменим на вектор указателей, производительность та же, просто юзать неудобно)
Обсуждают сегодня