Assembly Language for Beginners

3.18. C++

element 0: 1

element 1: 2

_Myfirst=0x8257028, _Mylast=0x8257034, _Myend=0x8257038

size=3, capacity=4

element 0: 1

element 1: 2

element 2: 3

_Myfirst=0x8257028, _Mylast=0x8257038, _Myend=0x8257038

size=4, capacity=4

element 0: 1

element 1: 2

element 2: 3

element 3: 4

_Myfirst=0x8257040, _Mylast=0x8257050, _Myend=0x8257058

size=4, capacity=6

element 0: 1

element 1: 2

element 2: 3

element 3: 4

_Myfirst=0x8257040, _Mylast=0x8257054, _Myend=0x8257058

size=5, capacity=6

element 0: 1

element 1: 2

element 2: 3

element 3: 4

element 4: 5

_Myfirst=0x8257040, _Mylast=0x8257058, _Myend=0x8257058

size=6, capacity=6

element 0: 1

element 1: 2

element 2: 3

element 3: 4

element 4: 5

element 5: 6

6

0

We can spot that the buffer size grows in a different way that in MSVC.

Simple experimentation shows that in MSVC’s implementation the buffer grows by ~50% each time it

needs to be enlarged, while GCC’s code enlarges it by 100% each time, i.e., doubles it.

std::map and std::set

The binary tree is another fundamental data structure.

As its name states, this is a tree where each node has at most 2 links to other nodes. Each node has key

and/or value:std::setprovides only key at each node,std::mapprovides both key and value at each

node.

Binary trees are usually the structure used in the implementation of “dictionaries” of key-values (AKA
“associative arrays”).

There are at least three important properties that a binary trees has:

• All keys are always stored in sorted form.


• Keys of any types can be stored easily. Binary tree algorithms are unaware of the key’s type, only a
  key comparison function is required.


• Finding a specific key is relatively fast in comparison with lists and arrays.

Here is a very simple example: let’s store these numbers in a binary tree: 0, 1, 2, 3, 5, 6, 9, 10, 11, 12,

20, 99, 100, 101, 107, 1001, 1010.