Reverse Engineering for Beginners

CHAPTER 51. C++ CHAPTER 51. C++

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.

51.4.4 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.

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.

10

1

0 5

3

2

6

9

100

20

12

11

99

107

101 1001

1010

All keys that are smaller than the node key’s value are stored on the left side. All keys that are bigger than the node key’s
value are stored on the right side.