jameshelou jameshelou - 2 months ago 3x
C++ Question

How does subtracting X.begin() return the index of an iterator?

Having trouble understanding the below code:

int data[5] = { 1, 5, 2, 4, 3 };
vector<int> X(data, data+5);
int v1 = *max_element(X.begin(), X.end()); // Returns value of max element in vector
int i1 = min_element(X.begin(), X.end()) – X.begin(); // Returns index of min element in vector

Not really sure how subtracting the iterator returned by X.begin returns the index of the max/min element?


std::vector<T>::iterator satisfies the RandomAccessIterator concept, which means that it has an operator- that allows you to subtract two iterators and obtain a std::vector<T>::iterator::difference_type that indicates the distance between the two iterators.

An under-the-hood implementation for std::vector<T>::iterator could in fact be made using pointers as iterators, in which case the subtraction operator would just be doing pointer arithmetic. There's no requirement for the iterator to be implemented using pointers, but it's a potential design.

Other containers' iterators may not have this capability. For instance, std::set<T>::iterator only satisfies the BidirectionalIterator concept, which specifies a less-rich set of functionality than the RandomAccessIterator concept.