In which situations should I dynamically allocate a vector to C++?

Question

I’m fiddling with a code from a framework for my work. In one of the functions, it dynamically allocates a std::vector, makes a copy of each node the object has and returns it to the user:

std::vector<Node> *Tree::getAllNodes() {
    std::vector<Node> *n, *aux;
    n = new vector<Node>();
    mut.lock();
    for (int i = 0; i < subnodes.size(); ++i) {
        aux = subnodes[i]->GetNodes();
        n->insert(n->end(), aux->begin(), aux->end());
    }
    mut.unlock();
    return n;
}

That is, it is up to the user to liquidate this memory after.

But, I do not know if it is really necessary to allocate this memory dynamically, since the vector take care of it for us, underneath the covers, right?

One of the reasons I find is that it is cheaper to return only the pointer than the vector copy, when we have a lot of data. If we didn’t allocate it dynamically, we would have to return a copy and, because it’s a lot of data, it would cost more.

Questions:

1. This is really a case that we should allocate the vector dynamically?
2. In other cases, when we have few data and/or few calls to this function, is it unnecessary to make this dynamic allocation? After all, memory management becomes simpler.

Answer 1

I can’t see any real advantage in allocating one std::vector dynamically. But one should be careful when returning a vector as a result of a function. Even though it is small (typically 12 bytes on 32-bit systems) its copy builder is slow.

• If possible, allow the compiler to apply the return optimizations. In them the object to be returned is built directly into its destination variable after the function call. There are two possible modalities (12.8/31):

  • NRVO (Named Return Value Optimization): When you create a variable within the function whose type is the return type of the function and at all return points, you return this variable. Example:

    // Otimização de valor nomeado:
    //  Todos os returns devem retornar a mesma variável local.
    std::vector<int> func_nrvo() {
        std::vector<int> result;
        // execute algo aqui e adicione elementos ao vetor
        return result;
    }
    
    std::vector<int> result = func_nrvo();
    

  • RVO (Return Value Optimization): When you return an object built on the return point itself, that is: a temporary one (which is exactly the type of the function). Example:

    // Otimização de valor não nomeado:
    //  Todos os returns devem ser um objeto temporário do tipo de retorno.
    std::vector<int> func_rvo() {
        return std::vector<int>(5, 0);
    }
    
    std::vector<int> result = func_rvo();
    

• If it is not possible to apply these optimizations (I suggest rewriting so that the function looks like in one of these examples), then there are two options: move or copy the object, being the first rather light and the second very costly. Unfortunately there is no concept of move in C++03 and if you cannot use C++11 you will have to use other means to avoid copying, such as using a reference argument to return:

  void func_ref(std::vector<int>& vec) {
      vec.clear();
      vec.push_back(1);
  }
  
  std::vector<int> vec;
  func_ref(vec);
  

• If you use a compiler that supports C++11:

  The vector in this case has a constructor that can move the object. So returning the vector by a function is quite light and you don’t have to worry. In cases where value return optimization does not apply, but if you return a local variable, the result will be moved automatically. But you can force the action to move using the std::move if the situation is different.

  std::vector<int> func1() {
      return std::vector<int>({1, 2, 3, 4, 5});
  }
  
  std::vector<int> func2() {
      std::vector<int> a, b;
      if (rand() % 2)
          return a;
      else
          return b;
  
      // Otimização não se aplica. Estamos retornando variáveis diferentes.
      // Mas ainda estamos retornando variáveis, mover é implícito.
  }
  
  std::vector<int> func3() {
      std::vector<int> a, b;
      return (rand() % 2) ? std::move(a) ? std::move(b);
      // Otimização não se aplica. Estamos retornando variáveis diferentes.
      // Mas note que não estamos retornando variáveis, e sim uma estrutura
      // mais complexa (a condicional ternária). Nesse caso precisa forçar o move.
  }
  
  std::vector<int> vec1 = func1(); // Resultado construído diretamente em vec1
  std::vector<int> vec2 = func2(); // Resultado movido para vec2
  std::vector<int> vec3 = func3(); // Resultado movido para vec3
  

Note:

In the code of your function I see that you use a mutex. Note that the function call insert vector may fail and cast the exception std::bad_alloc in case of memory failure. If this happens your function will be terminated without releasing the mutex. A deadlock waiting to appear!

The ideal is to use a class whose constructor stops the mutex and destructor to Strave, as the std::lock_guard. So even in the case of an exception the mutex will be released because the destructor of the local variables is always called.

In case of doubt...

The rules that govern exactly what type of constructor to call, when and which optimizations can be made in each case are quite complex and analyzing a code based only on its "instincts" can be risky. When faced with situations like this an attitude is to trust your compiler to tell you what is going on. Instead of a vector, use a "guinea pig" class to see through the code. Example:

struct Cobaia {
    Cobaia() {cout << "  Cobaia()" << endl;}
    ~Cobaia() {cout << "  ~Cobaia()" << endl;}
    Cobaia(const Cobaia&) {cout << "  Cobaia(const Cobaia&)" << endl;}
    Cobaia(Cobaia&&) {cout << "  Cobaia(Cobaia&&)" << endl;} // apenas C++11
};

volatile bool cond = true; // volatile para não otimizar

Cobaia func1() { Cobaia r; return r; }
Cobaia func2() { return Cobaia(); }
Cobaia func3() { Cobaia a, b; if (cond) return a; else return b; }
Cobaia func4() { Cobaia a, b; return cond ? a : b; }
Cobaia func5() { Cobaia a, b; return std::move(cond ? a : b); } // apenas C++11

int main() {
    cout << "func1:" << endl; Cobaia c1 = func1();
    cout << "func2:" << endl; Cobaia c2 = func2();
    cout << "func3:" << endl; Cobaia c3 = func3();
    cout << "func4:" << endl; Cobaia c4 = func4();
    cout << "func5:" << endl; Cobaia c5 = func5(); // apenas C++11
    cout << "fim:" << endl;
}

Here is the result of this program (compiled with GCC 4.8.1 in C++11 mode, my comments):

func1:
  Cobaia() // Otimização acontecendo. Tudo acontece como se 'c1' estivesse dentro de func1
func2:
  Cobaia() // Otimização acontecendo. Tudo acontece como se 'c2' estivesse dentro de func2
func3:
  Cobaia() // Construção do local a
  Cobaia() // Construção do local b
  Cobaia(Cobaia&&) // Mover a ou b para c3
  ~Cobaia() // Construção do local b
  ~Cobaia() // Construção do local a
func4:
  Cobaia() // Construção do local a
  Cobaia() // Construção do local b
  Cobaia(const Cobaia&) // Copiar a ou b para c4
  ~Cobaia() // Construção do local b
  ~Cobaia() // Construção do local a
func5:
  Cobaia() // Construção do local a
  Cobaia() // Construção do local b
  Cobaia(Cobaia&&) // Mover a ou b para c5
  ~Cobaia() // Construção do local b
  ~Cobaia() // Construção do local a
fim:
  ~Cobaia() // Destruir c5
  ~Cobaia() // Destruir c4
  ~Cobaia() // Destruir c3
  ~Cobaia() // Destruir c2
  ~Cobaia() // Destruir c1

Note the difference between func3, func4 and func5. It is a clear example of how obscure these rules can be. In func3 return is a local variable, so it has a fixed address from where the data can be moved. In the case of func4 the return expression is a temporary one, so it is expected that its value will be destroyed just before it effectively returns from the function. That way the compiler needs first copy the result for the return address before continuing. In func5 use the std::move to convert the expression into a Cobaia&& which may be moved.

If you run the same code in C++03 you will see that the last ones make copies since there is no concept of moving an object.

For extra fun doses, add the flag -fno-elide-constructors in GCC. It turns off all these optimizations and you can see each and every one of the copies happening. One exercise: determine the reason for each one.

Answer 2

In certain cases it may be advantageous/necessary to dynamically create the vector:

Situation 1: You have a multithreaded process and you have a heap of your own for each thread (for performance reasons), in this case you create the vector in the respective thread heap.

Situation 2: You use a custom allocator if it’s not Static you can’t possibly declare something like:

vector<unsigned int, my_allocator<unsigned int>> vVector;

because your my_allocator does not yet "exist" and when declaring the vector it automatically needs an allocator to do its initialization.