Six Layouts, Two Kinds of Size

Alice has the same library records in six boxes. Each box reports the same count. Yet the boxes occupy different space and behave differently when another record arrives. Maria asks why identical values need different arrangements.

Objects and owned storage

An object is one value with a type and a lifetime. A container object often manages other objects elsewhere. Its owned storage is the memory it must eventually release. The two sizes answer different questions. sizeof measures the object itself. It does not follow pointers and total their targets.

A vector containing many records can have the same object size as an empty vector. Its separate element block grows instead. An empty deque may already own allocated blocks. A node container adds separate allocations as values arrive. Never multiply sizeof(container) by its element count to estimate total ownership.

An implementation detail is a library choice that another library can change. A guarantee is a behaviour the C++ standard requires. This lesson draws GCC 12 libstdc++ layouts to connect Modules 2 through 10. Their detailed growth experiments remain in those modules. Here the question is what the layouts share.

Read the layouts together

Vector keeps three boundaries: the beginning, the end of live elements, and the end of allocated room. The first gap gives size; the second boundary limits growth without reallocation. These are three pointers in this GCC representation. The standard requires contiguous elements, but does not prescribe those exact fields.

String adds a different tradeoff. A small local buffer can hold short text inside the string object. Longer text needs separate storage. Module 3 examined that small-string choice. Compare it with vector: a small object may avoid an allocation, while a small vector still manages an outside element block.

Deque keeps a map of pointers to blocks. Here map means an indexing array, not std::map. Several elements fit inside each block. Indexing selects a block, then a slot. Growing at an end can replace the map without relocating old elements. That difference will explain its unusual iterator rule.

List distributes values among linked nodes. A node carries a value and links to neighbouring nodes. Its object keeps a boundary structure and bookkeeping. Appending adds a node rather than stretching one common element block. Finding a numbered position still requires walking links. Stable addresses do not provide fast indexing.

Ordered set and map use tree nodes in this implementation. Each node has parent, left, and right links, plus a colour. Rebalancing changes links while values remain in their nodes. This supports stable element handles and ordered search together. The standard requires the operation bounds, rather than this particular coloured tree.

Unordered containers combine a bucket array with linked nodes. A hash chooses a bucket. GCC connects nodes through a shared chain; bucket entries locate chain boundaries. Module 10 opened that detail. Rehash rebuilds bucket organization while keeping element objects alive. It changes traversal even when a saved element address stays usable.

These layouts exchange three resources: adjacent space, links, and spare room. Vector pays spare capacity to grow in batches. List pays links to keep nodes independent. A hash table pays both nodes and buckets. String sometimes trades a larger object for fewer small allocations. No single sizeof result prices all these choices.

A record may itself own more memory. A vector of strings stores adjacent string objects, but their long character buffers can live elsewhere. Contiguity applies to the element objects, not recursively to everything they own. Budget both levels before drawing a conclusion about a text-heavy workload.

An allocation request also differs from resident memory. The memory manager may round requests, keep bookkeeping, or retain released blocks. sizeof does not measure those effects. The node measurements here describe type layouts. They cannot establish a complete process memory total by themselves.

Compare what happens when one value arrives. Vector may use spare room or move its current block. Deque may add a block. List adds a node. A tree also repairs ordering links. Hash insertion may rebuild bucket organization. These different updates help explain why similar reads have different handle rules.

Module 2 already proved the ordinary vector growth accounting. Module 4 already inspected deque block arithmetic. Here neither proof needs repeating. Put their conclusions together: random access can be constant in two layouts, while their address stability and extra indirections differ. Equal complexity does not imply identical representation.

For an array, the fixed element count belongs to its type. There is no growable outside element block to steal during a move. A container adaptor adds another layer: its storage follows the underlying container. Ask which layer owns elements before interpreting an adaptor's sizeof result.

Finally, separate a design sketch from evidence. A sketch explains relationships between fields and owned values. The program measures actual types on this compiler. Public API guarantees determine which operations your application may rely on. Use all three together rather than making the sketch do every job.

sizeof(vector<int>)  // The manager object, not its element block.
sizeof(int)          // One payload object.
v.capacity()         // Element slots owned by this vector.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
struct Boundaries { int *start,*finish,*limit; };
    vector<int> v(100); string shortText="book",longText(100,'x');
    cout<<"vector-object "<<sizeof(v)<<'\n';
    cout<<"three-pointer-model "<<sizeof(Boundaries)<<'\n';
    cout<<"string-object "<<sizeof(shortText)<<'\n';
    cout<<"long-string-object "<<sizeof(longText)<<'\n';
    cout<<"live-vector-payload "<<v.size()*sizeof(int)<<'\n';
}

vector-object 24
three-pointer-model 24
string-object 32
long-string-object 32
live-vector-payload 400

#include <deque>
#include <iostream>
#include <list>
using namespace std;
int main() {
deque<int> blocks; list<int> nodes;
    cout<<"deque-object "<<sizeof(blocks)<<'\n';
    cout<<"list-object "<<sizeof(nodes)<<'\n';
    cout<<"list-node-gcc-only "<<sizeof(std::_List_node<int>)<<'\n';
    cout<<"deque-iterator "<<sizeof(deque<int>::iterator)<<'\n';
    cout<<"int-payload "<<sizeof(int)<<'\n';
}

deque-object 80
list-object 24
list-node-gcc-only 24
deque-iterator 32
int-payload 4

#include <iostream>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;
int main() {
cout<<"set-object "<<sizeof(set<int>)<<'\n';
    cout<<"map-object "<<sizeof(map<int,int>)<<'\n';
    cout<<"tree-node-gcc-only "<<sizeof(std::_Rb_tree_node<int>)<<'\n';
    cout<<"unordered-object "<<sizeof(unordered_set<int>)<<'\n';
    cout<<"hash-node-gcc-only "<<sizeof(std::__detail::_Hash_node<int,false>)<<'\n';
}

set-object 48
map-object 48
tree-node-gcc-only 40
unordered-object 56
hash-node-gcc-only 16

The arrows show relationships, not byte offsets or physical addresses. In the deque picture, each map entry points down to its corresponding block. In the tree picture, child links branch from a node. In the hash picture, buckets enter runs of the shared node chain. Read each picture alongside its measured program.

Each frame reads capacity from the vector itself. The moved field counts old integer elements relocated when storage changes. It does not count processor instructions. These frames describe this library run. They do not establish a growth factor that your code may assume elsewhere.

#include <list>
using namespace std;
int main() {
list<int> a{2,5}; auto p=a.data(); (void)p;
}

#include <vector>
using namespace std;
int main() {
vector<bool> flags(3); bool& first=flags[0]; (void)first;
}

4 3 0
2581

32

#include <iostream>
#include <string>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
int n,q; long long seed; string digits; cin>>n>>q>>seed>>digits;
    // Follow the inspection schedule and accumulate its weighted digits.
}

3 8 12

#include <iostream>
using namespace std;
int main() {
long long s,c,b; cin>>s>>c>>b;
    // Print the two payload budgets.
}

36 96

5 8 4 8

#include <iostream>
using namespace std;
int main() {
long long n,c,b,p; cin>>n>>c>>b>>p;
    // Compare the two stated memory models.
}

VECTOR

Next, compare the operation guarantees and the expensive calls hidden inside averages.