Qual é a maneira mais eficaz de obter o índice de um iterador de um std :: vector?

Estou interagindo com um vetor e preciso do índice para o qual o iterador está apontando no momento. AFAIK isso pode ser feito de duas maneiras:

  • it - vec.begin()
  • std::distance(vec.begin(), it)

Quais são os prós e contras desses methods?

Eu preferiria it - vec.begin() precisamente pela razão oposta dada por Naveen: então não compilaria se você alterasse o vetor em uma lista. Se você fizer isso durante cada iteração, poderá facilmente transformar um algoritmo O (n) em um algoritmo O (n ^ 2).

Outra opção, se você não pular no contêiner durante a iteração, seria manter o índice como um segundo contador de loop.

Eu preferiria std::distance(vec.begin(), it) , pois permitirá alterar o contêiner sem nenhuma alteração de código. Por exemplo, se você decidir usar std::list vez de std::vector que não fornece um iterador de access random, seu código ainda será compilado. Como std :: distance pega o método ótimo, dependendo das características do iterador, você também não terá nenhuma degradação no desempenho.

Como UncleBens e Naveen mostraram, há boas razões para ambos. Qual deles é “melhor” depende de qual comportamento você quer: Você quer garantir um comportamento em tempo constante, ou você quer que ele volte ao tempo linear quando necessário?

it - vec.begin() leva tempo constante, mas o operator - é definido apenas em iteradores de access random, portanto, o código não será compilado com iteradores de lista, por exemplo.

std::distance(vec.begin(), it) funciona para todos os tipos de iteradores, mas só será uma operação de tempo constante se usada em iteradores de access random.

Nenhum deles é “melhor”. Use o que faz o que você precisa.

Eu gosto deste: it - vec.begin() , porque para mim diz claramente “distância do começo”. Com iteradores estamos acostumados a pensar em termos de aritmética, então o sinal - é o indicador mais claro aqui.

Se você já restringiu / codificou seu algoritmo para usar apenas um std::vector::iterator e std::vector::iterator , não importa qual método você usará. Seu algoritmo já está concretizado além do ponto em que escolher um dos outros pode fazer alguma diferença. Ambos fazem exatamente a mesma coisa. É apenas uma questão de preferência pessoal. Eu usaria pessoalmente a subtração explícita.

Se, por outro lado, você quiser manter um grau maior de generalidade em seu algoritmo, ou seja, permitir a possibilidade de que algum dia no futuro ele possa ser aplicado a algum outro tipo de agente iterativo, então o melhor método depende da sua intenção. . Depende de quão restritivo você quer ser em relação ao tipo de iterador que pode ser usado aqui.

  • Se você usar a subtração explícita, seu algoritmo ficará restrito a uma class bastante restrita de iteradores: iteradores de access random. (Isto é o que você obtém agora de std::vector )

  • Se você usar a distance , seu algoritmo suportará uma class muito maior de iteradores: input iterators.

Obviamente, o cálculo da distance para iteradores de access não random é, em geral, uma operação ineficiente (enquanto, novamente, para os de access random, é tão eficiente quanto a subtração). Cabe a você decidir se o seu algoritmo faz sentido para os iteradores de access não random, em termos de eficiência. Se a perda de eficiência resultante for devastadora a ponto de tornar seu algoritmo completamente inútil, é melhor se ater à subtração, proibindo assim os usos ineficientes e forçando o usuário a buscar soluções alternativas para outros tipos de iteradores. Se a eficiência com iteradores de access não random ainda estiver no intervalo utilizável, você deverá usar a distance e documentar o fato de que o algoritmo funciona melhor com iteradores de access random.

De acordo com http://www.cplusplus.com/reference/std/iterator/distance/ , como vec.begin() é um iterador de access random , o método distance usa o operador - .

Então, a resposta é, do ponto de vista do desempenho, é o mesmo, mas talvez usar distance() seja mais fácil de entender se alguém tiver que ler e entender seu código.

Eu usaria a - variante para std::vector apenas – é bem claro o que significava, e a simplicidade da operação (que não é mais do que uma subtração de ponteiro) é expressa pela syntax ( distance , do outro lado). Soa como Pitágoras na primeira leitura, não é? Como o UncleBen aponta, - também atua como uma afirmação estática no caso de vector ser acidentalmente alterado para list .

Também acho que é muito mais comum – não tem números para provar isso, no entanto. Argumento mestre: it - vec.begin() é mais curto no código-fonte – menos trabalho de digitação, menos espaço consumido. Como está claro que a resposta certa para sua pergunta se resume a ser uma questão de gosto, este também pode ser um argumento válido.