Data Structures
Arrays
1  /* Builtin Array (fixed size) */ 
1  /* vector */ 
String
1 

Pair
1 

Stack
1 

Queue
1 

From now on, the declaration and capacity part will be omitted.
Hash Table
1 

1 

Algorithms
Well, algorithm is not a separated concept from data structure, and some algorithms have been covered in the above section. Here I’ll just list some more.
Sort
For sorting algorithms, refer to my GitHub post. The post currently includes insertion sort, merge sort and quick sort.
1 

Binary Search
Given a sorted array, binary search could find the target with a time complexity of . Following is the basic template:
1  int binarySearch(vector<int>& nums, int target) { 
The pointer left
and right
are used to control the search area.
If the middle value equals our target, then we just make it. If the middle value is less than the target, then it means that we should search the larger part. We need to move the left pointer to right. Otherwise, we need to move the right pointer to left if the middle value is greater.
Note that the calculation of mid is a bit counterintuitive. The purpose is to prevent the overflow caused by adding. Suppose that left is 1 and right is INT_MAX, then the adding will cause overflow and lead to errors. Therefore, it’s advised to use left + (right  left) / 2
instead.