CODEWITHSUNDEEP
c++arraysvectorreferencestl
Abhay Patil
Abhay Patil

Reputation: 399

Memory allocation in C++ STL for dynamic containers

When you declare 2D arrays, they are stored in contiguous memory locations and this is easy as the number of rows is fixed while declaring them.

Whereas when we declare a 2D vector vector<vector<int>> v, how does it work. As the number of rows is not fixed at all. My first guess was the new vector which you push_back into it are randomly allocated but then even that wont work as these vectors of int are randomly accessible.

My first guess is to allocate vectors of int randomly in the memory and store their address in another vector of addresses. eg

vector<vector<int>> vmain;

vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 3};
vector<int> c = {1, 2, 3};

vmain.push_back(a);
vmain.push_back(b);
vmain.push_back(c);

is stored something similar to

vector<&vector<int>> vmain; //vector of pointer to vector

vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 3};
vector<int> c = {1, 2, 3};

vmain.push_back(&a);
vmain.push_back(&b);
vmain.push_back(&c);

Please tell me if this is the correct way.

And also for vector of maps or sets vector<map<int, int>> v1 and vector<set<int>> v2. As size of maps and sets is not fixed.

Upvotes: 2

Views: 687

Answers (1)

eesiraed
eesiraed

Reputation: 4654

The vector object doesn't store the elements. It stores a pointer to a contiguous chunk of memory containing the elements. When you have std::vector<std::vector<int>> the outer vector contains a pointer to a contiguous chunk of memory containing vector objects, each of which have a pointer to a contiguous chunk of memory containing the ints.

std::map and std::set also don't store the elements in the object itself. Each object contains a pointer to a BST containing the elements.

Upvotes: 2

Related Questions