惯用的 STL：迭代列表并插入元素

Question

我正在编写一个算法，该算法迭代点列表，计算它们之间的距离，并在距离太大时插入附加点。然而，我似乎对 STL 缺乏适当的熟悉，无法想出一个优雅的解决方案。我希望我能学到一些东西，所以我只会向你展示我的代码。你可能会给我一些提示。

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

考虑使用 adjacent_find 查找连续元素之间距离过大的迭代器位置，然后插入 pointsToInsert 项。

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

此外，您可以使用带有函子的generate来填充中间点。

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

不确定你想对 STL 有多深入:)

Answer 2

您的迭代解决方案是完全可以理解的。我知道当你说“我希望我能学到一些东西”时，这不是你的本意，但我希望你学到的是：

1）为你遇到的问题找到一个“优雅”的功能解决方案没有任何好处以很好的方式迭代解决

2) C++ 中的函数式编程很乏味，甚至比 C++ 已经乏味的还要多。

Answer 3

我不喜欢提及迭代器类型，因为 1.) 它们有点丑陋，2.) 如果我更改集合类型，它会减少我必须做出的更改，所以我可能会做这样的事情......

我做了一些额外的调整，这些调整可能更符合我的个人风格，而不是惯用的。

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

您不必捕获列表插入到迭代器的返回值。这样，您就不需要手动增加它。

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

Answer 5

斯蒂芬的解决方案是一个很好的解决方案，但为了教育的目的，您可以一次循环两个变量：

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
        }
    }
}

像这样来回移动迭代器有点令人困惑。另请注意，无论是这个还是您的原始代码都不太喜欢空列表。