Idiomatic STL: Iterating over a list and inserting elements

Question

I'm writing an algorithm that iterates over a list of points, calculates the distance between them and inserts additional points if the distance is too great. However I seem to be lacking the proper familiarity with STL to come up with an elegant solution. I'm hoping that I can learn something, so I'll just show you my code. You might have some hints for me.

for (std::list<PathPoint>::iterator it = ++points_.begin();
     it != points_.end(); it++)
{
    Vector curPos = it->getPosition();
    Vector prevPos = (--it)->getPosition();
    Vector vecFromPrev = curPos - prevPos;
    float distance = vecFromPrev.abs();
    it++;
    if (distance > MAX_DISTANCE_BETWEEN_POINTS)
    {               
        int pointsToInsert = (int)(distance / MAX_DISTANCE_BETWEEN_POINTS);             
        Vector curPos = prevPos;                
        for (int i = 0; i < pointsToInsert; i++)
        {
            curPos += vecFromPrev / pointsToInsert;
            it = points_.insert(it, PathPoint(curPos, false));
            it++;
        }
    }
}

Answer 1

Consider using adjacent_find to find an iterator position where the distance between consecutive elements is too large, then inserting pointsToInsert items.

http://www.sgi.com/tech/stl/adjacent_find.html

In addition, you could use generate with a functor to fill in the intermediate points.

http://www.sgi.com/tech/stl/generate.html

Not sure how deep you want to go into STL :)

Answer 2

You're iterative solution is perfectly understandable. I know when you say "I'm hoping that I can learn something" this is not what you intended, but what I hope you learn is:

1) There is no benefit to finding an "elegant" functional solution to a problem you have solved iteratively in a fine way

2) Functional programming in C++ is tedious, even more so than C++ is already tedious.

Answer 3

I don't like mentioning the iterator types because 1.) they're kind of ugly and 2.) it reduces the changes I have to make if I change collection types, so I would probably do something like this....

I made a couple additional tweaks that are probably more my personal style than idiomatic.

this->addAdditionalPoints(points.begin(), points.end());


template<typename InIt>
void MyClass::addAdditionalPoints(InIt start, InIt finish)
{
   InIt it = start;
   ++it;                                      // Starting with second element
   for (; it != finish; ++it)  // I usually pre-increment iterators, but 
                                             // it probably doesn't matter.
   {
      InIt curr = it;                       // Work with a temp rather than loop index
      Vector curPos = curr->getPosition();
      Vector prevPos = (--curr)->getPosition();
      Vector vecFromPrev = curPos - prevPos;
      float distance = vecFromPrev.abs();
      ++curr;                             // Prefer to pre-increment iterators
      if (distance > MAX_DISTANCE_BETWEEN_POINTS)
      {               
          int pointsToInsert = static_cast<int>(distance /              
              MAX_DISTANCE_BETWEEN_POINTS);  // I prefer C++-style casts     
          Vector curPos = prevPos;                
          for (int i = 0; i < pointsToInsert; i++)
          {
              curPos += vecFromPrev / pointsToInsert;
              curr = points_.insert(curr, PathPoint(curPos, false));
              ++curr;  // Again I prefer to pre-increment iterators
          }
      }
   }
}

Answer 4

You don't have to catch the return value of the list insert to the iterator. That way, you don't need to manually increment it.

for (int i = 0; i < pointsToInsert; i++)
{
    curPos += vecFromPrev / pointsToInsert;
    points_.insert(it, PathPoint(curPos, false));
}

Answer 5

Stephen's solution is a good one, but in the interest of education, you can loop over two variables at once:

typedef typename std::list<PathPoint>::iterator Itr; //Pointless, but just to illustrate the possibility
for(Itr cur = points_.begin(), prev = cur++; cur != points_.end(); ++prev, ++cur) {
    Vector curPos = cur->getPosition();
    Vector prevPos = prev->getPosition();
    Vector vecFromPrev = curPos - prevPos;
    float distance = vecFromPrev.abs();
    if (distance > MAX_DISTANCE_BETWEEN_POINTS) {               
        int pointsToInsert = (int)(distance / MAX_DISTANCE_BETWEEN_POINTS);             
        Vector curPos = prevPos;                
        for (int i = 0; i < pointsToInsert; i++) {
            curPos += vecFromPrev / pointsToInsert;
            prev = points_.insert(cur, PathPoint(curPos, false));
            //as somebody mentioned, `cur` remains valid during `list` insertions
        }
    }
}

Moving your iterator back and forth like that is somewhat confusing. Also, note that neither this, nor your original code, like empty lists very much.