Why is inserting into a vector in C++ efficient?

Question

From https://learn.microsoft.com/en-us/cpp/cpp/value-types-modern-cpp?view=vs-2019, we have:

#include <set>
#include <vector>
#include <string>
using namespace std;

//...
set<widget> LoadHugeData() {
    set<widget> ret;
    // ... load data from disk and populate ret
    return ret;
}
//...
widgets = LoadHugeData();   // efficient, no deep copy

vector<string> v = IfIHadAMillionStrings();
v.insert( begin(v)+v.size()/2, "scott" );   // efficient, no deep copy-shuffle
v.insert( begin(v)+v.size()/2, "Andrei" );  // (just 1M ptr/len assignments)
//...
HugeMatrix operator+(const HugeMatrix& , const HugeMatrix& );
HugeMatrix operator+(const HugeMatrix& ,       HugeMatrix&&);
HugeMatrix operator+(      HugeMatrix&&, const HugeMatrix& );
HugeMatrix operator+(      HugeMatrix&&,       HugeMatrix&&);
//...
hm5 = hm1+hm2+hm3+hm4+hm5;   // efficient, no extra copies

I think I can see how the set is efficient, set stores its data on the heap so I assume returning the set creates a copy of the set where each pointer in the underlying array refers to the same memory locations as the set we're copying from. I assume you could make this even faster by using std::move which will not even have to use new pointers pointing to the same memory location, it will use the same pointers.

I can't see how inserting into a vector can be efficient if vectors in C++ are stored continuously. If they're stored contiguously, I would think that you definitely have to do a "copy-shuffle". What am I missing?

Answer 1

I assume returning the set creates a copy of the set where each pointer in the underlying array ...

Your assumption is wrong. A std::set doesn't have an "underlying array". It is generally implemented as a balanced search tree.

where each pointer in the underlying array refers to the same memory locations as the set we're copying from.

A copy of set does not refer to the data of the original set. It will be a deep copy; each element is copied to the new set.

In the example however, your return a local variable, so it will be moved instead of copied. A move is a shallow copy, and the resulting object will indeed to refer to data that was originally owned by the other object.

What is likely to happen however, is that the compiler does optimisation, and makes it so that the locally declared set actually creates the set that is used on the outside of the function. Because of this "magic trick", there is only one set in practice and no copy nor move needs to be made.

I assume you could make this even faster by using std::move

Actually, return std::move(local) is hardly ever faster than return local. Latter will invoke move constructor anyway, but also allows the before mentioned optimisation. std::move prevents that optimisation.

I can't see how inserting into a vector can be efficient if vectors in C++ are stored continuously.

"Efficiency" is subjective and depends a lot on context.

Sure, node based data structures like list and set have very good worst case for insertion - O(1) asymptotic complexity versus O(N) of vector. But often that is not relevant to your program. What is often more relevant is how well the data structure works with the CPU cache. In short, arrays work very well with cache, while linked nodes do not.

Note that vector is implemented with a clever algorithm that allows insertion of N elements into back of the vector to have O(N) asymptotic complexity, which is same as the linked node structures.

So, when you know how many elements the vector will have and can insert the elements in order, then you can simply reserve sufficient space initially and then there will be no need for shuffling.

If they're stored contiguously, I would think that you definitely have to do a "copy-shuffle". What am I missing?

It does have to do a shuffle. But it is more efficient than copy-shuffle, because it is a move-shuffle, and moving a std::string is efficient.