目录
2. string、vector、list是怎么插入数据的？如何扩容的？
unordered_map / unordered_set：（其实还有unordered_multimap/unordered_multiset）
4. 一个类型做 unordered_map / unordered_set 有什么要求？
1. 常见的容器及其常见问题
1.1 序列式容器
对应线性结构，逻辑上是依次存储的，任意位置都能插入，string和vector用的是最多的。string 严格来说虽然不属于STL，但是也比较重要，所以囊括进来做对比。
string：07.string类_stding::length()-CSDN博客
vector：08.vector-CSDN博客
list：09.list-CSDN博客
1.1.1 常见问题：
1. string、vector 和 list 的区别？
用法：
- string是专门用于处理字符串的容器，string后有 \0，string s
- vector是动态数组，数组元素类型任意vector<string>、vector<int>...
- list是双向链表，list<int>
优点：
- string 支持运算符重载（+, +=等），使用直观；专为字符串设计，接口丰富（find, substr等）
- vecto支持随机访问O(1)；尾插、尾删高效
- list 任意位置插入删除高效；没有容量概念，按需分配节点；插入删除不会使迭代器失效(除了被删除元素)
缺点：
- string 某些操作（如插入/删除非末尾字符）效率不高
- vector 非尾部插入/删除效率低O(n)；容量不足时需要重新分配内存并拷贝元素
- list 不支持随机访问（访问元素O(n)），[ ]会从开头遍历到指定位置；内存开销大（每个元素需要额外存储前后指针）
底层实现：
- string 通常实现为动态数组，char* _str，size_t _size，size_t _capacity。
- vector 维护三个指针：起始位置、当前元素末尾、容量末尾：
typedef T* iterator; iterator _start; iterator _finish; iterator _endofstorage; - list 使用双向链表节点结构，每个节点包含数据和前后指针，通常实现为循环链表，有哨兵头节点head
namespace zzy { template<class T> struct list_node//为什么这里写它？ { list_node<T>* _next; list_node<T>* _prev; T _val; explicit list_node(const T& val = T()) :_next(nullptr) ,_prev(nullptr) ,_val(val) {} }; template<class T> class list { typedef list_node<T> Node; public: list() { _head = new Node; _head->_prev = _head; _head->_next = _head; _size = 0; } private: Node* _head; size_t _size; }; }
2. string、vector、list是怎么插入数据的？如何扩容的？
string：
插入有两种，插入字符、字符串，分成push_back和append，同理在插入时要先检查空间扩容，特色的operate+=就根据参数是char或char*，分别调用push_back和append。
void reserve(size_t n)
{
if(n > _capacity)
{
char* tmp = new char[n+1];
memcpy(tmp, _str, _size+1);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
void push_back(char ch)
{
if(_size == _capacity)
{
reserve(_capacity == 0 ? 4: _capacity*2);
}
_str[_size] = ch;
++_size;
_str[_size] = '\0';
}
void append(const char* str)
{
size_t len = strlen(str);
//如果插入后的大小大于容量，二倍的容量不一定有size+len大
if(_size + len > _capacity)
{
reserve(_size+len);
}
memcpy(_str+_size, str, len+1);
_size += len;
}
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string operator+=(const char* str)
{
append(str);
return *this;
}vector：
尾插的话就先判断容量，不够就扩容，新元素放在最后一个位置上，finish++。
如果是insert，也是先判断容量，扩容后重新找到要插入的位置(迭代器失效)，从尾向前搬移元素，新元素放到pos上，finish++。
void push_back(const T& x)
{
if(_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0? 4:capacity*2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
} 如果要扩的容量大于当前的容量，就扩容，注意保留原大小以及逐个拷贝，不能使用memcpy(涉及到内存管理，memcpy只会复制指针值，不会复制指针指向的内容)
void reserve(size_t n)
{
if(n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if(_start)
{
//memcpy(tmp, _start, sizeof(T)*sz);
for (size_t i=0; i<sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}list：
其实就是双向带头循环链表的插入，没有扩容一说。
1.2 关联式容器
关联式容器也是用来存储数据的，与序列式容器不同的是，里面存的是<key，value>结构的键值对，在数据检索时比序列式容器效率更高。
1.2.1 树形结构的关联式容器
map / set：
1. 底层是什么：树形结构的这4种容器的底层都是红黑树。
各自的规则：
set：
- set与map/multimap 不同，map/multimap中存储的是真正的键值对<key， value>，set中只放value，但在底层实际存放的是由<value，value>构成的键值对。
- set按一定次序存储元素，默认按小于来比较，查找某个元素时，时间复杂度为O(logN)。
- set中的元素不允许修改，因为用的都是const迭代器。可以从容器中插入和删除。
map：
- map存储按特定次序（按key比较）由键和值组合而成的元素，为其取别名pair<>
- key也不允许修改，用的是const key
- 支持下标访问符，即在[ ]中放入key，可以找到与key对应的value
- 当key元素不存在时，operator[]用默认的value与key构造键值对然后插入，返回默认value，at()直接抛异常
- map中的元素如果用迭代器去遍历，可以得到一个有序的序列
效率：
set 中通过键访问单个元素时比 unodered_set 慢
map 中通过键值访问单个元素时比 unodered_map 慢
大概实现：
map和set底层使用的都是红黑树，那怎么让map和set共用一颗红黑树的呢？
使用模板，首先需要对红黑树进行改造
template<class K>
class set
{
private:
RBTree<K, K> _t;
};
template<class K, class V>
class map
{
private:
RBTree<K, pair<K, V>> _t;
};我们可以从上面的代码看出，set 和 map 的key位置一样，但是value位置，set用的是K，而map用的是一个pair<K, V>，他们是通过同一棵树搞出来的_t，那么RBTree在这个位置就要用一个模板T。
set用RBTree<K, K>：因为set只存Key，复用RBTree时需要传Value=K。map用RBTree<K, pair<const K, V>>：因为map存键值对，但比较时只关心Key。
这样设计可以最大程度复用 RBTree，避免为 set 和 map 分别实现不同的红黑树，set迁就了map。
如下方修改后的tree，如果是set建树，传给模板T的是key，树的结点就会用这个T(key)去定义数据；如果是map建树，传给模板T的是pair<K, V>，树的结点就会用这个T(pair<K, V>)去定义数据。
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
};
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
};还有一个问题就是，set，map建树需要比较key，set比较的就是保存的值，map比较的是保存的键值对pair<key，value>key的值。可以看出来set的值可以直接比较，但是 map 需要通过对键值对进行解引用才能得到key的值，两者方式不同。
我们可以通过仿函数+模板解决这个问题：
首先要再给RBTree添加一个模板，KeyOfT
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
};然后在map和set中实现各自KeyOfT的类，类中实现一个仿函数，分别取出他们自己的key：
namespace zzy
{
template<class K,class T>
class map
{
public:
//仿函数来获取值
struct MapKofT
{
const K& operator()(const pair<K, T>& V)
{
return V.first;
}
};
typedef typename RBTree<K, pair<K, T>, MapKofT>::Iterator iterator;
pair<iterator, bool> Insert(const pair<K, T>& data)
{
return _tree.insert(data);
}
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
T& operator[](const K& k)
{
pair<iterator, bool> ret = Insert(pair<K, T>(k, T()));
return ret.first->second;
}
private:
RBTree<K, pair<K, T>, MapKofT> _tree{};
};
}namespace zzy
{
template<class K>
class set
{
public:
struct SetKofT
{
const K& operator()(const K& k)
{
return k;
}
};
typedef typename RBTree<K, K, SetKofK>::Iterator iterator;
pair<iterator, bool> Insert(const K& k)
{
return _tree.insert(k);
}
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
private:
RBTree<K, K, SetKofT> _tree{};
};
}可以看到他们在建树时也把自己求K的类传给了RBTree。
这时树中的class KeyOfT模板接收的就是他们各自传的 SetKofT 和 MapKofT。
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool insert(const T& data)
{
KeyOfT kot;
while(cur)
{
if(kot(cur->data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
//...
}
}
};传过来的这个类要在函数中实例化一个对象kot才能用对象去使用其中的仿函数，像上面的代码一样。当然其实是SetKofT 或 MapKofT 类的对象去调用各自的仿函数。
2. 一个类型做 map/set 的 key 有什么要求？
：可以支持比大小 或者 提供仿函数比较大小
3. map的operator[ ]功能是什么？如何实现？
功能：它提供了对映射元素的快速访问和修改能力。
int main()
{
map<string, int> word_counts;
// 插入新元素
word_counts["apple"] = 5; // 键"apple"不存在，自动插入
// 修改现有元素
word_counts["apple"] += 3; // 现在"apple"对应的值是8
// 访问元素
cout << "apple count: " << word_counts["apple"] << endl;
// 访问不存在的键会创建新元素
cout << "orange count: " << word_counts["orange"] << endl;
// 现在map中包含"orange"键，值为0
return 0;
}实现：
opeartor[ ]的原理是：用<key，T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中。如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器；如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器。operator[ ]函数最后将insert返回键值对中的value返回。(给key返回value)
T& operator[](const K& k)
{
pair<iterator, bool> ret = Insert(pair<K, T>(k, T()));
return ret.first->second;
}创建一个新的键值对
pair<K, T>，其中：键是传入的
k值是用
T()构造的默认值（例如，如果T是int，则值为0）
return ret.first->second;ret.first是insert返回的迭代器->second访问迭代器指向的键值对中的值部分返回这个值的引用
multi_map / multi_set：
1.与各自 map 和 set 版本的不同：
| 特性 | map / set |
multimap / multiset |
|---|---|---|
| 元素唯一性 | 键/元素必须唯一 | 允许重复键/元素 |
| 插入行为 | key存在插入失败/忽略 | 总是插入新元素 |
| 查找返回值 | 返回单个迭代器 | 可能返回多个元素/迭代器范围 |
| 典型实现 | 红黑树 | 红黑树 |
| 内存占用 | 相对较小 | 可能较大（存储重复元素） |
| 查找 | count()返回0或1 | count()返回某元素数量 |
// map示例
map<int, string> m;
m.insert({1, "a"}); // 成功
m.insert({1, "b"}); // 失败，键1已存在
m[1] = "b"; // 覆盖原有值
// multimap示例
multimap<int, string> mm;
mm.insert({1, "a"}); // 成功
mm.insert({1, "b"}); // 成功，允许重复键
// mm[1] = "c"; // 错误，multimap不支持operator[]multimap不支持operator[ ]
如果operator[]用于multimap，当键重复时，无法明确应该返回哪个值的引用，导致语义模糊。
multimap<int, string> m;
m.insert({1, "a"});
m.insert({1, "b"});
string val = m[1]; // 应该返回 "a" 还是 "b"？1.2.2 哈希结构的关联式容器
最好的查询是，进行很少的比较次数就能将元素找到，所以C++11中，STL又提供了4个unordered系列的关联式容器，与红黑树结构的使用类似，只是底层结构不同。
unordered_map / unordered_set：（其实还有unordered_multimap/unordered_multiset）
1. 如何实现的：哈希表
规则：
unordered_map 中 key 是不能重复的，因此count函数的返回值最大为1。
unordered_map 的 operator[ ]，实际调用哈希桶的插入操作，用参数key和V()构造一个默认值往底层哈希桶插入，遍历桶内的元素，用 key 的 operator== 进行比较，找到匹配的 key，如果key不在哈希桶中，插入成功；如果找到：返回对应的 value。
大概实现：
底层实现：基于 指针数组 + 链表/红黑树（解决冲突），数组的每个槽位称为 桶，存储链表的头指针。
通过
哈希函数计算Key的哈希值，映射到桶数组的某个位置以完成增删查。当载荷因子到1时扩容到二倍，遍历所有元素，重新计算哈希并放入桶中。
2. unordered_map和map的区别
| 特性 | std::map |
std::unordered_map |
|---|---|---|
| 数据结构 | 红黑树（RB-Tree） | 哈希表（Hash Table）（数组 + 链表/红黑树） |
| 是否有序 | 是（按键 Key 升序排列） |
否（元素存储顺序取决于哈希函数） |
是否需要 operator< |
必须定义（用于排序） | 不需要 |
是否需要 hash 和 operator== |
不需要 | 必须定义（用于哈希计算和冲突检测） |
| 内存占用 | 较低 | 较高(桶数组 + 链表/红黑树） |
时间复杂度：
| 操作 | std::map (红黑树) |
std::unordered_map (哈希表) |
|---|---|---|
查找 find() |
O(log n) | 平均 O(1)，最坏 O(n)（哈希冲突严重时） |
插入 insert() |
O(log n) | 平均 O(1)，最坏 O(n) |
删除 erase() |
O(log n) | 平均 O(1)，最坏 O(n) |
遍历 iteration |
有序遍历（按 Key 排序） |
无序遍历（顺序取决于哈希桶） |
3. unordered_set 和 set 的区别
和上面的差不多，也是红黑树-哈希表、有序-无序、O(log n)-O(1)、内存占用较高-较低
4. 一个类型做 unordered_map / unordered_set 有什么要求？
unordered_map和unordered_set基于哈希表实现，因此必须能够计算Key的哈希值。- 必须提供相等比较（
operator==），需要通过operator==判断两个Key是否真正相等。