Maneira eficiente de retornar um std :: vector em c ++

106

Quantos dados são copiados, ao retornar um std :: vector em uma função e quão grande será a otimização para colocar o std :: vector no free-store (no heap) e retornar um ponteiro, isto é:

std::vector *f()
{
  std::vector *result = new std::vector();
  /*
    Insert elements into result
  */
  return result;
} 

mais eficiente do que:

std::vector f()
{
  std::vector result;
  /*
    Insert elements into result
  */
  return result;
} 

?

Morten
fonte
3
Que tal passar o vetor por referência e depois preenchê-lo f?
Kiril Kirov
4
RVO é uma otimização bastante básica que muitos compiladores serão capazes de fazer a qualquer momento.
Remus Rusanu
Conforme as respostas fluem, pode ajudá-lo a esclarecer se você está usando C ++ 03 ou C ++ 11. As melhores práticas entre as duas versões variam um pouco.
Drew Dormann
@Kiril Kirov, posso fazer isso sem colocá-lo na lista de argumentos da função. void f (std :: vector & result)?
Morten

Respostas:

140

Em C ++ 11, esta é a forma preferida:

std::vector<X> f();

Ou seja, retorno por valor.

Com o C ++ 11, std::vectortem semântica de movimento, o que significa que o vetor local declarado em sua função será movido no retorno e em alguns casos até mesmo o movimento pode ser omitido pelo compilador.

Nawaz
fonte
13
@LeonidVolnitsky: Sim, se for local . Na verdade, return std::move(v);desativará a elisão de movimento mesmo que fosse possível com apenas return v;. Portanto, o último é o preferido.
Nawaz,
1
@juanchopanza: Acho que não. Antes do C ++ 11, você poderia argumentar contra isso porque o vetor não será movido; e RVO é uma coisa dependente do compilador! Fale sobre as coisas dos anos 80 e 90.
Nawaz
2
Meu entendimento sobre o valor de retorno (por valor) é: em vez de 'foi movido', o valor de retorno no receptor é criado na pilha do chamador, então todas as operações no receptor estão no lugar, não há nada para mover no RVO . Isso é correto?
r0ng
2
@ r0ng: Sim, é verdade. É assim que os compiladores geralmente implementam RVO.
Nawaz,
1
@Nawaz Não é. Não há mais nem mesmo um movimento.
Lightness Races in Orbit
70

Você deve retornar por valor.

O padrão possui uma característica específica para melhorar a eficiência do retorno por valor. É chamado de "elisão de cópia" e, mais especificamente, neste caso, a "otimização do valor de retorno nomeado (NRVO)".

Os compiladores não precisam implementá-lo, mas, novamente, os compiladores não precisam implementar o inlining de funções (ou realizar qualquer otimização). Mas o desempenho das bibliotecas padrão pode ser muito pobre se os compiladores não otimizam, e todos os compiladores sérios implementam inlining e NRVO (e outras otimizações).

Quando o NRVO for aplicado, não haverá cópia no seguinte código:

std::vector<int> f() {
    std::vector<int> result;
    ... populate the vector ...
    return result;
}

std::vector<int> myvec = f();

Mas o usuário pode querer fazer isso:

std::vector<int> myvec;
... some time later ...
myvec = f();

A elisão de cópia não impede uma cópia aqui porque é uma atribuição em vez de uma inicialização. No entanto, você ainda deve retornar por valor. Em C ++ 11, a atribuição é otimizada por algo diferente, chamado "mover semântica". Em C ++ 03, o código acima causa uma cópia e, embora em teoria um otimizador possa evitá-lo, na prática é muito difícil. Então myvec = f(), em vez de , em C ++ 03, você deve escrever isto:

std::vector<int> myvec;
... some time later ...
f().swap(myvec);

Existe outra opção, que é oferecer uma interface mais flexível ao usuário:

template <typename OutputIterator> void f(OutputIterator it) {
    ... write elements to the iterator like this ...
    *it++ = 0;
    *it++ = 1;
}

Você também pode oferecer suporte à interface baseada em vetor existente além disso:

std::vector<int> f() {
    std::vector<int> result;
    f(std::back_inserter(result));
    return result;
}

Isso pode ser menos eficiente do que seu código existente, se seu código existente usar reserve()de uma forma mais complexa do que apenas uma quantia fixa inicial. Mas se o seu código existente basicamente chamar push_backo vetor repetidamente, esse código baseado em modelo deve ser tão bom.

Steve Jessop
fonte
Votei positivamente na resposta realmente melhor e detalhada. No entanto, em sua variante swap () ( para C ++ 03 sem NRVO ) você ainda terá uma cópia do construtor de cópia feita dentro de f (): do resultado variável para um objeto temporário oculto que será finalmente trocado para myvec .
JenyaKh
@JenyaKh: claro, esse é um problema de qualidade de implementação. O padrão não exigia que as implementações do C ++ 03 implementassem o NRVO, assim como não exigia o inlining de função. A diferença da função inlining é que inlining não altera a semântica ou seu programa, enquanto o NRVO o faz. O código portátil deve funcionar com ou sem NRVO. O código otimizado para uma implementação específica (e sinalizadores de compilador específicos) pode buscar garantias em relação ao NRVO na própria documentação da implementação.
Steve Jessop
3

É hora de postar uma resposta sobre RVO , eu também ...

Se você retornar um objeto por valor, o compilador geralmente otimiza isso para que não seja construído duas vezes, uma vez que é supérfluo construí-lo na função como temporário e depois copiá-lo. Isso é chamado de otimização do valor de retorno: o objeto criado será movido em vez de ser copiado.


fonte
1

Um idioma comum pré-C ++ 11 é passar uma referência ao objeto que está sendo preenchido.

Então, não há cópia do vetor.

void f( std::vector & result )
{
  /*
    Insert elements into result
  */
} 
Drew Dormann
fonte
3
Isso não é mais uma expressão idiomática em C ++ 11.
Nawaz,
1
@Nawaz eu concordo. Não tenho certeza de quais são as melhores práticas agora no SO em relação a perguntas sobre C ++, mas não especificamente C ++ 11. Eu suspeito que deveria estar inclinado a dar respostas em C ++ 11 para um aluno, respostas em C ++ 03 para alguém que está mergulhado na cintura no código de produção. Você tem uma opinião?
Drew Dormann
7
Na verdade, após o lançamento do C ++ 11 (que já tem 19 meses), considero todas as perguntas como C ++ 11, a menos que seja explicitamente declarado como C ++ 03.
Nawaz
1

Se o compilador oferecer suporte a Otimização de valor de retorno nomeado ( http://msdn.microsoft.com/en-us/library/ms364057(v=vs.80).aspx ), você poderá retornar diretamente o vetor, desde que não haja:

  1. Caminhos diferentes retornando objetos com nomes diferentes
  2. Vários caminhos de retorno (mesmo se o mesmo objeto nomeado for retornado em todos os caminhos) com estados EH introduzidos.
  3. O objeto nomeado retornado é referenciado em um bloco asm embutido.

NRVO otimiza o construtor de cópia redundante e chamadas de destruidor e, portanto, melhora o desempenho geral.

Não deve haver nenhuma diferença real em seu exemplo.

taocp
fonte
0
vector<string> getseq(char * db_file)

E se você quiser imprimir em main (), você deve fazer em um loop.

int main() {
     vector<string> str_vec = getseq(argv[1]);
     for(vector<string>::iterator it = str_vec.begin(); it != str_vec.end(); it++) {
         cout << *it << endl;
     }
}
Akash Kandpal
fonte
-2

Por melhor que seja "retorno por valor", é o tipo de código que pode levar a um erro. Considere o seguinte programa:

    #include <string>
    #include <vector>
    #include <iostream>
    using namespace std;
    static std::vector<std::string> strings;
    std::vector<std::string> vecFunc(void) { return strings; };
    int main(int argc, char * argv[]){
      // set up the vector of strings to hold however
      // many strings the user provides on the command line
      for(int idx=1; (idx<argc); ++idx){
         strings.push_back(argv[idx]);
      }

      // now, iterate the strings and print them using the vector function
      // as accessor
      for(std::vector<std::string>::interator idx=vecFunc().begin(); (idx!=vecFunc().end()); ++idx){
         cout << "Addr: " << idx->c_str() << std::endl;
         cout << "Val:  " << *idx << std::endl;
      }
    return 0;
    };
  • P: O que acontecerá quando o acima for executado? R: Um coredump.
  • P: Por que o compilador não detectou o erro? R: Porque o programa é sintaticamente, embora não semanticamente, correto.
  • P: O que acontece se você modificar vecFunc () para retornar uma referência? R: O programa é executado até a conclusão e produz o resultado esperado.
  • P: Qual é a diferença? R: O compilador não precisa criar e gerenciar objetos anônimos. O programador instruiu o compilador a usar exatamente um objeto para o iterador e para a determinação do ponto de extremidade, em vez de dois objetos diferentes, como faz o exemplo quebrado.

O programa errôneo acima não indicará erros, mesmo se alguém usar as opções de relatórios GNU g ++ -Wall -Wextra -Weffc ++

Se você deve produzir um valor, o seguinte funcionaria no lugar de chamar vecFunc () duas vezes:

   std::vector<std::string> lclvec(vecFunc());
   for(std::vector<std::string>::iterator idx=lclvec.begin(); (idx!=lclvec.end()); ++idx)...

O acima também não produz objetos anônimos durante a iteração do loop, mas requer uma possível operação de cópia (que, como alguns observam, pode ser otimizada em algumas circunstâncias. Mas o método de referência garante que nenhuma cópia será produzida. Acreditando que o compilador será executar RVO não substitui a tentativa de construir o código mais eficiente possível. Se você pode questionar a necessidade de o compilador fazer RVO, você está à frente do jogo.

dragão unclesmrgol
fonte
3
Este é mais um exemplo do que pode dar errado se um usuário não estiver familiarizado com C ++ em geral. Alguém familiarizado com linguagens baseadas em objetos, como .net ou javascript, provavelmente presumiria que o vetor string é sempre passado como um ponteiro e, portanto, em seu exemplo, sempre apontaria para o mesmo objeto. vecfunc (). begin () e vecfunc (). end () não corresponderão necessariamente em seu exemplo, pois devem ser cópias do vetor string.
Medran,
-2
   vector<string> func1() const
   {
      vector<string> parts;
      return vector<string>(parts.begin(),parts.end()) ;
   } 
Amruth A
fonte