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

user_5732910 0
Viewed 388

From https://docs.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?

c++
3 Answers

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.

user_20793030

The first assignment from LoadHugeData is efficient because of copy elision or return value optimization, the set is never actually copied.

The insertion in the middle of a vector does indeed require some or all of the existing items to be moved. This is made more efficient because the move semantics don't require any new allocations or copies to be made - the new item will simply take over the internals of the old item, including the pointer to an actual string buffer. No deep copies required.

Mark_Ransom_59870

I think the comment means that the strings are moved instead of deep copied. It's still a linear time operation with respect to the number of strings in the vector, but it won't copy all the characters in the strings (maybe except for SSO). That's what "just 1M ptr/len assignments" means. I guess you could consider that "efficient" when compared to copying every character.

user_92545390
Related