Note 21.2.1.
Accessing elements by position like this is is often referred to as random access. It is not that we are accessing a random element, but rather that we can directly access any “random”element we want by its position.
Section 21.2 Traversing Containers
A
list allows for things that would be much more difficult or inefficient with a vector. However, they do have their own limitations. One key limitation is that none of these containers allow you to access elements directly by their position (index) in the collection. Given a std::list it is an error to say something like myList.at(3) to try to get the 4th element.
Because lists do not support access by index, we can’t write a counting loop that goes from 0 to size()-1 and accesses each element using
.at(i). Instead, we have to use an iterator to walk through all the elements in the container. (Or use a range based loop, which behind the scenes uses iterators.)
When we introduced iterators in Section 13.6, we described them as a way to specify the location of an element in a vector. In a vector, an iterator feels a little redundant because we can also specify locations using indices. But in containers like lists, iterators are essential because we can not say “the thing at index 3”.
Think of an iterator as a “smart pointer” to an element in a collection. It can be used to access the element it points to. Depending on the type of collection, the iterator may also be able to move to the next or previous element in the collection, and/or jump to a particular element.
In a vector, we could get an iterator to the start of the vector using
.begin() and an iterator to one past the end using .end(). We could then modify that iterator using expressions like myVec.begin() + 2 to get an iterator that points to the third element of the vector.
Other standard containers provide iterators as well. And, where they provide similar capabilities, the syntax is the same. Given a
std::list called myList, we can get an iterator to the start of the list using myList.begin() and one past the end using myList.end(). However, not all iterator types provide the same capabilities.
For example, in containers like lists, we can’t jump forward or backward multiple items at a time the way we can with a vector iterator. Instead, we can only move an iterator forward one element at a time using the preincrement operator (
++it) or backwards one element at a time using the predecrement operator (--it). This means that to get to the 3rd element in a list, we would need to start at myList.begin() and then do ++ two times to move forward to the 3rd element.
begin() still gives an iterator to the first element and end() to one past the last element. But an iterator can only move forward or backward one element at a time. Given where it is, there is no way to jump directly to the 4th element.The type of a list iterator is list<T>::iterator, where T is the type of elements in the list. So for a
list<string>, the iterator type would be
list<string>::iterator.
To access the element that an iterator points to, we use the dereference operator (
*it). This gives us access to the element the iterator is pointing at. We can either read that value or assign to the element.
Insight 21.2.2.
The syntax
*it looks just like the syntax for dereferencing a pointer in C++. The iterator is not a pointer, but it acts like one in many ways.
This program demonstrates how to use an iterator to access the third element in a list. It also includes some illegal attempts to access elements by position. You can try uncommenting those lines to see that they do not compile.
Checkpoint 21.2.1.
You have attempted of activities on this page.
