Идиоматический 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

Решение Стивена хорошее, но в интересах образования вы можете зациклить сразу две переменные:

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

Перемещение вашего итератора назад и вперед, как это несколько запутываетТакже обратите внимание, что ни этот, ни ваш исходный код не очень любят пустые списки.

Answer 3

Вам не нужно перехватывать возвращаемое значение вставки списка в итератор. Таким образом, вам не нужно увеличивать его вручную.

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

Answer 4

Мне не нравится упоминать типы итераторов, потому что 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 5

Тебе итеративное решение вполне понятно. Я знаю, когда вы говорите: «Я надеюсь, что смогу чему-то научиться», это не то, что вы намеревались, но я надеюсь, что вы выучите:

1) Нет смысла находить «элегантное» функциональное решение проблемы, которую вы итеративно решили итеративно,

2) Функциональное программирование в C ++ утомительно, даже более, чем C ++ уже утомительно.