49template <
class T,
class Cmp = std::greater<T> >
75 enum State { UNORDERED, BOTTOM_KNOWN, HEAP_SORTED };
76 using UnsortedIterator =
typename std::vector<T>::const_iterator;
78 explicit TopN(
size_t limit) :
TopN(limit, Cmp()) {}
79 TopN(
size_t limit,
const Cmp& cmp) : limit_(limit), cmp_(cmp) {}
80 size_t limit()
const {
return limit_; }
83 size_t size()
const {
return std::min(elements_.size(), limit_); }
84 bool empty()
const {
return size() == 0; }
88 void reserve(
size_t n) { elements_.reserve(std::min(n, limit_ + 1)); }
94 void push(
const T& v) { push(v,
nullptr); }
95 void push(
const T& v, T* dropped) { PushInternal(v, dropped); }
99 push(std::move(v),
nullptr);
101 void push(T&& v, T* dropped) {
102 PushInternal(std::move(v), dropped);
105 const T& peek_bottom();
108 std::vector<T> Take();
113 std::vector<T>* Extract();
118 std::vector<T>* ExtractUnsorted();
123 std::vector<T>* ExtractNondestructive()
const;
132 void ExtractNondestructive(std::vector<T>* output)
const;
138 std::vector<T>* ExtractUnsortedNondestructive()
const;
148 void ExtractUnsortedNondestructive(std::vector<T>* output)
const;
152 UnsortedIterator unsorted_begin()
const {
return elements_.begin(); }
153 UnsortedIterator unsorted_end()
const {
return elements_.begin() + size(); }
155 Cmp* comparator() {
return &cmp_; }
161 template <
typename U>
177 std::vector<T> elements_;
180 State state_ = UNORDERED;
184template <
class T,
class Cmp>
188 if (dropped) *dropped = std::forward<U>(v);
191 if (state_ != HEAP_SORTED) {
192 elements_.push_back(std::forward<U>(v));
193 if (state_ == UNORDERED || cmp_(elements_.back(), elements_.front())) {
202 swap(elements_.front(), elements_.back());
204 if (elements_.size() == limit_ + 1) {
206 std::make_heap(elements_.begin(), elements_.end(), cmp_);
207 if (dropped) *dropped = std::move(elements_.front());
208 std::pop_heap(elements_.begin(), elements_.end(), cmp_);
209 state_ = HEAP_SORTED;
213 if (cmp_(v, elements_.front())) {
217 elements_.back() = std::forward<U>(
225 std::pop_heap(elements_.begin(), elements_.end(), cmp_);
226 if (dropped) *dropped = std::move(elements_.back());
228 if (dropped) *dropped = std::forward<U>(v);
232template <
class T,
class Cmp>
235 if (state_ == UNORDERED) {
237 int min_candidate = 0;
238 for (
size_t i = 1;
i < elements_.size(); ++
i) {
239 if (cmp_(elements_[min_candidate], elements_[i])) {
245 if (min_candidate != 0) {
247 swap(elements_[0], elements_[min_candidate]);
249 state_ = BOTTOM_KNOWN;
251 return elements_.front();
253template <
class T,
class Cmp>
255 std::vector<T> out = std::move(elements_);
256 if (state_ != State::HEAP_SORTED) {
257 std::sort(out.begin(), out.end(), cmp_);
260 std::sort_heap(out.begin(), out.end(), cmp_);
266template <
class T,
class Cmp>
268 auto out =
new std::vector<T>;
269 out->swap(elements_);
270 if (state_ != HEAP_SORTED) {
271 std::sort(out->begin(), out->end(), cmp_);
274 std::sort_heap(out->begin(), out->end(), cmp_);
278template <
class T,
class Cmp>
280 auto out =
new std::vector<T>;
281 out->swap(elements_);
282 if (state_ == HEAP_SORTED) {
288template <
class T,
class Cmp>
290 auto out =
new std::vector<T>;
291 ExtractNondestructive(out);
294template <
class T,
class Cmp>
298 if (state_ != HEAP_SORTED) {
299 std::sort(output->begin(), output->end(), cmp_);
302 std::sort_heap(output->begin(), output->end(), cmp_);
305template <
class T,
class Cmp>
307 auto elements =
new std::vector<T>;
308 ExtractUnsortedNondestructive(elements);
311template <
class T,
class Cmp>
315 if (state_ == HEAP_SORTED) {
320template <
class T,
class Cmp>