Determine index from pointers in C++

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Well I encountered this problem when I was practicing my DSA, so here I will share how its stored in my mind. In this article, we will look at how to compute the index using pointers returned by STL functions. It will be explained in such a way that even a 4th grader would get it.

Table of contents

Introduction
Problem statement
Reason for this behavior
How to solve this issue?
4.1 Solution 1 (Subtracting the starting iterator)
4.2 Solution 2 (Using std::distance())
Implementing the solutions
Time & Space Complexity

1. Introduction

So I think you have an idea on what a pointer and STL functions are. If not don’t worry, I gotcha!

Pointers have confusing definitions online, so let’s put it this way pointers are variables whose value is the address of another variable. It has various use cases but it’s enough for now. On the other hand Standard Template Library (STL) functions are instances of the classes present in it.

Since we have the basics covered, lets move on to the problem statement.

2. Problem Statement

The given problem statement is to compute the index using pointers returned by STL functions, lets understand it through an example.

Example:

In the following code we are finding the minimum element in a vector using std::min_element( start, end ). This is an STL function which returns a pointer, pointing to the minimum element in the vector.

// Program to find the minimum element in a vector
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{
    // Initialising a vector
    vector<int> v = {15, 51, 5, 12, 70, 102};

    // min_element(start,end); 
    //is an stl function which returns a pointer
    // pointing the minimum element in the vector
    // * Symbol is used to get the value pointed by the pointer
    cout << "Min element is:" << *min_element(v.begin(), v.end()) << endl;

    // Printig the index of the minimum element
    cout << "Index is: ";
    printf("%d", min_element(v.begin(), v.end()));

    return 0;
}

Output:

    Min element is:5
    Index is: 16717912

Woah! What happened! We are we getting a random value as the index. But why?

3. Reason for this behavior

We can observe that the value is different each time we run it. So, is it a random value?

The answer is NO! Reason for this behavior is very simple, remember the definition of pointers?

The number getting printed is the address of that memory location where that number is stored. It changes each time we run because the vector is getting initialized for each run. So how to solve this?

4. How to solve this issue?

To solve this issue and to obtain the index we have two ways those are:

To subtract the starting iterator and
To use an STL function

4.1 Solution 1 (Subtracting the starting iterator)

Lets take the same example as before and while printing the index lets subtract the starting iterator.

// Program to find the minimum element in a vector
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{
    // Initialising a vector
    vector<int> v = {15, 51, 5, 12, 70, 102};

    // min_element(start,end); is an stl function which returns a pointer
    // pointing the minimum element in the vector
    // * Symbol is used to get the value pointed by the pointer
    cout << "Min element is:" << *min_element(v.begin(), v.end()) << endl;

    // Printig the index of the minimum element 
    //by subtracting the staring iterator
    cout << "Index is: ";
    printf("%d", min_element(v.begin(), v.end()) - v.begin());

    return 0;
}

Output:

    Min element is:5
    Index is: 2

Vola! We got the correct index. But how did this happen. The main reason is because the ==vector space is continuous==.

Lets demonstrate it with code.

// Program to find the minimum element in a vector
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{
    // Initialising a vector
    vector<int> v = {15, 51, 5, 12, 70, 102};

    // min_element(start,end); is an stl function which 
    //returns a pointer
    // pointing the minimum element in the vector
    // * Symbol is used to get the value pointed by the pointer
    cout << "Min element is:" << *min_element(v.begin(), v.end()) << endl;

    // Printing the memory address of index 2
    cout << "Memory address of the minimum element is: ";
    printf("%d\n", min_element(v.begin(), v.end()));

    // Printing the memory address of index 0
    cout << "Memory address of the starting element is: ";
    printf("%d\n", v.begin());

    // Printig the index of the minimum element 
    //by subtracting the staring iterator
    cout << "Index is: ";
    printf("%d", min_element(v.begin(), v.end()) - v.begin());

    return 0;
}

Output:

   Min element is:5
   Memory address of the minimum element is: 15276120
   Memory address of the starting element is: 15276112
   Index is: 2

Calculation

    Value of desired location  = 15276120
    Value of starting iterator = 15276112
    Value after subtracting = 8
    Number of bytes occupied by int = 4
    	=> 8 / 4 = 2, The index of the minimum element.

This is how we are getting the index value after subtracting the starting iterator.

4.2 Solution 2 (Using std::distance())

std::distance() is an STL function and it is used when we have to find the number of elements between two iterators. It returns number of elements as integer.

// Program to find the minimum element in a vector
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;
int main()
{
    // Initialising a vector
    vector<int> v = {15, 51, 5, 12, 70, 102};

    // min_element(start,end); is an stl function 
    //which returns a pointer
    // pointing the minimum element in the vector
    // * Symbol is used to get the value pointed by the pointer
    cout << "Min element is:" << *min_element(v.begin(), v.end()) << endl;

    // Printig the index of the minimum element using distance()
    cout << "Index is: ";
    cout << distance(v.begin(), min_element(v.begin(), v.end()));

    return 0;
}

Output:

 Min element is:5
 Index is: 2

This function belong to the <iterator> header file.

5. Implementing the solutions

Lets apply the knowledge we gained to find an element in a vector.
Here we will be using std::find().

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    // Initializing the vector
    vector<int> v = {7, 50, 45, 106, 76, 10, 3, 67, 33, 15, 0};

    // value to be found
    int toFind = 10;

    // assigning the pointer with the return value
    auto it = find(v.begin(), v.end(), toFind);

    // If the element not present
    if (it == v.end())
    {
        cout << "Element is not present" << endl;
    }
    else
    {
        // Doing our calculation
        int idx = it - v.begin();

        // Using the distance function
        // int idx = distance(v.begin(), it);

        cout << "Index is: " << idx << endl;
    }

    return 0;
}

Output:

Index is: 5

6. Time & Space Complexity

In solution 1, we are using std::min_element() function which is a part of STL library.
Time Complexity: O(n) Where n is the size of vector.
Space Complexity: O(1) As no extra space is being consumed.
In solution 2 we are using both std::min_element(), std::distance() function which are a part of STL library.
Time Complexity: O(n) Where n is the size of vector.
Space Complexity: O(1) As no extra space is being consumed
Code under implementing solution uses std::find() function which is a part of STL library
Time Complexity: O(log(n)) Where n is the size of vector.
Space Complexity: O(1) As no extra space is being consumed

By the end of this article at OpenGenus, you must have complete idea on how to compute the index using pointers returned by STL functions.