To get a trial key
fill out the form below
Team License (a basic version)
Enterprise License (an extended version)
* By clicking this button you agree to our Privacy Policy statement

Request our prices
New License
License Renewal
--Select currency--
USD
EUR
GBP
RUB
* By clicking this button you agree to our Privacy Policy statement

Free PVS-Studio license for Microsoft MVP specialists
* By clicking this button you agree to our Privacy Policy statement

To get the licence for your open-source project, please fill out this form
* By clicking this button you agree to our Privacy Policy statement

I am interested to try it on the platforms:
* By clicking this button you agree to our Privacy Policy statement

Message submitted.

Your message has been sent. We will email you at


If you haven't received our response, please do the following:
check your Spam/Junk folder and click the "Not Spam" button for our message.
This way, you won't miss messages from our team in the future.

>
>
>
Iterators

Iterators

Oct 20 2021

Iterators are objects that implement an interface that accesses container elements. Their main purpose is to provide an opportunity to work with various containers in a common manner. This allows you to use the same functions and algorithms. With the use of iterators, you can iterate over objects inside any container. Iterators may be useful when the containers cannot provide quick access to an arbitrary element.

Iterator is a lightweight object that stores only a pointer to the type of container objects. An iterator is defined by 5 template parameters, two of which are mandatory — the iterator category and the value type. You can obtain the value type by dereferencing the iterator. Such operations, as prefix and postfix increments (++), comparison (==, !=), and dereference (*), are overloaded for each iterator category. After executing the ++ operator, the iterator points to the next element in the collection, if it exists. The == and != operators return true or false, depending on whether the iterators point to the same object. In order to obtain the object, you can also use the dereference operation. Just like pointers, iterators have operations of dereference (*,->), increment (++) and comparison (==, !=).

Each container type has its own iterator. This is due to the peculiarities of the location of elements in memory and access to them. All iterators can be divided into the following categories:

  • Input iterators (InputIterator);
  • Forward iterators (ForwardIterator);
  • Bidirectional iterators (BidirectionalIterator);
  • Random access iterators (RandomAccessIterator);
  • Continuous iterators (ContiguousIterator, since C++17);
  • Output iterators (OutputIterator).

A category is defined by operations that can be performed on it. Each of the first five categories includes the previous one. Thus, you can perform all operations of bidirectional, forward and input iterators on random access iterators. The table below shows all these categories. The table uses the following notation:

  • it, it1, it2 — iterators;
  • a — a field or base type method that the iterator points to;
  • n — a number of elements or an index.
Iterators/image1.png

A cell with ± means that the operation can only be executed if the iterator is not constant.

Depending on the iterator category, it can be used in different standard algorithms. For example, the algorithm for counting algorithm numbers (std::count) can be applied to all types of iterators, except for output iterators. The sorting algorithm (std::sort) can be applied only to random access and continuous iterators.

The following example demonstrates how you can use iterators to calculate the sum in different containers:

#include <vector>
#include <deque>
#include <forward_list>
#include <set>
#include <string>
#include <iostream>

template <typename InputIt, typename T>
constexpr T sum(InputIt first, InputIt last, T init)
{
  while (first != last)
  {
    init = std::move(init) + *first;
    ++first;
  }

  return init;
}

int main()
{
  std::forward_list<int> flist { 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 };
  std::deque<int>        deque { 1, 1, 2, 3, 5, 8, 13 };
  std::vector<float>    vector { 0.3, 0.5 ,0.7 ,0.9 ,1.1 };
  std::set<std::string>    set { "One", "Two", "Three", "Four" };

  auto  flist_sum = sum(flist.begin(), flist.end(), 0);
  auto  deque_sum = sum(deque.begin(),  deque.end(), 0);
  auto vector_sum = sum(vector.begin(), vector.end(), 0.0f);
  auto    set_sum = sum(set.begin(), set.end(), std::string {});

  std::cout << " flist_sum = " << flist_sum  << "\n";
  std::cout << " deque_sum = " << deque_sum  << "\n";
  std::cout << "vector_sum = " << vector_sum << "\n";
  std::cout << "   set_sum = " << set_sum    << std::endl;


  // flist_sum = 7
  // deque_sum = 33
  // vector_sum = 3.5
  // set_sum = FourOneThreeTwo

  return 0;
}

To calculate the sum, use the sum template function that accepts two iterators and an initial value. The sum function uses such operations on iterators as comparison (!=), dereference for reading (*) and prefix increment (++). These operations can be executed for all categories starting with InputIterator and except for OutputIterator. InputIterator is the lowest of the five, so the function can work with all five iterator categories. If you want to determine the type of returned value, use init argument function.

If you want to obtain an iterator for beginning and the end of the sequence of elements, any container has the begin and end methods. The forward_list container uses forward iterators.The deque and set containers use bidirectional iterators. The vector container uses random access iterators. Calling functions for different containers results in instantiating a template with the corresponding iterator type and stored value type.

The C++ language prohibits assigning the value of one iterator type to another iterator type. Except for a constant iterator that can take the value of the identical (but not constant) iterator.

For more convenient work with iterators, you can use the following operations:

  • std::distance returns the distance (number of transitions) between two iterators;
  • std::advance modifies the passed iterator by shifting it forward or backward by n positions. Any iterator type can be shifted by a positive number. A shift by a negative number is available for iterators starting from the BidirectionalIterator category;
  • std::prev returns the nth previous iterator;
  • std::next returns the nth next iterator.

If you want to change the iterator's behavior or add extra functionality, use the adapter iterators. For example, the reverse_iterator adapter allows you to traverse the container in the opposite direction. The back_insert_iterator adapter allows you to insert the elements in the end of a container.

Iterators often simplify programming. However, if you misuse iterators, the compilers can't always track it. This may lead to undefined behavior. For example, you can compare iterators from different containers (V662) or dereference an invalid iterator (V783). PVS-Studio detects these and some other patterns of errors related to iterators via diagnostics V803, V789 and V738.

Links:

Popular related articles
The Ultimate Question of Programming, Refactoring, and Everything

Date: Apr 14 2016

Author: Andrey Karpov

Yes, you've guessed correctly - the answer is "42". In this article you will find 42 recommendations about coding in C++ that can help a programmer avoid a lot of errors, save time and effort. The au…
How PVS-Studio Proved to Be More Attentive Than Three and a Half Programmers

Date: Oct 22 2018

Author: Andrey Karpov

Just like other static analyzers, PVS-Studio often produces false positives. What you are about to read is a short story where I'll tell you how PVS-Studio proved, just one more time, to be more atte…
Technologies used in the PVS-Studio code analyzer for finding bugs and potential vulnerabilities

Date: Nov 21 2018

Author: Andrey Karpov

A brief description of technologies used in the PVS-Studio tool, which let us effectively detect a large number of error patterns and potential vulnerabilities. The article describes the implementati…
Free PVS-Studio for those who develops open source projects

Date: Dec 22 2018

Author: Andrey Karpov

On the New 2019 year's eve, a PVS-Studio team decided to make a nice gift for all contributors of open-source projects hosted on GitHub, GitLab or Bitbucket. They are given free usage of PVS-Studio s…
Appreciate Static Code Analysis!

Date: Oct 16 2017

Author: Andrey Karpov

I am really astonished by the capabilities of static code analysis even though I am one of the developers of PVS-Studio analyzer myself. The tool surprised me the other day as it turned out to be sma…
PVS-Studio for Java

Date: Jan 17 2019

Author: Andrey Karpov

In the seventh version of the PVS-Studio static analyzer, we added support of the Java language. It's time for a brief story of how we've started making support of the Java language, how far we've co…
The way static analyzers fight against false positives, and why they do it

Date: Mar 20 2017

Author: Andrey Karpov

In my previous article I wrote that I don't like the approach of evaluating the efficiency of static analyzers with the help of synthetic tests. In that article, I give the example of a code fragment…
The Last Line Effect

Date: May 31 2014

Author: Andrey Karpov

I have studied many errors caused by the use of the Copy-Paste method, and can assure you that programmers most often tend to make mistakes in the last fragment of a homogeneous code block. I have ne…
PVS-Studio ROI

Date: Jan 30 2019

Author: Andrey Karpov

Occasionally, we're asked a question, what monetary value the company will receive from using PVS-Studio. We decided to draw up a response in the form of an article and provide tables, which will sho…
Characteristics of PVS-Studio Analyzer by the Example of EFL Core Libraries, 10-15% of False Positives

Date: Jul 31 2017

Author: Andrey Karpov

After I wrote quite a big article about the analysis of the Tizen OS code, I received a large number of questions concerning the percentage of false positives and the density of errors (how many erro…

Comments (0)

Next comments
This website uses cookies and other technology to provide you a more personalized experience. By continuing the view of our web-pages you accept the terms of using these files. If you don't want your personal data to be processed, please, leave this site.
Learn More →
Accept