CERT C++: CTR54-CPP

Do not subtract iterators that do not refer to the same container

Since R2022b

expand all in page

Description

Rule Definition

Do not subtract iterators that do not refer to the same container.¹

Polyspace Implementation

The rule checker checks for Subtraction or comparison between iterators from different containers.

Examples

expand all

Subtraction or Comparison between Iterators from Different Containers

Issue

This issue occurs when you subtract or compare iterators from different containers. For instance:

std::vector<int> v1,v2;
//...
std::less<std::vector<int>::iterator>()(v1.begin(), v2.end());

Polyspace^® reports a violation when you compare between iterators from v1 and v2.

Risk

If the two iterators are not from the same container, performing subtraction or comparison between these two iterators might result in a nonportable code, undefined behavior, or an unexpected result. For instance:

Subtracting iterators from different containers results in undefined behavior.
Comparing iterators from different containers leads to unexpected, implementation-dependent results.

Fix

Before subtracting or comparing iterators, verify that they belong to the same container.

Example — Compare or Subtract Pointers to Different Containers

#include <iostream>
#include <cassert>
#include <cstddef>
#include <cstdbool>
#include <vector>

template <typename T>
bool isWithinRange(const T *query, const T *begin, size_t span)
{
	//undefined behavior
	return 0 < (query - begin) && ((query - begin) < (std::ptrdiff_t)span); // Noncompliant 
}
template <typename T>
bool isOutofRange(const T *query, const T *begin, size_t span)
{
	std::less<const T*> less;
	//unspecified behavior
	return less(query, begin) && query > (begin + span); //Noncompliant
}


template <typename Iter>
bool inContainerRange(Iter query, Iter begin, Iter end)
{
       // unspecified behavior
	return query >= begin && query < end; //Noncompliant
}

void foo()
{
	double set[10];
	double *first = &set[0];
	double test_case;
	std::cout << std::boolalpha << isWithinRange(&test_case, first, 10);
	std::cout << std::boolalpha << isOutofRange(&test_case, first, 10);
}
void func(){
	std::vector<double> v1(10);
	std::vector<double> v2(1);
	std::cout << std::boolalpha << inContainerRange(v2.begin(), v1.begin(), v1.end());
}

In this example, Polyspace flags comparison and subtraction between iterators or pointers belonging to different containers. For instance:

In the function foo(), isWithinRange() is called in such a way that the iterators query and begin might not point to the same container. The operation query-begin might be undefined behavior. Polyspace reports a violation of this rule on the subtraction.
Similarly, the function isOutofRange() is called in such a way that the iterators query and begin might not point to the same container. The operation less(query, begin) might be unspecified behavior. Depending on your hardware architecture and software environment, this comparison might result in an unexpected result or undefined behavior. Polyspace reports a violation of this rule on the comparison.
In the function inContainerRange(), the iterators query, begin, and end might not belong to the same container. The operation query >= begin compares iterators from different containers when the function inContainerRange is improperly used, as shown in the function func(). Comparing iterators from different containers results in an unspecified behavior. Depending on your hardware architecture and software environment, this comparison might result in unexpected result or undefined behavior. Polyspace reports a violation of this rule on the comparison.

Correction —Do Not Compare or Subtract Iterators or Pointers to Different Containers

Avoid subtraction or comparison between pointers or iterators that might be from different containers. For instance, range checking is done in the function isWithinRange() by using the == operation, which has well-defined behavior even if the operands belong to different containers. While less efficient, this code avoids undefined or unexpected behavior.

#include <iostream>
#include <cassert>
#include <cstddef>
#include <cstdbool>
#include <vector>

template <typename T>
bool isWithinRange(const T *query, const T *begin, size_t span)
{
	auto *current = reinterpret_cast<const unsigned char *>(begin);
	auto *end = reinterpret_cast<const unsigned char *>(begin + span);
	auto *ptr = reinterpret_cast<const unsigned char *>(query);
	while(current!=end){
		if(current==ptr){
			return true;
		}
	}
	
	return false;
}
template <typename T>
bool isOutofRange(const T *query, const T *begin, size_t span)
{
	return !(isWithinRange(query, begin, span));
} 


void foo()
{
	double set[10];
	double *first = &set[0];
	double test_case;
	std::cout << std::boolalpha << isWithinRange(&test_case, first, 10);
	std::cout << std::boolalpha << isOutofRange(&test_case, first, 10);
}

Check Information

Group: Rule 04. Containers (CTR)

Version History

Introduced in R2022b

expand all

R2023a: Iterator subtractions involving outputs of stubbed function no longer ignored

Polyspace reports violations of this rule on iterator subtraction operations even if one of the operand is the output of a stubbed function. Polyspace no longer ignores iterator arithmetic operations when one of the operands is the output of the stubbed function.

¹ This software has been created by MathWorks incorporating portions of: the “SEI CERT-C Website,” © 2017 Carnegie Mellon University, the SEI CERT-C++ Web site © 2017 Carnegie Mellon University, ”SEI CERT C Coding Standard – Rules for Developing safe, Reliable and Secure systems – 2016 Edition,” © 2016 Carnegie Mellon University, and “SEI CERT C++ Coding Standard – Rules for Developing safe, Reliable and Secure systems in C++ – 2016 Edition” © 2016 Carnegie Mellon University, with special permission from its Software Engineering Institute.

ANY MATERIAL OF CARNEGIE MELLON UNIVERSITY AND/OR ITS SOFTWARE ENGINEERING INSTITUTE CONTAINED HEREIN IS FURNISHED ON AN "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.

This software and associated documentation has not been reviewed nor is it endorsed by Carnegie Mellon University or its Software Engineering Institute.