Sat
30
Sep 2023

This will be a short article about basics of C++. std::vector is a container that dynamically allocates a continuous array of elements. There are multiple ways to write a for loop to iterate over its elements. In 2018 I've written an article "Efficient way of using std::vector" where I compared their performance. I concluded that using iterators can be orders of magnitude slower than using a raw pointer to its data in Debug configuration. This time, I would like to focus on how using "modern" C++ also limits our freedom.

Language purists would probably say that the recommended way to traverse a vector is now a range-based for loop, available since C++11. This is indeed the shortest and the most convenient form, but inside the loop it gives access only to the current element, not its index and not any other elements.

struct Item
{
    int number;
    int otherData[10];
};

std::vector<Item> items = ...

int numberSum = 0;
for(const Item& item : items)
    numberSum += item.number;

Imagine that while traversing the vector, for some elements that are not the first and that meet certain criteria, we want to compare them with their previous element. This is not possible in a range-based for loop above, unless we memorize the previous element in a separate variable and update it on every iteration. Using iterators gives us the possibility to move forward or backward and thus to access the previous element when needed.

for(std::vector<Item>::const_iterator currIt = items.begin(); currIt != items.end(); ++currIt)
{
    if(currIt != items.begin() && // Not the first
        MeetsCriteria(*currIt))
    {
        std::vector<Item>::const_iterator prevIt = currIt;
        --prevIt; // Step back to the previous element
        CompareWithPrevious(*prevIt, *currIt);
    }
}

This is more flexible, but what if we want to insert some elements to the vector while traversing it? There is a trap awaiting here because insert method may invalidate all iterators when underlying array gets reallocated. This is why only iterating using an index is safe here:

for(size_t index = 0; index < items.size(); ++index)
{
    Item newItem;
    if(NeedInsertItemBefore(items[index], &newItem))
    {
        items.insert(items.begin() + index, newItem);
        ++index;
    }
}

Note that pretty much any modern programming language allows to insert and remove elements from a dynamic array using an index, e.g.:

• C#: List methods Insert, RemoveAt
• Java: ArrayList methods add, remove
• JavaScript: array method splice
• Python: list methods insert, pop
• Even Rust, which also supports iterators, offers Vec methods insert, remove that take index as parameter.

Only C++ requires clumsy syntax with iterators like items.begin() + index.

I know that the code fragments shown above can be written in many other ways, e.g. using auto keyword. If you have an idea for writing any of these loops better way, please leave a comment below and let's discuss.

Comments | #c++ Share

Comments