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

Estou iterando sobre um vetor e preciso do índice que 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 os contras desses métodos?

Eu preferiria it - vec.begin()precisamente pela razão oposta dada por Naveen: para que não compile se você mudar o vetor em uma lista. Se você fizer isso durante todas as iterações, poderá facilmente transformar um algoritmo O (n) em um algoritmo O (n ^ 2).

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

Nota: ité um nome comum para um iterador de contêiner std::container_type::iterator it;,.

Eu preferiria std::distance(vec.begin(), it), pois me permitirá alterar o contêiner sem nenhuma alteração no código. Por exemplo, se você decidir usar em std::listvez de std::vectornão fornecer um iterador de acesso aleatório, seu código ainda será compilado. Como o std :: distance escolhe o método ideal, dependendo das características do iterador, você também não terá nenhuma degradação no desempenho.

Como o UncleBens e Naveen mostraram, há boas razões para ambos. Qual é "melhor" depende do comportamento que você deseja: deseja garantir o comportamento em tempo constante ou deseja que ele volte ao tempo linear quando necessário?

it - vec.begin()leva tempo constante, mas operator -é definido apenas em iteradores de acesso aleatório; 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 somente será uma operação de tempo constante se usado em iteradores de acesso aleatório.

Nenhum dos dois é "melhor". Use aquele que faz o que você precisa.

Eu gosto deste: it - vec.begin()porque para mim diz claramente "distância do começo". Com os 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 um std::vector::iteratore std::vector::iteratorsomente, não importa realmente qual método você vai usar. Seu algoritmo já está concretizado além do ponto em que a escolha de um dos outros pode fazer qualquer diferença. Ambos fazem exatamente a mesma coisa. É apenas uma questão de preferência pessoal. Eu pessoalmente usaria subtração explícita.

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

• Se você usar a subtração explícita, seu algoritmo será restrito a uma classe bastante estreita de iteradores: iteradores de acesso aleatório. (É disso que você obtém agora std::vector)

• Se você usar distance, seu algoritmo suportará uma classe muito maior de iteradores: iteradores de entrada.

Obviamente, calcular distancepara iteradores de acesso não aleatório é geralmente uma operação ineficiente (enquanto, novamente, para iteradores de acesso aleatório é tão eficiente quanto subtração). Cabe a você decidir se o seu algoritmo faz sentido para iteradores de acesso não aleatório, em termos de eficiência. Como a perda de eficiência resultante é 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 procurar soluções alternativas para outros tipos de iteradores. Se a eficiência com iteradores de acesso não aleatório ainda estiver no intervalo utilizável, você deve usar distancee documentar o fato de que o algoritmo funciona melhor com iteradores de acesso aleatório.

De acordo com http://www.cplusplus.com/reference/std/iterator/distance/ , como vec.begin()é um iterador de acesso aleatório , o método de distância usa o -operador.

Portanto, a resposta é, do ponto de vista do desempenho, a mesma, mas talvez o uso distance()seja mais fácil de entender se alguém precisaria ler e entender seu código.

Eu usaria a -variante std::vectorapenas - é bem claro o que significa, e a simplicidade da operação (que não é mais que uma subtração de ponteiro) é expressa pela sintaxe ( distancedo outro lado, soa como pitágoras no primeira leitura, não é?). Como destaca o UncleBen, -também atua como uma asserção estática, caso vectorseja acidentalmente alterado paralist .

Também acho que é muito mais comum - embora não tenha números para provar. 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 uma questão de gosto, esse também pode ser um argumento válido.

Aqui está um exemplo para encontrar "todas" ocorrências de 10 junto com o índice. Pensei que isso seria de alguma ajuda.

void _find_all_test()
{
    vector<int> ints;
    int val;
    while(cin >> val) ints.push_back(val);

    vector<int>::iterator it;
    it = ints.begin();
    int count = ints.size();
    do
    {
        it = find(it,ints.end(), 10);//assuming 10 as search element
        cout << *it << " found at index " << count -(ints.end() - it) << endl;
    }while(++it != ints.end()); 
}