std :: vector 에의 삽입 vs. std :: deque 에의 삽입

나는 2017 Advent of Code에서 퍼즐을 푸는 중이었습니다. 특정 알고리즘을 사용하여 순환 버퍼를 채울 필요가있었습니다. 버퍼 구현을 위해 먼저 벡터를 사용하고 deque로 시도했다. 벡터와 큐의 값을 인쇄 할 때 다른 결과가 나타납니다. 20 (std :: vector 에의 삽입 vs. std :: deque 에의 삽입

0 2 1 
0 3 2 1 
0 3 2 4 1 
0 5 3 2 4 1 
0 6 5 3 2 4 1 
0 7 6 5 3 2 4 1 
0 7 6 8 5 3 2 4 1 
0 7 6 9 8 5 3 2 4 1 
0 10 7 6 9 8 5 3 2 4 1 
0 10 7 6 9 11 8 5 3 2 4 1 
0 10 7 6 9 11 8 5 3 2 4 12 1 
0 10 7 6 9 11 8 5 3 2 4 12 13 1 
0 10 7 6 9 11 8 5 3 2 4 12 14 13 1 
15 0 10 7 6 9 11 8 5 3 2 4 12 14 13 1 
...

와이 양단 큐를 사용하는 경우 (다만 "벡터"을 "양단 큐"를 변경하고 circularBuffer.reserve을 주석입니다 : 벡터를 사용하는 경우

#include <iostream> 
#include <vector> 

void PrintBuffer(std::vector<int> a_CircularBuffer) 
{ 
    for (std::vector<int>::iterator it = a_CircularBuffer.begin(); it != a_CircularBuffer.end(); ++it) { 
     std::cout << *it << " "; 
    } 
    std::cout << std::endl; 
} 

int main() 
{ 
    std::vector<int> circularBuffer; 
    circularBuffer.reserve(20); 

    circularBuffer.push_back(0); 
    circularBuffer.push_back(1); 

    std::vector<int>::iterator currentPosition = circularBuffer.begin() + 1; 

    for (int i = 2; i < 20; ++i) { 
     int steps = 378; 
     if (steps >= i) { 
      steps = (steps % i); 
     }  

     if ((circularBuffer.end() - currentPosition) <= steps) { 
      currentPosition = circularBuffer.begin() + (((currentPosition - circularBuffer.begin()) + steps) % i); 
      circularBuffer.insert(currentPosition, i); 
     } 
     else { 
      currentPosition = currentPosition + steps; 
      circularBuffer.insert(currentPosition, i); 
     } 
     PrintBuffer(circularBuffer); 
    } 
    return 0; 
}

이것은 결과입니다 : 여기에 코드는) 행) :

0 2 1 
0 3 2 1 
0 3 2 4 1 
0 5 3 2 4 1 
0 5 6 3 2 4 1 
0 5 6 7 3 2 4 1 
0 5 6 7 3 8 2 4 1 
0 5 6 7 3 9 8 2 4 1 
0 5 6 10 7 3 9 8 2 4 1 
0 5 6 10 7 3 9 8 11 2 4 1 
0 5 12 6 10 7 3 9 8 11 2 4 1 
0 5 12 6 13 10 7 3 9 8 11 2 4 1 
0 5 12 6 13 14 10 7 3 9 8 11 2 4 1 
0 5 12 6 13 14 10 7 3 15 9 8 11 2 4 1 
...

왜 vector와 deque에 대한 결과가 다른가요?

출처

2017-12-17 adamm

재 할당을 유발하는 요소를 삽입 할 때 정의되지 않은 동작이 발생하고 이전 반복기를 다시 사용하십시오.

아무거나 발생할 수 있습니다.

색인을 사용하여 현재 위치를 저장하면 동일한 방식으로 작동합니다.

출처

2017-12-17 21:49:59 RiaD

감사합니다. 예, 나중에 인덱스를 사용하여 현재 위치를 저장했으며 deque 및 iterators와 같은 방식으로 작업했습니다. 나는 왜 벡터가 다른지를 방황하고 있었는데 그것이 정의되지 않은 행동이라는 것을 몰랐다. 또한, 내가이 일을 할 때 currentPosition = circularBuffer.insert (currentPosition, 전), 나는 이전과 같은 결과를 얻고있다. 나는 이것이 currentPosition 반복자를 "갱신"할 것이라고 생각했다. – adamm

한 가지 더, 충분한 공간을 확보 한 경우 (그리고 내가 한 경우) 재 할당이 없어야합니다. 맞습니까? 그렇다면 이터레이터는 괜찮을 것입니다. – adamm

재 할당 할 필요가 없더라도 UB를 큐에 넣을 수 없습니다> 삽입의 처음이나 끝에서 삽입이 발생하면이 컨테이너와 관련된 모든 반복자는 무효화되지만 포인터와 참조는 참조 된 동일한 요소를 참조하여 유효합니다. 전화하기 전에. 삽입이 deque의 다른 곳에서 일어나면이 컨테이너와 관련된 모든 반복기, 포인터 및 참조가 무효화됩니다. – RiaD

std :: vector 에의 삽입 vs. std :: deque 에의 삽입

답변

관련 문제