CODEWITHSUNDEEP
c++
alekscooper
alekscooper

Reputation: 831

Why does a vector have the same size when I add elements to it?

I have this C++ structure:

typedef unsigned long T;

struct Node {
    T index;
    T length;
    Node(): index(0), length(0), next(0) {}
    Node(const T &ind, const T &len): index(ind), length(len), next(0) {}
    vector<Node*> next;
};

I'm trying to find out how much memory next will take. I know that it will have five elements maximum. So here's what I do:

int main(int argc, const char * argv[]) {

    Node n;
    Node* x = new Node(3, 4);

    cout << "An empty vector of pointers: " << sizeof(n.next) << " bytes\n";

    // Add five elements
    for(int i = 0; i < 5; i++)
        n.next.push_back(x);

    cout<< "New size of the vector of pointers: " << n.next.size() << " elements\n";
    cout<< "New size of the vector of pointers: " << sizeof(n.next)  << " bytes\n";

    return 0;
}

And here's my output:

An empty vector of pointers: 24 bytes
New size of the vector of pointers: 5 elements
New size of the vector of pointers: 24 bytes

My question: how is that possible that an empty vector takes 24 bytes, but the same vector with 5 elements in it still takes 24 bytes? Shouldn't it take more memory? Like *24 + 5 * sizeof(Node*)*?

Upvotes: 1

Views: 618

Answers (4)

Aganju
Aganju

Reputation: 6395

The vector implementation that comes as a standard is typically optimized to start its life with more than the necessary amount of space. In simple terms, the implementation plans space for a vector on - for example - 8 objects even though you ask for less, and only starts allocating more memory once you get over this number.

This wastes some small amount of memory, if you never use those elements, but removes the performance overhead of reallocating memory for each element you add. The exact amount is implementation dependent, and some might not do it that way, but it is a typical optimization.

If you want to measure the space an element uses up, you need to go for larger amounts; for example, put 100 objects in and check, and then put 200 in and check. For small amounts, you will see a constant size, until you hit the threshold.

Upvotes: 1

molbdnilo
molbdnilo

Reputation: 66371

All objects of a given type are the same size, and sizeof(n.next) is equivalent to sizeof(vector<Node*>).

A vector instance doesn't contain the elements, it only points to them, so the instance itself is always the same size.

It works exactly like this:

class A
{
public:
    A(int n) : p(new char[n]), s(n) {}
    int size() const { return s; }
private:
    char* p;
    int s;
};

int main()
{
    A a(1);
    A b(100);
    // These all print the same thing:
    std::cout << sizeof(a);
    std::cout << sizeof(b);
    std::cout << sizeof(A);
    // These are different:
    std::cout << a.size();  // Prints 1
    std::cout << b.size();  // Prints 100
}

If you want to find out how much space your vector occupies in total, you need to calculate that yourself.

Upvotes: 2

peppe
peppe

Reputation: 22724

You want n.next.size().

sizeof is entirely a compile-time operation, since it just looks at the type to figure out how many bytes you need for storing one instance of it. sizeof(n.next) tells you how many bytes it takes to hold n.next. Since it's a vector, it's likely to be implemented using 3 pointers (8 bytes each) -- one pointing at the start of the allocated array, one pointing at the end of the data, one pointing at the end of the allocated array.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

Vector is a dynamic structure that has a fixed "footprint", which usually contains pointers to dynamically-allocated data.

n.next.size() returns the size of dynamically allocated data. sizeof(n.next) returns the size of the fixed footprint.

Upvotes: 4

Related Questions