unorder_map

C++ 的 unordered_map  是标准模板库（STL）中的一个关联容器，它存储键值对，并通过哈希函数实现快速查找。以下是关于 unordered_map 的详细概览：

1. 基本特性

• 底层实现：哈希表（散列表）。
• 键的特性：键唯一且不可重复，插入后不可修改（若需修改，需删除后重新插入）。
• 元素顺序：无序，元素存储位置由哈希函数决定。
• 时间复杂度：平均情况下，插入、查找、删除操作的时间复杂度为 O(1)；最坏情况下为 O(n)（哈希冲突严重时）。

2. 常用函数

构造函数与初始化

#include <unordered_map>

// 默认构造函数
unordered_map<int,string> map1;

// 初始化列表构造
unordered_map<int,string> map2 = {{1, "apple"}, {2, "banana"}};

// 拷贝构造
unordered_map<int,string> map3(map2);

元素操作

// 插入元素
map1.insert({3, "cherry"});  // 方式 1：插入键值对
map1[4] = "date";           // 方式 2：通过[]赋值（不存在则创建）

// 访问元素
cout << map1[3];           // 通过键访问（键不存在时会插入默认值）
cout << map1.at(3);        // 通过键访问（键不存在时抛出 out_of_range 异常）

// 修改元素
map1[3] = "grape";         // 修改已存在的键对应的值

// 删除元素
map1.erase(3);             // 删除键为 3 的元素
map1.erase(map1.find(4));  // 通过迭代器删除
map1.clear();              // 清空所有元素

查找元素

// 查找键是否存在
if(map1.find(2) != map1.end()) {  // find 返回迭代器，不存在时返回 end()
    cout << "Key 2 exists";
}

// 统计键的数量（只能是 0 或 1）
if(map1.count(2) > 0) {           // count 返回键的出现次数
    cout << "Key 2 exists";
}

容量与大小

bool empty = map1.empty();  // 判断是否为空
size_t size = map1.size();  // 返回元素个数
size_t max_size = map1.max_size();  // 返回最大容量

迭代器

// 遍历所有元素（使用范围 for 循环更简洁）
for(const auto& pair: map1) {
    cout << pair.first << ": " << pair.second << endl;
}

// 使用迭代器遍历
for(auto it = map1.begin();it != map1.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

哈希表特性

size_t bucket_count = map1.bucket_count();  // 返回桶的数量
size_t bucket = map1.bucket(2);             // 返回键 2 所在的桶索引
float load_factor = map1.load_factor();     // 返回负载因子（元素数/桶数）
float max_load_factor = map1.max_load_factor();  // 返回最大负载因子
map1.rehash(10);  // 重新调整桶的数量（至少为 10）

3. 注意事项

1. 哈希函数与键比较：

   • 对于自定义类型（如结构体、类）作为键，需要自定义哈希函数和键比较函数。

   struct MyKey {
       int x,y;
       bool operator==(const MyKey& other)const {
           return x == other.x && y == other.y;
       }
   };
   
   // 自定义哈希函数
   struct MyHash {
       size_t operator()(const MyKey& k)const {
           return std::hash<int>()(k.x) ^ (std::hash<int>()(k.y) << 1);
       }
   };
   
   unordered_map<MyKey,string,MyHash> customMap;
   

2. 键的不可修改性：

   • 插入后的键不可直接修改，若需修改键，必须先删除再插入新键值对。

3. 性能考虑：

   • 当元素数量接近桶的数量时（负载因子过高），哈希冲突增加，性能下降。可通过  rehash() 或  reserve() 提前调整桶数量。

4. 与 map 的对比

string

C++ 的 std::string 是标准模板库（STL）中用于处理字符串的类，它封装了动态字符数组，并提供了丰富的操作函数。以下是关于 std::string 的详细概览：

1. 基本特性

• 底层实现：动态字符数组（通常以 '\0' 结尾）。
• 内存管理：自动管理内存，无需手动分配或释放。
• 元素类型：char（或 wchar_t、char16_t 等宽字符类型）。
• 线程安全：非线程安全，多线程环境下需外部同步。

2. 常用函数

构造函数与初始化

cpp

#include <string>

// 默认构造
string s1;                   // 空字符串

// 从 C 风格字符串构造
string s2("hello");          // s2 = "hello"
string s3 = "world";         // s3 = "world"

// 复制构造
string s4(s2);               // s4 = "hello"

// 部分复制
string s5("abcdef",3);      // s5 = "abc"（前 3 个字符）

// 重复字符
string s6(5, 'A');           // s6 = "AAAAA"

字符串操作

cpp

// 拼接
string s = s2 + " " + s3;    // s = "hello world"
s.append("!");               // s = "hello world!"
s += "??";                   // s = "hello world!??"

// 插入
s.insert(6, "beautiful");   // s = "hello beautiful world!??"

// 删除
s.erase(11,5);              // 删除从位置 11 开始的 5 个字符，s = "hello beautiful!??"

// 替换
s.replace(6,9, "cruel");    // 从位置 6 开始的 9 个字符替换为"cruel"，s = "hello cruel!??"

// 清空
s.clear();                   // s = ""

查找与比较

cpp

string str = "hello world";

// 查找子串
size_t pos = str.find("world");  // pos = 6（第一次出现的位置）
if(pos!= string::npos) {       // string::npos 表示未找到
    cout << "Found at position" << pos << endl;
}

// 反向查找
pos = str.rfind("l");            // pos = 9（最后一次出现的位置）

// 比较
bool equal = (str == "hello world");  // true
int cmp = str.compare("hello");       // 大于 0（按字典序比较）

子串与提取

cpp

string substr = str.substr(6,5);  // 从位置 6 开始的 5 个字符，substr = "world"

// 转为 C 风格字符串
const char* c_str = str.c_str();   // 返回以'\0'结尾的字符指针

大小写转换

cpp

#include <algorithm>

// 转为大写
transform(str.begin(),str.end(),str.begin(), ::toupper);  // str = "HELLO WORLD"

// 转为小写
transform(str.begin(),str.end(),str.begin(), ::tolower);  // str = "hello world"

容量与大小

cpp

bool empty = str.empty();      // 判断是否为空
size_t len = str.length();     // 返回字符串长度（同 size()）
size_t size = str.size();      // 返回字符串长度
size_t capacity = str.capacity();  // 返回当前分配的容量
str.reserve(100);              // 预分配至少 100 个字符的容量
str.resize(20, 'x');           // 调整长度为 20，不足部分用'x'填充

迭代器

cpp

// 正向遍历
for(auto it = str.begin();it != str.end(); ++it) {
    cout << *it;
}

// 反向遍历
for(auto rit = str.rbegin();rit != str.rend(); ++rit) {
    cout << *rit;
}

// 范围 for 循环（C++11+）
for(char c: str) {
    cout << c;
}

3. 字符串与数值转换

cpp

// 数值转字符串（C++11+）
string numStr = to_string(12345);      // numStr = "12345"
string floatStr = to_string(3.14);     // floatStr = "3.140000"

// 字符串转数值（C++11+）
int num = stoi("123");                // num = 123
double d = stod("3.14");              // d = 3.14
long long ll = stoll("9223372036854775807");  // 大整数

// 错误处理（转换失败时抛出异常）
try {
    int invalid = stoi("abc");
} catch(const invalid_argument& e) {
    cout << "Invalid number" << endl;
}

4. 注意事项

1. 性能考虑：

   • 频繁的插入 / 删除操作可能导致内存重新分配，性能下降。可使用  reserve() 预分配内存。
   • += 和  append() 比  insert() 效率更高。

2. 字符编码：

   • std::string 默认处理单字节字符（如 ASCII），处理多字节字符（如 UTF-8）时需注意编码规则。

3. 与 C 风格字符串的转换：

   • 使用  c_str() 获取 C 风格字符串指针。
   • 使用  data() 在 C++11 及以后与  c_str() 功能相同（返回以 '\0' 结尾的指针）。