blob: 951b36962d7f52dad200d9cfa7db49476b37d5cb (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#pragma once
#include "compact_vector.h"
namespace NYT {
////////////////////////////////////////////////////////////////////////////////
//! A heap structure optimized for storing elements inline
//! and with little memory overhead. See TCompactVector.
/*!
* When inline, uses linear search for selecting minimum
* instead of storing heap.
*/
template <class T, size_t N, class C = std::less<T>>
class TCompactHeap
{
public:
static_assert(N <= 8, "TCompactHeap is not optimal for large N");
explicit TCompactHeap(C comparator = C()) noexcept;
using value_type = T;
using const_reference = const T&;
using const_iterator = const T*;
using difference_type = ptrdiff_t;
using size_type = size_t;
void push(T value);
void pop();
const_reference get_min() const;
value_type extract_min();
const_iterator begin() const;
const_iterator end() const;
void swap(TCompactHeap<T, N, C>& other);
size_t size() const;
size_t capacity() const;
size_t max_size() const;
bool empty() const;
void shrink_to_small();
private:
TCompactVector<T, N> Heap_;
class TReverseComparator
{
public:
explicit TReverseComparator(C underlying);
bool operator()(const T& lhs, const T& rhs) const;
private:
C Underlying_;
};
TReverseComparator Comparator_;
bool IsInline() const;
};
////////////////////////////////////////////////////////////////////////////////
} // namespace NYT
#define COMPACT_HEAP_INL_H_
#include "compact_heap-inl.h"
#undef COMPACT_HEAP_INL_H_
|
