C++ : How to get element by index in List

In this article we will discuss how to get element by index in std::list.

std::list doesn’t have operator []

std::list does not have random access operator [] because std::list internally store elements in doubly linked list. So, to access an element at nth location we need to iterate one by one from beginning to nth element. So, its complexity will be O(n).

Suppose we have a list of strings i.e.

std::list<std::string> listOfStrs = { "First", "Sec",
								"Third", "Fourth",
								"Fifth", "Sixth"
								};

Now lets see how to access element at 3rd position from list using 2 different techniques.

Accessing nth element in std::list using std::advance

STL provides and algorithm std::advance() i.e.

template <class InputIterator, class Distance>
void advance (InputIterator& it, Distance n);

It advances the given iterator by n positions. Now lets access element at 3rd position using std::advance.

// Create iterator pointing to first element
std::list<std::string>::iterator it = listOfStrs.begin();

// Advance the iterator by 2 positions,
std::advance(it, 2);

As iterator it was already pointing to first element, therefore we need to advance it by 2 to point it to 3rd position.

Complexity of std::advance for std::list is O(n) because it needs to iterate one by one from beginning to nth position.

In C++11 another algorithm has been introduced i.e std::next()

Accessing nth element in std::list using std::next()

template <class ForwardIterator>
ForwardIterator next (ForwardIterator it,
       typename iterator_traits<ForwardIterator>::difference_type n = 1);

std::next() is introduced in C++11. It accepts an iterator and position to be advanced. It does not modify the passed iterator, but uses it to create a new iterator pointing to nth  -1 position from given iterator and returns it.

Lets see how to access element at 3rd position by std::next()

auto it1 = std::next(listOfStrs.begin(), 2);

Complete example is as follows,

#include <iostream>
#include <list>
#include <string>
#include <iterator>
#include <algorithm>

int main()
{
	std::list<std::string> listOfStrs =
	{ "First", "Sec", "Third", "Fourth", "Fifth", "Sixth" };

	/**** Finding nth element using std::advance() ******/

	// Find 3rd element from list

	// Create iterator pointing to first element
	std::list<std::string>::iterator it = listOfStrs.begin();

	// Advance the iterator by 2 positions,
	std::advance(it, 2);

	// Now iterator it points to 3rd element
	std::cout << "3rd element = " << *it << std::endl;

	/**** Finding nth element using std::next() ******/

	// Find 3rd element from list

	// It returns a new iterator pointing to n position after the
	// base iterator given as first argument
	auto it1 = std::next(listOfStrs.begin(), 2);

	std::cout << "3rd element = " << *it1 << std::endl;

	return 0;
}

Output:

3rd element = Third
3rd element = Third

As the above example uses std::next(), which is a c++11 feature. So, use following command to compile the example in linux i.e.

g++ –std=c++11 example.cpp

Complexity of std::next() & std::advance() for std::list()

As std::list is internally implemented as doubly linked list. So, in linked list to access the nth element we need to go one by one from start to nth element.

Therefore, for both the APIs i.e. std::next() & std::advance() complexity to fetch nth element will be O(n).

Thanks.