Memory allocation and working of std::map in c++
c++, dictionary
Solution
An `std::map` is typically a self balancing binary search tree1. This is a node-based data structure, quite different to an array. Typically, the data are allocated dynamically. What you have here:
map <int, int> A[100005];
is an array of maps with automatic storage, so a plain array of 100005 binary search trees that gets destroyed when exiting the scope in which it is declared.
So this
A[1][2]=1;
is adding a key-value pair (2,1) to the second map in the array.
The C++ standard does not specify how exactly an `std::map` should be implemented, but places conditions on complexity of various operations, and iterator validity, which mean that it really is implemented as a self-balancing BST, typically a red-black tree.
Problem
I was reading about the map c++ dictionary implementation. I read a code somewhere on the net which had the following lines. ``` map <int, int> A[100005]; A[1][2]=1; ``` please can you explain how is memory allocated. Is it in the same way as a 2-D array or it increases dynamically while we are inserting. And how does the insertion in the map takes place given the second line of code.