How to iterate through a list while adding items to it

Question

I have a list of line segments (a std::vector<std::pair<int, int> > that I'd like to iterate through and subdivide. The algorithm would be, in psuedocode:

for segment in vectorOfSegments:
    firstPoint = segment.first;
    secondPoint = segment.second;
    newMidPoint = (firstPoint + secondPoint) / 2.0
    vectorOfSegments.remove(segment);
    vectorOfSegments.push_back(std::make_pair(firstPoint, newMidPoint));
    vectorOfSegments.push_back(std::make_pair(newMidPoint, secondPoint));

The issue that I'm running into is how I can push_back new elements (and remove the old elements) without iterating over this list forever.

It seems like the best approach may be to make a copy of this vector first, and use the copy as a reference, clear() the original vector, and then push_back the new elements to the recently emptied vector.

Is there a better approach to this?

Answer 1

It seems like the best approach may be to make a copy of this vector first, and use the copy as a reference, clear() the original vector, and then push_back the new elements to the recently emptied vector.

Almost. You don't need to copy-and-clear; move instead!

// Move data from `vectorOfSegments` into new vector `original`.
// This is an O(1) operation that more than likely just swaps
// two pointers.
std::vector<std::pair<int, int>> original{std::move(vectorOfSegments)};

// Original vector is now in "a valid but unspecified state".
// Let's run `clear()` to get it into a specified state, BUT
// all its elements have already been moved! So this should be
// extremely cheap if not a no-op.
vectorOfSegments.clear();

// We expect twice as many elements to be added to `vectorOfSegments`
// as it had before. Let's reserve some space for them to get
// optimal behaviour.
vectorOfSegments.reserve(original.size() * 2);

// Now iterate over `original`, adding to `vectorOfSegments`...

Answer 2

Don't remove elements while you insert new segments. Then, when finished with inserting you could remove the originals:

int len=vectorOfSegments.size();
for (int i=0; i<len;i++)
{
    std::pair<int,int>& segment = vectorOfSegments[i];
    int firstPoint = segment.first;
    int secondPoint = segment.second;
    int newMidPoint = (firstPoint + secondPoint) / 2;
    vectorOfSegments.push_back(std::make_pair(firstPoint, newMidPoint));
    vectorOfSegments.push_back(std::make_pair(newMidPoint, secondPoint));
}
vectorOfSegments.erase(vectorOfSegments.begin(),vectorOfSegments.begin()+len);

Or, if you want to replace one segment by two new segments in one pass, you could use iterators like here:

for (auto it=vectorOfSegments.begin(); it != vectorOfSegments.end(); ++it)
{
    std::pair<int,int>& segment = *it;
    int firstPoint = segment.first;
    int secondPoint = segment.second;
    int newMidPoint = (firstPoint + secondPoint) / 2;
    it = vectorOfSegments.erase(it);
    it = vectorOfSegments.insert(it, std::make_pair(firstPoint, newMidPoint));
    it = vectorOfSegments.insert(it+1, std::make_pair(newMidPoint, secondPoint));
}

As Lightning Racis in Orbit pointed out, you should do a reserve before either of these approaches. In the first case do reserve(vectorOfSegmets.size()*3), in the latter reserve(vectorOfSegmets.size()*2+1)