Page tree

Skip to end of metadata
Go to start of metadata

Insure++ can detect several STL usage errors on Unix systems:

Derefencing an Unbound Iterator

This problem occurs when there is an attempt to dereference an unbound iterator–an iterator that has not been tasked as an iterator over any container.

Problem

When this program is compiled with g++, the resulting executable produces a SEG_FAULT, but there is no indication of what went wrong.

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI::iterator iter;
	int x = *iter; // unbound iterator.
	return 0;
}

Diagnosis at Runtime

$ insure g++ -g -Zstl unbound_iterator.cc -o unbound_iterator
[unbound_iterator.cc:9] **STL_ERROR**
>>	 int x = *iter;			 // unbound iterator.
Dereferencing unbound iterator.
	Iterator at: 0xbffff6c0 (stack)
				iter, declared at unbound_iterator.cc, 8
Stack trace where the error occurred:
		iterator<>::operator*() (interface)
				main() unbound_iterator.cc, 9
  • Line 2: Source line at which the problem was detected.
  • Line 4: Description of the problem.
  • Line 5: Iterator declaration/information. Notice that the iterator does not "belong" to any container.
  • Line 7: Stack trace showing where the error occurred.

Repair

Before you attempt to use an iterator, you should be certain that all paths initialize or assign to it. In this example, there wasn't even a container to which iterator iter could have been bound. The following code shows the correct STL usage:

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI v(1);
	VI::iterator iter = v.begin(); // creates and binds the iterator
	int x = *iter;
	return 0;
}

Derefencing an Invalid Iterator

Valid iterators can become invalided by various STL operations.

Problem 1

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI v(10);
	VI::iterator iter1 = v.begin()+ 5;
	VI::iterator iter2 = iter1 + 3;
	v.erase(iter1); // both iterators are now invalid.
	int x = *iter2; // invalid iterator.
	return 0;
}

Diagnosis at Runtime

$ insure g++ -g -Zstl invalid_iterator.cc -o invalid_iterator
$ ./invalid_iterator
[invalid_iterator.cc:12] **STL_ERROR**
>>	 int x = *iter2;	 // invalid iterator.
Dereferencing invalid iterator.
	Iterator at: 0xbffff680 (stack)
			iter2, declared at invalid_iterator.cc, 10
	Container at: 0xbffff6b0 (stack)
			v, declared at invalid_iterator.cc, 8
Stack trace where iterator was bound:
				main() invalid_iterator.cc, 10
Stack trace where iterator was invalidated:
		vector<>::erase(iterator) (interface)
				main() invalid_iterator.cc, 11
Stack trace where the error occurred:
		iterator<>::operator*() (interface)
  • Line 3: Source line at which the problem was detected.
  • Line 5: Description of the problem.
  • Line 6: Iterator declaration/information and container to which the iterator is bound.
  • Line 10: Stack trace showing where the iterator was bound.
  • Line 12: Stack trace showing where the iterator was invalidated.
  • Line 15: Stack trace showing where the error occurred.

Repair

Be aware of what STL operations invalidate the iterators of the container. For example, a vector erase() operation not only invalidates any iterators pointing to the erased element, but also, it invalidates all iterators from that point to the end of the vector. Be certain that you understand these rules, (which are different for each container type), and follow them.

One way of correcting this invalid program is to re-task the iterator before using it:

v.erase(iter1); // both iterators are now invalid
iter2 = v.begin(); // iter2 is now retasked and is now valid
int x = *iter2; // valid dereference.

Problem 2

Although STLport and G++ can find some STL errors in debugging mode, the capabilities of Insure++ go beyond that. For example, Insure++ can catch uses of invalidated pointers and references, too:

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI v(10);
	VI::iterator iter1 = v.begin()+ 5;
	int* p = &v[8];
	v.erase(iter1); // iter1 and pointer "p" are now invalid.
	int x = *p; // READ_DANGLING (invalid pointer).
	return 0;
}

Diagnosis at Runtime

In the example shown above, the memory pointed to by p might still be physically present not deleted), however, it is logically no longer part of the vector. Therefore, it is an error to dereference any pointer or reference to it.

$ insure g++ -g -Zstl invalid_pointer.cc -o invalid_pointer
$ ./invalid_pointer
[invalid_pointer.cc:12] **READ_DANGLING**
>>		 int x = *p;	 // READ_DANGLING (invalid pointer).
Reading from a dangling pointer: p
Pointer : 0x08050070
In block: 0x08050064 thru 0x08050077 (20 bytes)
stack trace where memory was destroyed:
		vector<>::erase(iterator) (interface)
				main() invalid_pointer.cc, 11
this block was internal to STL container:
			v, declared at invalid_pointer.cc, 8
Stack trace where the error occurred:
				main() invalid_pointer.cc, 12 
  • Line 3: Source line at which the problem was detected.
  • Line 5: Description of the problem.
  • Line 6: Pointer information.
  • Line 8: Stack trace showing where the memory was destroyed/invalidated.
  • Line 11: Information showing that memory "belongs" to the STL container.
  • Line 13: Stack trace showing where the error occurred.

Repair

Repair of this problem is similar to the repair of Problem 1. The vector erase() operation not only invalidates the memory at the erased element, but also, it invalidates the memory at all iterators, references and pointers from the erased element to the end of the vector.

v.erase(iter1); // iter1 and pointer "p" are now invalid
p = &v[0]; // p is now retasked and is now valid
int x = *p; // valid dereference.

Derefencing an Iterator at End of Container

Insure++ also checks iterator boundary conditions.

Problem 

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI v;
	v.push_back(42); // v now contains one element.
	VI::iterator it = v.begin();

	for (size_t count = 0; count <= v.size(); ++count, ++it) {
		int x = *it; // deferencing iterator at end of container.
	}
	return 0;
}

Diagnosis at Runtime

$ insure g++ -g -Zstl at_end.cc -o at_end
$ ./at_end
[at_end.cc:13] **STL_ERROR**
>>		 int x = *it;
Dereferencing iterator at end of container.
Iterator at: 0xbffff6b0 (stack)
			it, declared at at_end.cc, 10
Container at: 0xbffff6c0 (stack)
			v, declared at at_end.cc, 8
Stack trace where iterator was bound:
			main() at_end.cc, 10
Stack trace where the error occurred:
	iterator<>::operator*() (interface)
			main() at_end.cc, 13
  • Line 3: Source line at which the problem was detected.
  • Line 5: Description of the problem.
  • Line 6: Iterator information showing where the iterator was declared and the container to which it is bound.
  • Line 9: Stack trace showing where the iterator was bound.
  • Line 11: Stack trace showing where the error occurred.

Repair

Because the loop termination condition is incorrect, it should be <, not <=, the iterator it eventually moves to the end of the vector. It is illegal to dereference an iterator once it has reached the end of the container.

The for-loop should have been written as follows:

for (size_t count = 0; count < v.size(); ++count) {

Iterator Bound to Wrong Container

Sometimes a valid iterator is not the only requirement. Certain STL operations require that the iterator not only be valid, but bound to the correct container for the given operation.

Problem

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI v1(10);
	VI v2;
	VI::iterator iter = v1.begin()+ 5;

	v2.insert(iter, v1.begin(), v1.end()); // wrong container
	// ^^^ should be an iterator into v2, not v1.
	return 0;
}

Diagnosis at Runtime

$ insure g++ -g -Zstl wrong_containers.cc -o wrong_containers
$ ./wrong_containers
[wrong_containers.cc:12] **STL_ERROR**
>>		 v2.insert(iter, v1.begin(), v1.end()); // wrong container
Iterator bound to wrong container.
	Iterator at: 0xbffff610 (stack)
			[argument 1], declared in dbg_vector.h
	Container at: 0xbffff6b0 (stack)
			v1, declared at wrong_containers.cc, 8
Stack trace where iterator was bound:
					main() wrong_containers.cc, 12
Container the iterator should have been bound to:
	Container at: 0xbffff690 (stack)
			v2, declared at wrong_containers.cc, 9
Stack trace where the error occurred:
vector<>::insert(iterator, InputIterator, InputIterator) (interface)
					main() wrong_containers.cc, 12
  • Line 3: Source line at which the problem was detected. 
  • Line 5: Description of the problem.
  • Line 6: Iterator information showing declaration and container to which it is currently bound. 
  • Line 10: Stack trace showing where the iterator was created and bound.
  • Line 12: Description of the container to which the iterator should have been bound.
  • Line 15: Stack trace showing where the error occurred. 

Repair

Be aware of the correct semantics for all STL operations. In this example, the user was trying to insert into vector v2 using an iterator that was bound to vector v1. The repair is straight-forward:

v2.insert(v2.begin(), v1.begin(), v1.end());

This operation has the effect of inserting a copy of all elements of vector v1 into vector v2 at the start of vector v2.

Iterator Refers to Different Containers

Some operations require an iterator range. A valid iterator range must have two valid iterators bound to the same container.

Problem

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI v1(10);
	VI v2(5);
	VI::iterator iter1 = v1.begin();
	VI::iterator iter2 = v2.begin();

	v2.insert(v2.begin(), iter1, iter2); // different containers.
	return 0;
}

Diagnosis at Runtime

$ insure g++ -g -Zstl different_containers.cc -o different_containers
$ ./different_containers
[different_containers.cc:13] **STL_ERROR**
>>		 v2.insert(v2.begin(), iter1, iter2); // different containers.
Iterators refer to different containers.
First iterator info:
	Iterator at:	 0xbffff630 (stack)
					[argument 2], declared in dbg_vector.h
	Container at:	 0xbffff6a0 (stack)
					v1, declared at different_containers.cc, 8
Stack trace where iterator was bound:
						main() different_containers.cc, 13
Second iterator info:
	Iterator at:	 0xbffff640 (stack)
					[argument 3], declared in dbg_vector.h
	Container at:	 0xbffff680 (stack)
					v2, declared at different_containers.cc, 9
Stack trace where iterator was bound:
						main() different_containers.cc, 13
Stack trace where the error occurred:
vector<>::insert(iterator, InputIterator, InputIterator) (interface)
						main() different_containers.cc, 13
  • Line 3: Source line at which the problem was detected.
  • Line 5: Description of the problem.
  • Line 6: First iterator description showing the container to which it is bound.
  • Line 11: Stack trace showing where the first iterator was bound.
  • Line 13: Second iterator description showing the container to which it is bound.
  • Line 18: Stack trace showing where the second iterator was bound.
  • Line 20: Stack trace showing where the error occurred.

Repair

Be aware of the implicit and explicit rules for proper STL usage. In this example, iter2 should have been bound to vector v1, not vector v2. The repair is straight-forward:

VI::iterator iter2 = v1.end();

Iterator Does Not Constitute Valid Range

A valid iterator range must be properly ordered.

Problem

#include <vector>
using namespace std;

typedef vector<int> VI;

int main()
{
	VI v(10);
	VI v2(v.end(), v.begin()); // invalid iterator range
	return 0;
}

Diagnosis at Runtime

$ insure g++ -g -Zstl invalid_range.cc -o invalid_range
$ ./invalid_range
[invalid_range.cc:9] **STL_ERROR**
>>			 VI v2(v.end(), v.begin()); // invalid iterator range
Iterators do not constitute valid range.
First iterator info:
	Iterator at:	 0xbffff650 (stack)
	Container at:	 0xbffff6b0 (stack)
			v, declared at invalid_range.cc, 8
Stack trace where iterator was bound:
				main() invalid_range.cc, 9
Second iterator info:
	Iterator at:	 0xbffff670 (stack)
	Container at:	 0xbffff6b0 (stack)
			v, declared at invalid_range.cc, 8
Stack trace where iterator was bound:
				main() invalid_range.cc, 9
Stack trace where the error occurred:
				main() invalid_range.cc, 9
  • Line 3: Source line at which the problem was detected.
  • Line 5: Description of the problem.
  • Line 6: Description of first iterator showing container to which it is bound.
  • Line 10: Stack trace showing how the first iterator was bound.
  • Line 12: Description of second iterator showing container to which it is bound.
  • Line 16: Stack trace showing how the second iterator was bound.
  • Line 18: Stack trace showing where the error occurred.

Repair

A valid range of iterators has a starting point logically "less than" its ending point. In this case, the range is invalid because the order of arguments in the constructor were swapped. The correction is straight-forward:

VI v2(v.begin(), v.end());

  • No labels