Oi pessoal,
Digamos que eu tenha uma lista com 10 posições. Quero inserir um valor na lista que fique na posição 4, por exemplo. Claro que quero que minha list se encarregue de qualquer realocação necessária.
Olhando o método insert (http://www.cplusplus.com/reference/stl/list/insert/) ele parece ser o que preciso. Mas a impressão que tenho é que teria que iterar sobre a lista até a posição 4, para então ter um iterator válido para aquela posição e então poder usar o insert. É isso mesmo? Não tem algum jeito de simplesmente passar a posição onde quero que o novo elemento fique sem ter de iterar sobre a lista antes?
Você quer usar um (que é uma lista duplamente ligada) ou um ?
No caso de um , para inserir na 4a. posição (supondo que você saiba que esse list tem 4 posições ou mais) você pode usar o algoritmo “advance” para obter um iterador que aponta para a 4a. posição.
http://www.cplusplus.com/reference/std/iterator/advance/
Estou optando por uma list ao invés de vector pois de vez em quando preciso dar um push_front nela. Se fosse um vector, teria um jeito mais simples de dar o insert?
Em particular, eu normalmente prefiro usar uma “deque” em vez de uma “list”. Elas costumam gastar menos memória (porque são organizadas como listas de vetores, não como listas duplamente ligadas) e têm essa vantagem do acesso aleatório.
Eu estava usando uma deque também. Acabei trocando por list por conta desse trecho aqui que encontrei na página sobre o deque::insert no cplusplus.com: Insertions on other positions are usually less efficient than in list containers.
É porque se você estiver inserindo na primeira posição (por exemplo), você pode ter a seguinte situação:
a) O primeiro “chunk” do deque não está cheio - nesse ponto, o deque se comporta como um vector. Se a sua versão do compilador é antiga suficiente para não aceitar o “&&” (“move reference”), que é um tipo novo do C++0X, então ele irá chamar o copy constructor do tipo do vector (ou deque) vezes suficientes para poder mover os elementos de uma posição dentro do vector (ou deque).
b) O primeiro “chunk” está cheio - nesse caso, é necessário quebrar o chunk em dois - imagine o que tem de ser feito em termos de cópias então.
Eu normalmente não tenho deques tão grandes para eu ter de me preocupar com isso 
Mas então, seja qual for a estrutura, o jeito mais fácil pra dar o insert é usando o advance mesmo?