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

This is easiest solved by using an explicit index variable like this:

for(size_t i = 0; i < segments.size(); i++) {
    ...    //other code
    if(/*condition when to split segments*/) {
        Point midpoint = ...;
        segments[i] = Segment(..., midpoint);    //replace the segment by the first subsegment
        segments.emplace_back(Segment(midpoint, ...));    //add the second subsegment to the end of the vector
        i--;    //reconsider the first subsegment
    }
}

Notes:

• segments.size() is called in each iteration of the loop, so we really reconsider all appended segments.

• The explicit index means that the std::vector<> is free to reallocate in the emplace_back() call, there are no iterators/pointers/references that can become invalid.

• I assumed that you don't care about the order of your vector because you add the new segments to the end of the vector. If you do care, you might want to use a linked list to avoid quadratic complexity of your algorithm as insertion/deletion to/from an std::vector<> has linear complexity. In my code I avoid insertion/deletion by replacing the old segment.

  Another approach to retain order would be to ignore order at first and then reestablish order via sorting. Assuming a good sorting algorithm, that is O(n*log(n)) which is still better than the naive O(n^2) but worse than the O(n) of the linked list approach.

• If you don't want to reconsider the new segments, just use a constant size and omit the counter decrement:

  size_t count = segments.size();
  for(size_t i = 0; i < count; i++) {
      ...    //other code
      if(/*condition when to split segments*/) {
          Point midpoint = ...;
          segments[i] = Segment(..., midpoint);    //replace the segment by the first subsegment
          segments.emplace_back(Segment(midpoint, ...));    //add the second subsegment to the end of the vector
      }
  }
  

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)

Answer 3

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`...