52template <
class T,
class Cmp = std::greater<T> >
78 enum State { UNORDERED, BOTTOM_KNOWN, HEAP_SORTED };
79 using UnsortedIterator =
typename std::vector<T>::const_iterator;
81 explicit TopN(
size_t limit) :
TopN(limit, Cmp()) {}
82 TopN(
size_t limit,
const Cmp& cmp) : limit_(limit), cmp_(cmp) {}
83 size_t limit()
const {
return limit_; }
86 size_t size()
const {
return std::min(elements_.size(), limit_); }
87 bool empty()
const {
return size() == 0; }
91 void reserve(
size_t n) { elements_.reserve(std::min(n, limit_ + 1)); }
97 void push(
const T& v) { push(v,
nullptr); }
98 void push(
const T& v, T* dropped) { PushInternal(v, dropped); }
102 push(std::move(v),
nullptr);
104 void push(T&& v, T* dropped) {
105 PushInternal(std::move(v), dropped);
108 const T& peek_bottom();
111 std::vector<T> Take();
116 std::vector<T>* Extract();
121 std::vector<T>* ExtractUnsorted();
126 std::vector<T>* ExtractNondestructive()
const;
135 void ExtractNondestructive(std::vector<T>* output)
const;
141 std::vector<T>* ExtractUnsortedNondestructive()
const;
151 void ExtractUnsortedNondestructive(std::vector<T>* output)
const;
155 UnsortedIterator unsorted_begin()
const {
return elements_.begin(); }
156 UnsortedIterator unsorted_end()
const {
return elements_.begin() + size(); }
158 Cmp* comparator() {
return &cmp_; }
164 template <
typename U>
180 std::vector<T> elements_;
183 State state_ = UNORDERED;
187template <
class T,
class Cmp>
191 if (dropped) *dropped = std::forward<U>(v);
194 if (state_ != HEAP_SORTED) {
195 elements_.push_back(std::forward<U>(v));
196 if (state_ == UNORDERED || cmp_(elements_.back(), elements_.front())) {
205 swap(elements_.front(), elements_.back());
207 if (elements_.size() == limit_ + 1) {
209 std::make_heap(elements_.begin(), elements_.end(), cmp_);
210 if (dropped) *dropped = std::move(elements_.front());
211 std::pop_heap(elements_.begin(), elements_.end(), cmp_);
212 state_ = HEAP_SORTED;
216 if (cmp_(v, elements_.front())) {
220 elements_.back() = std::forward<U>(
228 std::pop_heap(elements_.begin(), elements_.end(), cmp_);
229 if (dropped) *dropped = std::move(elements_.back());
231 if (dropped) *dropped = std::forward<U>(v);
235template <
class T,
class Cmp>
238 if (state_ == UNORDERED) {
240 int min_candidate = 0;
241 for (
size_t i = 1;
i < elements_.size(); ++
i) {
242 if (cmp_(elements_[min_candidate], elements_[i])) {
248 if (min_candidate != 0) {
250 swap(elements_[0], elements_[min_candidate]);
252 state_ = BOTTOM_KNOWN;
254 return elements_.front();
256template <
class T,
class Cmp>
258 std::vector<T> out = std::move(elements_);
259 if (state_ != State::HEAP_SORTED) {
260 std::sort(out.begin(), out.end(), cmp_);
263 std::sort_heap(out.begin(), out.end(), cmp_);
269template <
class T,
class Cmp>
271 auto out =
new std::vector<T>;
272 out->swap(elements_);
273 if (state_ != HEAP_SORTED) {
274 std::sort(out->begin(), out->end(), cmp_);
277 std::sort_heap(out->begin(), out->end(), cmp_);
281template <
class T,
class Cmp>
283 auto out =
new std::vector<T>;
284 out->swap(elements_);
285 if (state_ == HEAP_SORTED) {
291template <
class T,
class Cmp>
293 auto out =
new std::vector<T>;
294 ExtractNondestructive(out);
297template <
class T,
class Cmp>
301 if (state_ != HEAP_SORTED) {
302 std::sort(output->begin(), output->end(), cmp_);
305 std::sort_heap(output->begin(), output->end(), cmp_);
308template <
class T,
class Cmp>
310 auto elements =
new std::vector<T>;
311 ExtractUnsortedNondestructive(elements);
314template <
class T,
class Cmp>
318 if (state_ == HEAP_SORTED) {
323template <
class T,
class Cmp>