Как перебрать список, добавляя в нее элементы

Question

У меня есть список отрезков (в std::vector<std::pair<int, int> >, что я хотел бы перебирать и подразделяют алгоритм будет, в 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)); 

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

Похоже, что наилучшим подходом может быть сделать копию этого вектора сначала, и используйте копию в качестве ссылки, clear() оригинальный вектор, а затем push_back новый элемент s к недавно опустошенному вектору.

Есть ли лучший подход к этому?

Answer 1

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

Практически. Вам не нужно копировать и очищать; переместить вместо этого!

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

Не удаляйте элементы при вставке новых сегментов. Затем, когда закончите с установкой можно удалить оригиналы:

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); 

Или, если вы хотите заменить один сегмент на два новых сегментов в один проход, вы можете использовать итераторы, как здесь:

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

Как указывал Lightning Racis на Orbit, вы должны сделать reserve перед любым из этих подходов. В первом случае не reserve(vectorOfSegmets.size()*3), в последнем reserve(vectorOfSegmets.size()*2+1)

Answer 3

Это проще всего решается с помощью явного индексную переменную так:

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

Примечания:

• segments.size() вызывается в каждой итерации цикла, так что мы действительно пересмотреть все добавленные сегменты.

• Явный индекс означает, что std::vector<> может свободно перераспределять в вызове emplace_back(), нет итераторов/указателей/ссылок, которые могут стать недействительными.

• Я предполагал, что вам не нужен порядок вашего вектора, потому что вы добавляете новые сегменты в конец вектора. Если вам все равно, вы можете использовать связанный список, чтобы избежать квадратичной сложности вашего алгоритма, поскольку вставка/удаление в/из std::vector<> имеет линейную сложность. В моем коде я избегаю вставки/удаления, заменив старый сегмент.

  Другим подходом к удержанию заказа является сначала игнорировать порядок, а затем восстановить порядок путем сортировки. Предполагая хороший алгоритм сортировки, то есть O (n * log (n)), который по-прежнему лучше наивного O (n^2), но хуже, чем O (n) подхода связанного списка.

• Если вы не хотите, чтобы пересмотреть новые сегменты, просто использовать постоянный размер и опустить счетчик декремент:

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