An iterator is a variable that points to an element of a data structure. The iterator begin points to the first element of a data structure, and the iterator end points to the position after the last element. Let’s look at the example below Where vector v contain these elements:
[4, 3, 2, 5, 6, 8, 9]
v.begin() = “4”
v.end() = “]”
begin() points to element in the data structure while end points outside the data structure.
A range is a sequence of consecutive elements in a data structure. The usual way to specify a range is to give iterators to its first element and the position after its last element. In particular, the iterators begin() and end() define a range that contains all elements in a data structure.
The C++ standard library functions typically operate with ranges. For example, the following code first sorts a vector, then reverses the order of its elements and finally shuffles its elements.
sort(v.begin(),v.end(); reverse(v.begin(),v.end()) random_shuffle(v.begin(),v.end());
The element to which iterator is pointing at can be accesses through * operator. For example, the below code prints the first element of a vector:
cout << *v.begin() << “\n”;
Let’s consider an example using lower_bound and upper_bound to check ranges usage. lower_bound gives an iterator to the first element in a sorted range whose value is at least x and upper_bound gives an iterator to the first element whose value is larger than x:
vector<int> v = {1,2,3,4,5,6,7,8,9};
auto lb = lower_bound(v.begin(),v.end(),4);
auto ub = upper_bound(v.begin(),v.end(),5);
cout << *lb << " " << *ub << "\n"; //4,6
Above functions only work correctly when the given range is sorted. It use binary search and find the requested element in logarithmic time. If there is no such element, the functions return an iterator to the element after the last element in the range.