| 153 | } |
| 154 | |
| 155 | iterator upper_bound(const Key& key) { |
| 156 | // Binary search: find first element where key < element |
| 157 | iterator first = mData.begin(); |
| 158 | size_type count = mData.size(); |
| 159 | |
| 160 | while (count > 0) { |
| 161 | size_type step = count / 2; |
| 162 | iterator it = first + step; |
| 163 | if (!mLess(key, *it)) { |
| 164 | first = it + 1; |
| 165 | count -= step + 1; |
| 166 | } else { |
| 167 | count = step; |
| 168 | } |
| 169 | } |
| 170 | return first; |
| 171 | } |
| 172 | |
| 173 | const_iterator upper_bound(const Key& key) const { |
| 174 | // Binary search: find first element where key < element |