First, I note that generally when C++ programmers refer to std::lower_bound(), we refer to the free function template algorithm. In contrast, the std::map<> template class has a member function with the same name, that you might denote as std::map<>::lower_bound() to avoid confusion between the two.

The same holds for std::upper_bound().

Both the free algorithms and the member functions return an iterator; an object that represents a reference or a pointer to an element in a container. We use the term pointer for something else already in the language, and so we chose the term iterator for something that represents an abstractness over that. A pointer is a special case of an iterator, and so is any object that behaves like a pointer in the sense that it can be incremented and dereferenced.

For example:

int n = 1;
int* p = &n;  // a pointer is an iterator
*p = 2;  // dereference
++p;  // increment
my_iterator mp = &n;  // also an iterator
*mp = 3;
++mp;

Because my_iterator supports these two operations, and they mean what a pointer means with these operations, my_iterator is a conforming iterator. Specifically, it is a conforming input iterator. Were it to support other pointer operations as well, like decrement, it would be of a stronger iterator category, like a bidirectional iterator. So there is an iterator category hierarchy, where the higher you go in the heptarchy, the more powerful the iterator is and the more demanding its implementation is.

When a class wishes to conform as an iterator, it must fulfill iterator requirements. Among them are the operations I mentioned above, along with their meanings. Also among them is the operations' complexities. In the case of increment, it must be a constant-time operation.

The reason why iterators must guarantee complexities for their operations is because standard algorithms (and container member functions among them) provide these guarantees, and they generally work with iterators. So the guarantees that standard algorithms provide rely on the guarantees that iterators provide.

For example, the std::find() algorithm is a linear search algorithm. It can work on many kinds of containers, including the obvious array-like and the not-so-obvious tree-like. This algorithm requires a mere input iterator, the simplest iterator category, for its parameters. The algorithm then guarantees a linear complexity. Of course, this assumes that the iterator's increment operation is constant time; were it not the case, there is no way the algorithm could guarantee linear operation.