알고리즘 비용을 계산하는 것이 좋지 않으므로 여기에서 질문합니다.역방향 및 팝/푸시 _ 백 비용이 적용된 STL 벡터
vector<unsigned int> mFreeIndexes(1000);
내가 지속적으로 (재 할당 벡터를 강제로 이렇게 않음) 결코와 push_back을 통해 1000 벡터에 /와 push_back 요소와 pop_back,하지만 것 : 여기
는 처음 1000 개 요소로 초기화 벡터이다. 이 경우 는와 pop_back /와 push_back 조작 것이다 O (1) 또는 (N) O? 는 C에서++ 표준 23.3.7.5 :
보이드와 push_back (CONST T & X);
보이드와 push_back (T & & X);
비고 : 새로운 사이즈가 기존 용량 (...) 그것은 다른 시나리오에서 재 할당 할 수없는 말을하지 않는
주보다 큰하지만이 될 경우 재 할당 원인 이 표준의 매우 특별한 구현. 나는 아직도 용량이있을 때 push_back이 재 할당하지 않을 것이라고 생각합니다.
pop_back을 가진 것은 좀 더 복잡하다. 이 표준은 pop_back 컨텍스트에서 재 할당에 대해 아무 것도 말하지 않습니다. 그러나 이것은 알 수없는 예외없이 pop_back이 재 할당되지 않는 일반적인 구현 인 것으로 보입니다. 일부 보장하지만이 있으며,이를 참조하십시오
Can pop_back() ever reduce the capacity of a vector? (C++)
어쨌든만큼 당신이 미리 정의 된 크기 이상하지 않는 한 더 재 할당이 발생 없다고 가정하는 것이 안전하고 복잡성이 참으로 O (1).
재 할당이 수행되지 않는 한 O (1)이어야합니다. –
'push_back'하면 벡터에 요소를 추가합니다. 위의 정의 이후에, 예를 들어 'mFreeIndexes.push_back (1);'그러면 벡터는 1001 개의 요소를 갖게됩니다. 아마도 '예비'(http://en.cppreference.com/w/cpp/container/vector/reserve) 기능을 원하십니까? –
이 질문에 대한 답변은 이미 [documentation] (http://en.cppreference.com/w/cpp/container/vector/pop_back)에서 확인하실 수 있습니다. – nwp