Bounds - binary search using pointer arithmetic
| 117 | |
| 118 | // Bounds - binary search using pointer arithmetic |
| 119 | iterator lower_bound(const Key& key) { |
| 120 | // Binary search: find first element where !(element < key) |
| 121 | iterator first = mData.begin(); |
| 122 | size_type count = mData.size(); |
| 123 | |
| 124 | while (count > 0) { |
| 125 | size_type step = count / 2; |
| 126 | iterator it = first + step; |
| 127 | if (mLess(*it, key)) { |
| 128 | first = it + 1; |
| 129 | count -= step + 1; |
| 130 | } else { |
| 131 | count = step; |
| 132 | } |
| 133 | } |
| 134 | return first; |
| 135 | } |
| 136 | |
| 137 | const_iterator lower_bound(const Key& key) const { |
| 138 | // Binary search: find first element where !(element < key) |