Before we start walking through the STL containers and some other useful data structures, we will briefly discuss some properties of computer memory.
C++ treats memory as a sequence of cells. The size of each cell is one byte, and each cell has an address. Accessing a byte in memory by its address is a constant time operation, O(1), that is independent of the total number of memory cells. On a 32-bit machine, one can theoretically address 232 bytes, that is, around 4 GB, which restricts the amount of memory a process is allowed to use at once. On a 64-bit machine, one can theoretically address 264 bytes, which is so big that there is hardly any risk of running out of addresses.
The following image shows a sequence of memory cells laid out in memory. Each cell contains eight bits. The hexadecimal numbers are the addresses of the memory cells:
