1

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*)*?

alekscooper
  • 795
  • 1
  • 7
  • 19
  • 3
    `int* x = new int[1]; int* y = new int[100]`. Think, why `sizeof(x) == sizeof(y)`, even through they are pointing to different sized arrays? – Revolver_Ocelot Aug 16 '16 at 10:25
  • It's the size of a pointer in both cases? – alekscooper Aug 16 '16 at 10:36
  • If you need to know at least how much memory the vector is using, use `sizeof(n.next) + n.next.capacity() * sizeof(Node*);` if you need to know exactly how much memory the vector has allocated, provide your own allocator to the vector. – evan Aug 16 '16 at 14:29

4 Answers4

4

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
2

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.

molbdnilo
  • 64,751
  • 3
  • 43
  • 82
1

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.

peppe
  • 21,934
  • 4
  • 55
  • 70
  • No, I want to know how many bytes my next will take when it's full, which means when it has five pointers to Node in it. But I don't understand how to compute it. – alekscooper Aug 16 '16 at 10:29
  • @alekscooper If you actually *need* to track memory usage that closely, you're using the wrong programming language. If you just want to know what's going on, see http://stackoverflow.com/questions/910172/track-c-memory-allocations – Andrew Henle Aug 16 '16 at 10:38
1

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.

Aganju
  • 6,295
  • 1
  • 12
  • 23
  • At the end of the day I'd like to know what's more efficient in terms of memory resources: to have as structure with a vector of pointers, although not each instance of the structure will have exactly 5 pointers in its vector; or to have a structure with a fixed-length array of 5 elements, something like Node* next[5]. – alekscooper Aug 16 '16 at 10:46
  • A fixed array of 5 will be more efficient in pure memory byte counting. Always. However, the overhead of using a vector is small and negligent unless you will have many millions of them, and the extra code you will need to handle the things that vector comes with will eat such savings. Also, with an array, you have a lot more chances of errors that vector avoids. So, in a nutshell, vector has maybe 20% memory overhead, but it is still the better choice unless you need a huge amount of them. – Aganju Aug 16 '16 at 10:51