16 #ifndef STXXL_PRIORITY_QUEUE_HEADER
17 #define STXXL_PRIORITY_QUEUE_HEADER
21 #include <stxxl/bits/deprecated.h>
22 #include <stxxl/bits/mng/typed_block.h>
23 #include <stxxl/bits/mng/block_alloc.h>
24 #include <stxxl/bits/mng/read_write_pool.h>
25 #include <stxxl/bits/mng/prefetch_pool.h>
26 #include <stxxl/bits/mng/write_pool.h>
27 #include <stxxl/bits/common/tmeta.h>
28 #include <stxxl/bits/algo/sort_base.h>
29 #include <stxxl/bits/parallel.h>
30 #include <stxxl/bits/common/is_sorted.h>
34 #if defined(STXXL_PARALLEL_MODE) && ((__GNUC__ * 10000 + __GNUC_MINOR__ * 100) < 40400)
35 #undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
36 #undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
37 #undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER
38 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 0
39 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 0
40 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 0
44 #ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
45 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 1
47 #ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
48 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 1
50 #ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER
51 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 1
54 #endif //STXXL_PARALLEL
56 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
57 #define STXXL_PQ_EXTERNAL_LOSER_TREE 0 // no loser tree for the external sequences
59 #define STXXL_PQ_EXTERNAL_LOSER_TREE 1
62 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
63 #define STXXL_PQ_INTERNAL_LOSER_TREE 0 // no loser tree for the internal sequences
65 #define STXXL_PQ_INTERNAL_LOSER_TREE 1
68 #include <stxxl/bits/containers/pq_helpers.h>
69 #include <stxxl/bits/containers/pq_mergers.h>
70 #include <stxxl/bits/containers/pq_ext_merger.h>
71 #include <stxxl/bits/containers/pq_losertree.h>
73 __STXXL_BEGIN_NAMESPACE
88 unsigned BufferSize1_ = 32,
90 unsigned IntKMAX_ = 64,
91 unsigned IntLevels_ = 4,
92 unsigned BlockSize_ = (2 * 1024 * 1024),
93 unsigned ExtKMAX_ = 64,
94 unsigned ExtLevels_ = 2,
95 class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY
97 struct priority_queue_config
99 typedef Tp_ value_type;
100 typedef Cmp_ comparator_type;
101 typedef AllocStr_ alloc_strategy_type;
104 delete_buffer_size = BufferSize1_,
107 num_int_groups = IntLevels_,
108 num_ext_groups = ExtLevels_,
109 BlockSize = BlockSize_,
111 element_size =
sizeof(Tp_)
115 __STXXL_END_NAMESPACE
119 template <
class BlockType_,
123 void swap(stxxl::priority_queue_local::ext_merger<BlockType_, Cmp_, Arity_, AllocStr_> & a,
124 stxxl::priority_queue_local::ext_merger<BlockType_, Cmp_, Arity_, AllocStr_> & b)
128 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
129 void swap(stxxl::priority_queue_local::loser_tree<ValTp_, Cmp_, KNKMAX> & a,
130 stxxl::priority_queue_local::loser_tree<ValTp_, Cmp_, KNKMAX> & b)
136 __STXXL_BEGIN_NAMESPACE
139 template <
class Config_>
143 typedef Config_ Config;
146 delete_buffer_size = Config::delete_buffer_size,
148 IntKMAX = Config::IntKMAX,
149 num_int_groups = Config::num_int_groups,
150 num_ext_groups = Config::num_ext_groups,
151 total_num_groups = Config::num_int_groups + Config::num_ext_groups,
152 BlockSize = Config::BlockSize,
153 ExtKMAX = Config::ExtKMAX
160 typedef typename Config::alloc_strategy_type alloc_strategy_type;
188 value_type group_buffers[total_num_groups][N + 1];
189 value_type * group_buffer_current_mins[total_num_groups];
192 value_type delete_buffer[delete_buffer_size + 1];
193 value_type * delete_buffer_current_min;
194 value_type * delete_buffer_end;
202 unsigned_type num_active_groups;
210 void refill_delete_buffer();
211 unsigned_type refill_group_buffer(unsigned_type k);
213 unsigned_type make_space_available(unsigned_type level);
214 void empty_insert_heap();
216 value_type get_supremum()
const {
return cmp.min_value(); }
217 unsigned_type current_delete_buffer_size()
const {
return delete_buffer_end - delete_buffer_current_min; }
218 unsigned_type current_group_buffer_size(unsigned_type i)
const {
return &(group_buffers[i][N]) - group_buffer_current_mins[i]; }
248 priority_queue(unsigned_type p_pool_mem, unsigned_type w_pool_mem);
255 for (unsigned_type i = 0; i < num_int_groups; ++i)
256 std::swap(int_mergers[i], obj.int_mergers[i]);
260 std::swap(ext_mergers, obj.ext_mergers);
261 for (unsigned_type i1 = 0; i1 < total_num_groups; ++i1)
262 for (unsigned_type i2 = 0; i2 < (N + 1); ++i2)
263 std::swap(group_buffers[i1][i2], obj.group_buffers[i1][i2]);
265 swap_1D_arrays(group_buffer_current_mins, obj.group_buffer_current_mins, total_num_groups);
266 swap_1D_arrays(delete_buffer, obj.delete_buffer, delete_buffer_size + 1);
267 std::swap(delete_buffer_current_min, obj.delete_buffer_current_min);
268 std::swap(delete_buffer_end, obj.delete_buffer_end);
269 std::swap(cmp, obj.cmp);
270 std::swap(insert_heap, obj.insert_heap);
271 std::swap(num_active_groups, obj.num_active_groups);
272 std::swap(size_, obj.size_);
296 const value_type &
top()
const;
310 void push(
const value_type & obj);
318 unsigned_type dynam_alloc_mem = 0;
321 for (
int i = 0; i < num_int_groups; ++i)
322 dynam_alloc_mem += int_mergers[i].
mem_cons();
324 for (
int i = 0; i < num_ext_groups; ++i)
325 dynam_alloc_mem += ext_mergers[i].
mem_cons();
328 return (
sizeof(*
this) +
335 template <
class Config_>
339 insert_heap.size() - 1 +
340 (delete_buffer_end - delete_buffer_current_min);
344 template <
class Config_>
347 assert(!insert_heap.empty());
350 if ( cmp(*delete_buffer_current_min, t))
353 return *delete_buffer_current_min;
356 template <
class Config_>
360 assert(!insert_heap.empty());
362 if ( cmp(*delete_buffer_current_min, insert_heap.top()))
366 assert(delete_buffer_current_min < delete_buffer_end);
367 ++delete_buffer_current_min;
368 if (delete_buffer_current_min == delete_buffer_end)
369 refill_delete_buffer();
373 template <
class Config_>
377 assert(int_mergers->not_sentinel(obj));
378 if (insert_heap.size() == N + 1)
382 assert(!insert_heap.empty());
384 insert_heap.push(obj);
390 template <
class Config_>
394 delete_buffer_end(delete_buffer + delete_buffer_size),
396 num_active_groups(0), size_(0)
398 STXXL_VERBOSE2(
"priority_queue::priority_queue(pool)");
403 template <
class Config_>
405 pool(new pool_type(p_pool_, w_pool_)),
407 delete_buffer_end(delete_buffer + delete_buffer_size),
409 num_active_groups(0), size_(0)
411 STXXL_VERBOSE2(
"priority_queue::priority_queue(p_pool, w_pool)");
415 template <
class Config_>
417 pool(new
pool_type(p_pool_mem / BlockSize, w_pool_mem / BlockSize)),
419 delete_buffer_end(delete_buffer + delete_buffer_size),
421 num_active_groups(0), size_(0)
423 STXXL_VERBOSE2(
"priority_queue::priority_queue(pool sizes)");
427 template <
class Config_>
430 assert(!cmp(cmp.min_value(), cmp.min_value()));
432 ext_mergers =
new ext_merger_type[num_ext_groups];
433 for (unsigned_type j = 0; j < num_ext_groups; ++j)
434 ext_mergers[j].set_pool(pool);
436 value_type sentinel = cmp.min_value();
437 insert_heap.push(sentinel);
438 delete_buffer[delete_buffer_size] = sentinel;
439 delete_buffer_current_min = delete_buffer_end;
440 for (unsigned_type i = 0; i < total_num_groups; i++)
442 group_buffers[i][N] = sentinel;
443 group_buffer_current_mins[i] = &(group_buffers[i][N]);
447 template <
class Config_>
450 STXXL_VERBOSE2(
"priority_queue::~priority_queue()");
454 delete[] ext_mergers;
460 template <
class Config_>
463 STXXL_VERBOSE2(
"priority_queue::refill_group_buffer(" << group <<
")");
466 unsigned_type length;
467 size_type group_size = (group < num_int_groups) ?
468 int_mergers[group].size() :
469 ext_mergers[group - num_int_groups].size();
470 unsigned_type left_elements = group_buffers[group] + N - group_buffer_current_mins[group];
471 if (group_size + left_elements >= size_type(N))
473 target = group_buffers[group];
474 length = N - left_elements;
478 target = group_buffers[group] + N - group_size - left_elements;
485 memmove(target, group_buffer_current_mins[group], left_elements *
sizeof(value_type));
486 group_buffer_current_mins[group] = target;
489 if (group < num_int_groups)
490 int_mergers[group].multi_merge(target + left_elements, length);
492 ext_mergers[group - num_int_groups].multi_merge(
493 target + left_elements,
494 target + left_elements + length);
499 #if STXXL_CHECK_ORDER_IN_SORTS
501 if (!stxxl::is_sorted(group_buffer_current_mins[group], group_buffers[group] + N, inv_cmp))
503 STXXL_VERBOSE2(
"length: " << length <<
" left_elements: " << left_elements);
504 for (value_type * v = group_buffer_current_mins[group] + 1; v < group_buffer_current_mins[group] + left_elements; ++v)
506 if (inv_cmp(*v, *(v - 1)))
508 STXXL_MSG(
"Error in buffer " << group <<
" at position " << (v - group_buffer_current_mins[group] - 1) <<
"/" << (v - group_buffer_current_mins[group]) <<
" " << *(v - 2) <<
" " << *(v - 1) <<
" " << *v <<
" " << *(v + 1));
515 return length + left_elements;
519 template <
class Config_>
522 STXXL_VERBOSE2(
"priority_queue::refill_delete_buffer()");
524 size_type total_group_size = 0;
526 for (
int i = num_active_groups - 1; i >= 0; i--)
528 if ((group_buffers[i] + N) - group_buffer_current_mins[i] < delete_buffer_size)
530 unsigned_type length = refill_group_buffer(i);
532 if (length == 0 &&
unsigned(i) == num_active_groups - 1)
535 total_group_size += length;
538 total_group_size += delete_buffer_size;
541 unsigned_type length;
542 if (total_group_size >= delete_buffer_size)
544 length = delete_buffer_size;
545 size_ -= size_type(delete_buffer_size);
549 length = total_group_size;
550 assert(size_ == size_type(length));
559 delete_buffer_current_min = delete_buffer_end - length;
560 STXXL_VERBOSE2(
"Active groups = " << num_active_groups);
561 switch (num_active_groups)
566 std::copy(group_buffer_current_mins[0], group_buffer_current_mins[0] + length, delete_buffer_current_min);
567 group_buffer_current_mins[0] += length;
570 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER
572 std::pair<value_type *, value_type *> seqs[2] =
574 std::make_pair(group_buffer_current_mins[0], group_buffers[0] + N),
575 std::make_pair(group_buffer_current_mins[1], group_buffers[1] + N)
577 parallel::multiway_merge_sentinel(seqs, seqs + 2, delete_buffer_current_min, inv_cmp, length);
579 group_buffer_current_mins[0] = seqs[0].first;
580 group_buffer_current_mins[1] = seqs[1].first;
583 priority_queue_local::merge_iterator(
584 group_buffer_current_mins[0],
585 group_buffer_current_mins[1], delete_buffer_current_min, length, cmp);
589 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER
591 std::pair<value_type *, value_type *> seqs[3] =
593 std::make_pair(group_buffer_current_mins[0], group_buffers[0] + N),
594 std::make_pair(group_buffer_current_mins[1], group_buffers[1] + N),
595 std::make_pair(group_buffer_current_mins[2], group_buffers[2] + N)
597 parallel::multiway_merge_sentinel(seqs, seqs + 3, delete_buffer_current_min, inv_cmp, length);
599 group_buffer_current_mins[0] = seqs[0].first;
600 group_buffer_current_mins[1] = seqs[1].first;
601 group_buffer_current_mins[2] = seqs[2].first;
604 priority_queue_local::merge3_iterator(
605 group_buffer_current_mins[0],
606 group_buffer_current_mins[1],
607 group_buffer_current_mins[2], delete_buffer_current_min, length, cmp);
611 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER
613 std::pair<value_type *, value_type *> seqs[4] =
615 std::make_pair(group_buffer_current_mins[0], group_buffers[0] + N),
616 std::make_pair(group_buffer_current_mins[1], group_buffers[1] + N),
617 std::make_pair(group_buffer_current_mins[2], group_buffers[2] + N),
618 std::make_pair(group_buffer_current_mins[3], group_buffers[3] + N)
620 parallel::multiway_merge_sentinel(seqs, seqs + 4, delete_buffer_current_min, inv_cmp, length);
622 group_buffer_current_mins[0] = seqs[0].first;
623 group_buffer_current_mins[1] = seqs[1].first;
624 group_buffer_current_mins[2] = seqs[2].first;
625 group_buffer_current_mins[3] = seqs[3].first;
628 priority_queue_local::merge4_iterator(
629 group_buffer_current_mins[0],
630 group_buffer_current_mins[1],
631 group_buffer_current_mins[2],
632 group_buffer_current_mins[3], delete_buffer_current_min, length, cmp);
636 STXXL_THROW(std::runtime_error,
"priority_queue<...>::refill_delete_buffer()",
637 "Overflow! The number of buffers on 2nd level in stxxl::priority_queue is currently limited to 4");
640 #if STXXL_CHECK_ORDER_IN_SORTS
641 if (!stxxl::is_sorted(delete_buffer_current_min, delete_buffer_end, inv_cmp))
643 for (value_type * v = delete_buffer_current_min + 1; v < delete_buffer_end; ++v)
645 if (inv_cmp(*v, *(v - 1)))
647 STXXL_MSG(
"Error at position " << (v - delete_buffer_current_min - 1) <<
"/" << (v - delete_buffer_current_min) <<
" " << *(v - 1) <<
" " << *v);
661 template <
class Config_>
664 STXXL_VERBOSE2(
"priority_queue::make_space_available(" << level <<
")");
665 unsigned_type finalLevel;
666 assert(level < total_num_groups);
667 assert(level <= num_active_groups);
669 if (level == num_active_groups)
672 const bool spaceIsAvailable_ =
673 (level < num_int_groups) ? int_mergers[level].is_space_available()
674 : ((level == total_num_groups - 1) ?
true : (ext_mergers[level - num_int_groups].is_space_available()));
676 if (spaceIsAvailable_)
682 finalLevel = make_space_available(level + 1);
684 if (level < num_int_groups - 1)
686 unsigned_type segmentSize = int_mergers[level].size();
687 value_type * newSegment =
new value_type[segmentSize + 1];
688 int_mergers[level].multi_merge(newSegment, segmentSize);
690 newSegment[segmentSize] = delete_buffer[delete_buffer_size];
694 int_mergers[level + 1].insert_segment(newSegment, segmentSize);
698 if (level == num_int_groups - 1)
700 const unsigned_type segmentSize = int_mergers[num_int_groups - 1].size();
701 STXXL_VERBOSE1(
"Inserting segment into first level external: " << level <<
" " << segmentSize);
702 ext_mergers[0].insert_segment(int_mergers[num_int_groups - 1], segmentSize);
706 const size_type segmentSize = ext_mergers[level - num_int_groups].size();
707 STXXL_VERBOSE1(
"Inserting segment into second level external: " << level <<
" " << segmentSize);
708 ext_mergers[level - num_int_groups + 1].insert_segment(ext_mergers[level - num_int_groups], segmentSize);
717 template <
class Config_>
720 STXXL_VERBOSE2(
"priority_queue::empty_insert_heap()");
721 assert(insert_heap.size() == (N + 1));
723 const value_type sup = get_supremum();
726 value_type * newSegment =
new value_type[N + 1];
727 value_type * newPos = newSegment;
731 value_type * SortTo = newSegment;
733 insert_heap.sort_to(SortTo);
735 SortTo = newSegment + N;
737 insert_heap.push(*SortTo);
739 assert(insert_heap.size() == 1);
745 const unsigned_type tempSize = N + delete_buffer_size;
746 value_type temp[tempSize + 1];
747 unsigned_type sz1 = current_delete_buffer_size();
748 unsigned_type sz2 = current_group_buffer_size(0);
749 value_type * pos = temp + tempSize - sz1 - sz2;
750 std::copy(delete_buffer_current_min, delete_buffer_current_min + sz1, pos);
751 std::copy(group_buffer_current_mins[0], group_buffer_current_mins[0] + sz2, pos + sz1);
752 temp[tempSize] = sup;
757 priority_queue_local::merge_iterator(pos, newPos, delete_buffer_current_min, sz1, cmp);
762 priority_queue_local::merge_iterator(pos, newPos, group_buffer_current_mins[0], sz2, cmp);
767 priority_queue_local::merge_iterator(pos, newPos, newSegment, N, cmp);
770 unsigned_type freeLevel = make_space_available(0);
771 assert(freeLevel == 0 || int_mergers[0].size() == 0);
772 int_mergers[0].insert_segment(newSegment, N);
778 for (int_type i = freeLevel; i >= 0; i--)
783 newSegment =
new value_type[current_group_buffer_size(i) + 1];
784 std::copy(group_buffer_current_mins[i], group_buffer_current_mins[i] + current_group_buffer_size(i) + 1, newSegment);
785 int_mergers[0].insert_segment(newSegment, current_group_buffer_size(i));
786 group_buffer_current_mins[i] = group_buffers[i] + N;
791 size_ += size_type(N);
794 if (delete_buffer_current_min == delete_buffer_end)
795 refill_delete_buffer();
798 namespace priority_queue_local
800 struct Parameters_for_priority_queue_not_found_Increase_IntM
802 enum { fits =
false };
803 typedef Parameters_for_priority_queue_not_found_Increase_IntM result;
808 enum { fits =
false };
809 typedef dummy result;
812 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_,
unsigned_type B_,
unsigned_type m_,
bool stop = false>
815 typedef find_B_m<E_, IntM_, MaxS_, B_, m_, stop> Self;
825 fits = c > 10 && ((k - m) * (m) * (m * B / (element_size * 4 * 1024))) >= MaxS_
826 && ((MaxS_ < ((k - m) * m / (2 * element_size)) * 1024) || m >= 128),
830 typedef typename find_B_m<element_size, IntM, MaxS_, B, m + step, fits || (m >= k - step)>::result candidate1;
831 typedef typename find_B_m<element_size, IntM, MaxS_, B / 2, 1, fits || candidate1::fits>::result candidate2;
836 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_,
bool stop>
837 struct find_B_m<E_, IntM_, MaxS_, 2048, 1, stop>
839 enum { fits =
false };
840 typedef Parameters_for_priority_queue_not_found_Increase_IntM result;
844 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_,
unsigned_type B_,
unsigned_type m_>
845 struct find_B_m<E_, IntM_, MaxS_, B_, m_, true>
847 enum { fits =
false };
848 typedef dummy result;
852 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_>
856 typedef typename find_B_m<E_, IntM_, MaxS_, (8 * 1024 * 1024), 1>::result result;
859 struct Parameters_not_found_Try_to_change_the_Tune_parameter
861 typedef Parameters_not_found_Try_to_change_the_Tune_parameter result;
865 template <
unsigned_type AI_,
unsigned_type X_,
unsigned_type CriticalSize_>
868 typedef compute_N<AI_, X_, CriticalSize_> Self;
875 typedef typename IF<(N >= CriticalSize_), Self,
typename compute_N<AI / 2, X, CriticalSize_>::result>::result result;
878 template <
unsigned_type X_,
unsigned_type CriticalSize_>
879 struct compute_N<1, X_, CriticalSize_>
881 typedef Parameters_not_found_Try_to_change_the_Tune_parameter result;
954 template <
class Tp_,
class Cmp_,
unsigned_type IntM_,
unsigned MaxS_,
unsigned Tune_ = 6>
959 typedef typename priority_queue_local::find_settings<sizeof(Tp_), IntM_, MaxS_>::result settings;
963 X = B * (settings::k - m) / settings::element_size,
967 typedef typename priority_queue_local::compute_N<(1 << Tune_), X, 4 * Buffer1Size>::result ComputeN;
972 AE = (m / 2 < 2) ? 2 : (m / 2)
976 EConsumption = X * settings::element_size + settings::B * AE + ((MaxS_ / X) / AE) * settings::B * 1024
992 __STXXL_END_NAMESPACE
997 template <
class Config_>
998 void swap(stxxl::priority_queue<Config_> & a,
999 stxxl::priority_queue<Config_> & b)
1005 #endif // !STXXL_PRIORITY_QUEUE_HEADER
Priority queue type generator.
Definition: priority_queue.h:955
_STXXL_DEPRECATED(priority_queue(prefetch_pool< block_type > &p_pool_, write_pool< block_type > &w_pool_))
Constructs external priority queue object.
Block containing elements of fixed length.
Definition: typed_block.h:223
const value_type & top() const
Returns "largest" element.
Definition: priority_queue.h:345
Implements dynamically resizable prefetching pool.
Definition: prefetch_pool.h:34
priority_queue(pool_type &pool_)
Constructs external priority queue object.
Definition: priority_queue.h:391
Inverts the order of a comparison functor by swapping its arguments.
Definition: pq_helpers.h:145
Implements dynamically resizable buffered writing pool.
Definition: write_pool.h:36
Implements dynamically resizable buffered writing and prefetched reading pool.
Definition: read_write_pool.h:28
Loser tree from Knuth, "Sorting and Searching", Section 5.4.1 !
Definition: pq_losertree.h:36
Similar to std::priority_queue, with the following differences:
Definition: pq_helpers.h:39
void push(const value_type &obj)
Inserts x into the priority_queue.
Definition: priority_queue.h:374
stxxl::uint64 size_type
An unsigned integral type (64 bit)
Definition: priority_queue.h:162
size_type size() const
Returns number of elements contained.
Definition: priority_queue.h:336
unsigned_type mem_cons() const
Returns number of bytes consumed by the priority_queue.
Definition: priority_queue.h:316
IF template metaprogramming statement.
Definition: tmeta.h:31
bool empty() const
Returns true if queue has no elements.
Definition: priority_queue.h:283
Config::value_type value_type
The type of object stored in the priority_queue.
Definition: priority_queue.h:157
External priority queue data structure.
Definition: priority_queue.h:140
void swap(priority_queue &obj)
swap this priority queue with another one Implementation correctness is questionable.
Definition: priority_queue.h:252
void pop()
Removes the element at the top.
Definition: priority_queue.h:357
External merger, based on the loser tree data structure. !
Definition: pq_ext_merger.h:127
Config::comparator_type comparator_type
Comparison object.
Definition: priority_queue.h:159