lower_bound returns minimum position in sorted vector element can inserted, without losing sorted order property. upper_bound, maximum. in mind, there edge case which:
auto lower = std::lower_bound(vec.begin(), vec.end(), x); auto upper = std::upper_bound(lower, vec.end(), y); // using lower, opposed vec.begin() (auto = lower; != upper; it++) { /* work */ } would not perform expected? is, not visit every element in range [x, y), x < y?
i wish know if optimization (albeit small) viable.
tl;dr - yes, it's fine.
for original question (where both upper , lower bound searching same key x), it's built-in std::equal_range.
note paragraph
the returned range defined 2 iterators, 1 pointing first element not less value , pointing first element greater value. the first iterator may alternatively obtained
std::lower_bound(), second -std::upper_bound().
for edited question - lower_bound(x) .. upper_bound(y) x <= y, preconditions change slightly.
the original version required input range partitioned respect comparison x. now, require partitioned wrt comparison both x , y. still more satisfied total ordering though, sorted vector work assuming < sane (ie, provides required strict weak ordering).
Comments
Post a Comment