CODEWITHSUNDEEP
c++
python152
python152

Reputation: 1951

on storage class whereabout

Let's say I have a vector which takes a struct point as its type, see snippet below. A function adds two points into it. Since the points here are locally initialized. Is there an issue/concern that the points will not be accessible when the function returns? Is there a copy action happening inside the vector container, if so, where are these data struct actually stored? in heap?

struct point {
    int x;
    int y;
    string name;
};

vector<point> pointvec;

int addpoints() {
    point p1 {2, 3, "point 1"};
    point p2 {4, 4, "point 2"};

    pointvec.push_back(p1);
    pointvec.push_back(p2);

}

Upvotes: 0

Views: 35

Answers (1)

pat
pat

Reputation: 823

vector starts with no memory allocated. During the first push_back, it allocates enough room for that one element and copies the passed point in. During the next push_back, it reallocates enough room for both elements, and moves its copy of the previous element to the new memory then copies the second point. If you were to push_back again, it would allocate enough room for (typically) 4 elements, move its copies, and copy the new one.

There are standardized restrictions (amortized constancy) on the complexity of these operations which require the allocated vector memory to grow proportionally to the vectors current length. The reason it must grow proportionally is because of the moves for existing elements (like the second push_back described above). That means the complexity of a reallocation grows with the length of the vector, and amortized constant insertions would no longer be amortized constant. To counteract that, the reallocation must be proportional to the length. This proportionality is typically 2x the current length, though I don't believe it is required to be.

The memory in your example is allocated on the heap, but if you were to provide a different allocator type for the vector, it could be allocated anywhere an allocator allows.

So, your example is safe, but it is slow, and typically requires 2 allocations on the heap for that simple function. A better solution is to preallocate the necessary memory using the reserve method which only allocates heap memory once.

int addpoints() {
    point p1 {2, 3, "point 1"};
    point p2 {4, 4, "point 2"};

    pointvec.reserve(2);

    pointvec.push_back(p1);
    pointvec.push_back(p2);
}

Upvotes: 2

Related Questions