-
Notifications
You must be signed in to change notification settings - Fork 1.6k
Closed
Labels
enhancementSomething can be improvedSomething can be improvedfixedSomething works now, yay!Something works now, yay!good first issueGood for newcomersGood for newcomers
Description
The heap algorithms repeatedly say *(iter + idx) when iter[idx] would probably be easier to read. (Because of our iterator unwrapping logic, this usually shouldn't make a performance difference.) After searching the entire STL, the three affected functions that I see are:
Lines 2577 to 2590 in f9b1dcc
| template <class _RanIt, class _Ty, class _Pr> | |
| void _Push_heap_by_index(_RanIt _First, _Iter_diff_t<_RanIt> _Hole, _Iter_diff_t<_RanIt> _Top, _Ty&& _Val, _Pr _Pred) { | |
| // percolate _Hole to _Top or where _Val belongs, using _Pred | |
| using _Diff = _Iter_diff_t<_RanIt>; | |
| for (_Diff _Idx = (_Hole - 1) >> 1; // shift for codegen | |
| _Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val); // | |
| _Idx = (_Hole - 1) >> 1) { // shift for codegen | |
| // move _Hole up to parent | |
| *(_First + _Hole) = _STD move(*(_First + _Idx)); | |
| _Hole = _Idx; | |
| } | |
| *(_First + _Hole) = _STD move(_Val); // drop _Val into final hole | |
| } |
Lines 2612 to 2638 in f9b1dcc
| template <class _RanIt, class _Ty, class _Pr> | |
| void _Pop_heap_hole_by_index(_RanIt _First, _Iter_diff_t<_RanIt> _Hole, _Iter_diff_t<_RanIt> _Bottom, _Ty&& _Val, | |
| _Pr _Pred) { // percolate _Hole to _Bottom, then push _Val, using _Pred | |
| // precondition: _Bottom != 0 | |
| using _Diff = _Iter_diff_t<_RanIt>; | |
| const _Diff _Top = _Hole; | |
| _Diff _Idx = _Hole; | |
| // Check whether _Idx can have a child before calculating that child's index, since | |
| // calculating the child's index can trigger integer overflows | |
| const _Diff _Max_sequence_non_leaf = (_Bottom - 1) >> 1; // shift for codegen | |
| while (_Idx < _Max_sequence_non_leaf) { // move _Hole down to larger child | |
| _Idx = 2 * _Idx + 2; | |
| if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1)))) { | |
| --_Idx; | |
| } | |
| *(_First + _Hole) = _STD move(*(_First + _Idx)); | |
| _Hole = _Idx; | |
| } | |
| if (_Idx == _Max_sequence_non_leaf && _Bottom % 2 == 0) { // only child at bottom, move _Hole down to it | |
| *(_First + _Hole) = _STD move(*(_First + (_Bottom - 1))); | |
| _Hole = _Bottom - 1; | |
| } | |
| _Push_heap_by_index(_First, _Hole, _Top, _STD move(_Val), _Pred); | |
| } |
Lines 2672 to 2683 in f9b1dcc
| template <class _RanIt, class _Pr> | |
| void _Make_heap_unchecked(_RanIt _First, _RanIt _Last, _Pr _Pred) { | |
| // make nontrivial [_First, _Last) into a heap, using _Pred | |
| using _Diff = _Iter_diff_t<_RanIt>; | |
| _Diff _Bottom = _Last - _First; | |
| for (_Diff _Hole = _Bottom >> 1; 0 < _Hole;) { // shift for codegen | |
| // reheap top half, bottom to top | |
| --_Hole; | |
| _Iter_value_t<_RanIt> _Val = _STD move(*(_First + _Hole)); | |
| _Pop_heap_hole_by_index(_First, _Hole, _Bottom, _STD move(_Val), _Pred); | |
| } | |
| } |
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
enhancementSomething can be improvedSomething can be improvedfixedSomething works now, yay!Something works now, yay!good first issueGood for newcomersGood for newcomers