1. 二分查找避免死循环
在二分查找中，通常会有两个主要操作：
- 更新左边界 (
left = mid或left = mid + 1)。 - 更新右边界 (
right = mid - 1或right = mid)。
二分查找通过不断缩小 [left, right] 的区间，最终使得 left == right 或者区间变得不可再缩小，从而退出循环。
假设我们使用经典的二分查找方法来计算 mid：
mid = (left + right) >> 1;如果在某些情况下，更新区间时没有正确地缩小区间，就会导致死循环。例如：
- 假设
left = 2，right = 3。 - 计算
mid = (2 + 3) >> 1 = 2。 - 如果条件导致
left = mid，那么left的值仍然是2，而right的值仍然是3。 - 在下一次迭代中，
mid的值仍然是2，区间没有缩小，导致死循环。
为了避免这种情况，通常需要在某些场景下通过 +1 或其他方法来确保区间能够正确缩小。
在这段代码中，mid = (left + right + 1) >> 1 的作用是使 mid 向上取整（更偏向右边界）：
- 当
left + right是奇数时，+1的效果是使得mid更靠近右边界。 - 这可以确保当更新区间时，
left或right都会发生变化，从而避免死循环。
A. C++ STL 容器
STL 中的容器有序列容器和关联容器，容器适配器 (congtainer adapters: stack,queue, priority queue)，位集(bit set)，串包(string package)等等。
- 序列式容器（Sequence containers），每个元素都有固定位置——取决于插入时机和地点，和元素值无关，vector、deque、list。
- Vector：将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时。
- Deque：是 double-ended queue 的缩写，可以随机存取元素（用索引直接存取），数织头部和尾部添加或移除元素都非常快速，但是在中部或头部安插元素比较费时。
- List：双向链表，不提供随机存取（按顺序走到需存取的元素，O（n）），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针。
- 关联式容器（Associated containers），元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap等。
- Set/Multiset：内部的元素依据其值自动排序，Set内的相同数值的元素只能出现一次，Mulisets内可包含多个数值相同的元素，内部由二叉树实现，便于查找。
- Map/Multimap：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现，便于查找。
容器类自动申请和释放内存，无需new和delete操作。
A.1. std::string（严格意义非容器但类似）
容量管理
size_t size() const noexcept：返回字符串长度。size_t length() const noexcept：返回字符串长度（等价于size()）。size_t max_size() const noexcept：返回字符串的最大大小。void resize(size_t n)：调整字符串大小。void resize(size_t n, char c)：调整大小并填充字符c。size_t capacity() const noexcept：返回当前分配的容量。void reserve(size_t new_cap = 0)：调整容量大小。void shrink_to_fit()：释放多余的容量。bool empty() const noexcept：检查字符串是否为空。
访问操作
char& front()：返回第一个字符（可修改）。const char& front() const：返回第一个字符（只读）。char& back()：返回最后一个字符（可修改）。const char& back() const：返回最后一个字符（只读）。const char* c_str() const noexcept：返回 C 字符串格式的内容。const char* data() const noexcept：返回数据指针（不可修改）。char* data() noexcept：返回数据指针（可修改，从 C++17 开始）。std::string substr(size_t pos = 0, size_t n = npos) const：提取子字符串。
修改操作
void clear() noexcept：清空字符串。std::string& insert(size_t pos, const std::string& str)：插入字符串。std::string& insert(size_t pos, const char* s)：插入 C 字符串。std::string& insert(size_t pos, size_t n, char c)：插入n个字符c。std::string& erase(size_t pos = 0, size_t n = npos)：删除子字符串。std::string& replace(size_t pos, size_t len, const std::string& str)：替换子字符串。void push_back(char c)：在字符串末尾添加字符。void pop_back()：移除字符串末尾的字符。void swap(std::string& str) noexcept：交换两个字符串内容。
查找操作
size_t find(const std::string& str, size_t pos = 0) const noexcept：查找子字符串。size_t find(const char* s, size_t pos = 0) const：查找 C 字符串。size_t find(char c, size_t pos = 0) const noexcept：查找字符。size_t rfind(const std::string& str, size_t pos = npos) const noexcept：从右查找子字符串。size_t find_first_of(const std::string& str, size_t pos = 0) const noexcept：查找第一个匹配的字符。size_t find_last_of(const std::string& str, size_t pos = npos) const noexcept：查找最后一个匹配的字符。size_t find_first_not_of(const std::string& str, size_t pos = 0) const noexcept：查找第一个不匹配的字符。size_t find_last_not_of(const std::string& str, size_t pos = npos) const noexcept：查找最后一个不匹配的字符。
比较操作
int compare(const std::string& str) const noexcept：比较两个字符串。int compare(size_t pos, size_t len, const std::string& str) const：比较子字符串。
运算符重载
std::string& operator=(const std::string& str)：拷贝赋值运算符。std::string& operator=(std::string&& str) noexcept：移动赋值运算符。std::string& operator=(const char* s)：从 C 字符串赋值。std::string& operator=(char c)：赋值单个字符。std::string& operator=(std::initializer_list<char> ilist)：从初始化列表赋值。char& operator[](size_t pos)：获取指定位置的字符（可修改）。const char& operator[](size_t pos) const：获取指定位置的字符（只读）。char& at(size_t pos)：获取指定位置的字符（带边界检查，可修改）。const char& at(size_t pos) const：获取指定位置的字符（带边界检查，只读）。std::string& operator+=(const std::string& str)：拼接字符串。std::string& operator+=(const char* s)：拼接 C 字符串。std::string& operator+=(char c)：拼接单个字符。bool operator==(const std::string& lhs, const std::string& rhs)：比较相等。bool operator!=(const std::string& lhs, const std::string& rhs)：比较不相等。bool operator<(const std::string& lhs, const std::string& rhs)：小于比较。bool operator>(const std::string& lhs, const std::string& rhs)：大于比较。bool operator<=(const std::string& lhs, const std::string& rhs)：小于等于比较。bool operator>=(const std::string& lhs, const std::string& rhs)：大于等于比较。std::string operator+(const std::string& lhs, const std::string& rhs)：拼接两个字符串。std::string operator+(const std::string& lhs, const char* rhs)：拼接字符串和 C 字符串。std::string operator+(const char* lhs, const std::string& rhs)：拼接 C 字符串和字符串。std::string operator+(const std::string& lhs, char rhs)：拼接字符串和单个字符。std::ostream& operator<<(std::ostream& os, const std::string& str)：输出流支持。std::istream& operator>>(std::istream& is, std::string& str)：输入流支持。
构造函数
std::string()：默认构造函数，创建一个空字符串。std::string(const std::string& str)：拷贝构造函数。std::string(std::string&& str) noexcept：移动构造函数。std::string(const char* s)：从 C 字符串构造。std::string(const char* s, size_t n)：从 C 字符数组的前n个字符构造。std::string(size_t n, char c)：构造一个包含n个字符c的字符串。std::string(std::initializer_list<char> ilist)：从初始化列表构造。