Distance function in C++

In this article, we will learn about the Distance function in C++. This function is a part of the standard template library. It helps us to calculate the number of elements present between two iterator positions.

Syntax of the std:: distance function:

int n = distance(iterator1, iterator2);

PARAMETERS: The function takes two iterator values as parameters. The first one being the starting position and the second being the ending position.
RETURN VALUE: It returns the number of elements present between the two positions. Note that the number of elements = [start, end).

This function is an alias of the mathematical vectors which provides both magnitude and direction i.e if the starting position comes after the ending position, a result is a negative number. This is true for the random access iterators. But, when we use the bidirectional iterators, the function treats the arrangement of the elements as circular. The following example will make this more clear.

Example code for distance function in C++

APPROACH:

  1. We will be seeing the implementation of the distance function in c++ using two types of iterators. The first type is random access iterators and the second is bidirectional iterators.
  2. Firstly, we create a vector named values. The vector, in this case, has 7 elements.
  3. Then we create two iterators for the vector data type and assign the beginning position to iterator1 and ending position to iterator2. We can assign any positions to these iterators.
    vector<int> :: iterator it1;
     //starting iterator 
    vector<int> :: iterator it2; 
    //ending iterator 
    it1=values.begin(); 
    it2=values.end();
  4. Then we use the distance function to calculate the number of elements between the two positions, once for the forward direction and once for the backward direction.
    cout<<distance(it1,it2)<<endl; 
    //to see the difference of the magnitude
    cout<<distance(it2,it1)<<endl;
  5. We then repeat the above steps for the bidirectional type of iterator(i.e for list).

 

CODE:

#include <iostream>
#include<list>  //bidirectional iterator
#include<vector>//random access iterator
#include<iterator>
using namespace std;

int main() {
  vector<int> values;
  for(int i=0;i<7;i++){    //insert the values
      values.push_back(i*2);
  }
  vector<int> :: iterator it1; //starting iterator
  vector<int> :: iterator it2; //ending iterator
  it1=values.begin();
  it2=values.end();
  cout<<distance(it1,it2)<<endl; //to see the difference
  cout<<distance(it2,it1)<<endl; //of the magnitude
  
  
  list<int> value;
  for(int i=0;i<7;i++){        //insert values
      value.push_back(i*2);
  }
  list<int> :: iterator it3; //starting iterator
  list<int> :: iterator it4; //ending iterator
  it3=value.begin();
  it4=value.begin();  
//note that the bidirectional iterators can only be incremented using ++ 
// it3=it4+5 is invalid for bidirectional iterators
  it4++;
  it4++;  
  it4++; 
 
  cout<<distance(it3,it4)<<endl; //circular arrangement is considered
  cout<<distance(it4,it3)<<endl;  //also considers value.end() as an element
  return 0;
  
  
  
}

OUTPUT

7
-7
3
5

TIME COMPLEXITY: O(n)

As you can see, in the case of random access iterator, it is considering the direction. Our starting position is values.begin() and ending position is values.end() which points to one space ahead of the last element. So, in total, we have 7 elements between them. But, when we reverse the positions in the function we get a -7 because of the opposite direction.

In the case of a bidirectional iterator, we go around the elements in a circular manner. So, when we use distance(it3,it4) we are moving in the forward direction and we have 3 elements between the two positions. But, when we reverse the parameters i.e we use distance(it4,it3) we still move forward, and when value.end() is encountered we start again from the beginning and hence get 4 elements as the output.

 

READ MORE:

Iterator Invalidation in C++

Leave a Reply