QC++ / Qt 学习之路

STL 容器

熟悉常用容器接口并掌握选型依据

进阶第 7 / 48 章第一篇 · C++ 基础巩固

#一张对照表看懂容器

如果你来自 Python 或 Java,STL 容器基本都能找到老朋友——只是名字换了、行为细节更明确了。先建立映射关系,学起来会快很多:

STL 容器选型决策图先看访问方式,再看插入位置,最后看是否需要排序去重要存一组数据vector默认首选:连续内存,随机访问 O(1)deque需要头尾两端高效插入删除list频繁在中间任意位置插入删除map有序 key-value,按键排序,O(log n)unordered_map哈希 key-value,平均 O(1) 最快set只需去重并自动排序的 key判据:随机访问 → vector;两端操作 → deque;中间插删 → list;键值映射 → map / unordered_map;去重 → set
STL 容器选型决策
C++ 容器PythonJava底层结构特点
std::vector<T>listArrayList连续动态数组随机访问 O(1),尾部增删 O(1),中间插入 O(n)
std::deque<T>collections.dequeArrayDeque分段连续块头尾增删均 O(1),随机访问 O(1)
std::list<T>无直接对应LinkedList双向链表任意位置插入 O(1),无随机访问
std::set<T>setTreeSet红黑树有序、去重,增删查 O(log n)
std::map<K,V>无(Python 3.7+ dict 保序但非排序)TreeMap红黑树按键排序,增删查 O(log n)
std::unordered_map<K,V>dictHashMap哈希表无序,平均 O(1),最坏 O(n)
std::unordered_set<T>set(实际就是它)HashSet哈希表去重,平均 O(1)
std::stringstrString连续数组可变,支持 SSO 小字符串优化

一个重要的心智差异:C++ 容器是"值容器"。std::vector<Person> v; Person p = v[0]; 会真的复制一份 Person;Python 和 Java 里 p = v[0] 拿到的只是引用。这既带来拷贝成本(用 const auto& 遍历可避免),也带来安全性(不会出现"改了容器里的对象却意外影响别处"的别名问题)。

#std::string:不只是字符串

C++ 的 std::string 是可变的,这一点和 Java 的 String(不可变)、Python 的 str(不可变)完全不同,倒更像 Java 的 StringBuilder。它底层是连续内存,支持 += 追加、[] 随机访问、resize 等,用起来很像 Python 的 list 和 str 的混合体。

另外 C++ 的字符串字面量 "hello" 类型是 const char[N](会退化成 const char*),不是 std::string。混用时编译器会自动转换,但要注意由此产生的临时对象开销。C++17 引入的 std::string_view 是只读场景的更好选择(第 3 章已提过),Qt 中对应的是 QString 和 QStringView。

C++
#include <iostream>
#include <string>
#include <string_view>

int main() {
    std::string s = "Hello";          // 从字面量构造
    s += ", C++";                     // 追加,可变(Java String 做不到)
    s.append(3, '!');                 // 追加 3 个 '!'
    std::cout << s << "\n";           // Hello, C++!!!

    std::cout << "长度 " << s.size()           // 字节数,不含 '\0'
              << ",首字符 " << s.front()
              << ",末字符 " << s.back() << "\n";

    // 查找与截取:find 找不到时返回 npos(一个巨大的 size_t)
    auto pos = s.find("C++");
    if (pos != std::string::npos) {
        std::cout << "在位置 " << pos << " 找到\n";
        std::cout << "子串: " << s.substr(pos, 3) << "\n";
    }

    // 插入与删除
    s.insert(5, " World");
    s.erase(5, 6);
    std::cout << "编辑后: " << s << "\n";

    // 数值转换:C++11 起有 stoi / stod / to_string
    int    n = std::stoi("1024");
    double d = std::stod("3.14159");
    std::cout << n << " " << d << " " << std::to_string(n) << "\n";

    // string_view(C++17):只读视图,零拷贝,不拥有数据
    std::string_view sv = s;          // 隐式转换,不会复制字符
    std::cout << "视图长度 " << sv.size() << ",前 5 字符 " << sv.substr(0, 5) << "\n";

    // 注意:string_view 不管理生命周期,切勿指向已销毁的临时 string
    // std::string_view bad = std::string("临时");   // 危险:悬垂视图

    // 遍历:C++ 的 string 存的是字节,UTF-8 中文占 3 字节
    std::string utf8 = "你好Qt";
    std::cout << "中文字节数 " << utf8.size() << "\n";   // 不是 4
    return 0;
}

#std::vector:默认容器

不知道该用什么容器时,就用 vector。 这是 C++ 社区公认的默认选择,理由和 Python 里 list 一家独大类似:连续内存带来的缓存友好性,往往比渐进复杂度的优劣更重要。哪怕你需要在中间插入,除非数据量很大,vector 也常常比 list 快。

需要掌握的三个要点:reserve() 预分配避免反复扩容;emplace_back 原地构造避免临时对象;迭代器失效规则(扩容后所有迭代器/引用/指针全部失效,erase 后从删除点开始的都失效)。

C++
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>      // std::move
#include <vector>

struct Person {
    std::string name;
    int         age{0};

    // 聚合类型(无自定义构造函数)不能用 emplace_back("Bob", 25) 这种括号写法,
    // 所以显式给出构造函数;或者改用 push_back(Person{"Bob", 25})
    Person(std::string n, int a) : name(std::move(n)), age(a) {}
};

int main() {
    std::vector<int> v{1, 2, 3};
    v.push_back(4);
    v.emplace_back(5);                // 原地构造,比 push_back 少一次临时对象

    std::cout << "大小 " << v.size() << ",容量 " << v.capacity() << "\n";

    // reserve 预分配:避免多次扩容(每次扩容要复制全部元素)
    std::vector<int> big;
    big.reserve(1000);
    for (int i = 0; i < 1000; ++i) {
        big.push_back(i);
    }
    std::cout << "预分配后容量 " << big.capacity() << "(不会反复增长)\n";

    // 三种访问方式:[] 不检查越界,at() 越界抛异常,front/back 访问首尾
    std::cout << v[0] << " " << v.at(1) << " " << v.front() << " " << v.back() << "\n";
    try {
        std::cout << v.at(99) << "\n";
    } catch (const std::out_of_range& e) {
        std::cout << "越界捕获: " << e.what() << "\n";
    }

    // 插入与删除:中间操作是 O(n)
    v.insert(v.begin() + 1, 99);      // 在下标 1 处插入
    v.erase(v.begin() + 1);           // 删除刚插入的元素
    v.pop_back();                     // 删除尾部,O(1)

    // 存自定义类型:emplace_back 直接传构造参数
    std::vector<Person> people;
    people.push_back(Person{"Alice", 30});     // 构造临时对象再移动
    people.emplace_back("Bob", 25);            // 直接原地构造,更优
    people.reserve(100);

    // 遍历:const auto& 避免复制整个 Person
    for (const auto& p : people) {
        std::cout << p.name << "(" << p.age << ") ";
    }
    std::cout << "\n";

    // 用 vector 模拟栈:back/push_back/pop_back 足够
    std::vector<int> stack;
    stack.push_back(1);
    stack.push_back(2);
    while (!stack.empty()) {
        std::cout << stack.back() << " ";
        stack.pop_back();
    }
    std::cout << "\n";
    return 0;
}

上面的 at() 在越界时抛 std::out_of_range(第 10 章会系统讲异常),这也是它比 [] 安全的地方——后者越界属于未定义行为,可能静默读到垃圾数据。

#map / set / unordered_map:三种关联容器

std::map 和 std::unordered_map 的取舍,等价于 Java 里 TreeMap 与 HashMap、Python 里"没有内置有序 dict"的取舍:需要按 key 排序遍历、或需要 lower_bound 这类区间查询,用 map;只做精确查找,用 unordered_map(它平均 O(1),通常快 2-5 倍)。

Python 的 dict 从 3.7 起保证插入顺序,这和两者都不同;如果你要的是插入顺序,C++ 标准库没有直接对应物,通常用 vector 辅助维护顺序。

std::set 与 std::unordered_set 同理,对应 Python 的 set(Python 的 set 实际就是哈希表实现,等价 unordered_set)。

C++
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>

int main() {
    // 1) map:按键排序的红黑树
    std::map<std::string, int> scores{
        {"Alice", 90}, {"Bob", 85}, {"Carol", 92}
    };
    scores["Dave"] = 78;              // operator[] 不存在时会自动插入默认值
    scores.insert_or_assign("Bob", 88);  // C++17:存在则改,不存在则插

    for (const auto& [name, score] : scores) {   // 结构化绑定(C++17)
        std::cout << name << ":" << score << " ";
    }
    std::cout << "\n";                // 按字母序输出,map 自动排序

    // 查找:find 返回迭代器,找不到是 end()。不要用 operator[] 来"查",它会插入
    auto it = scores.find("Alice");
    if (it != scores.end()) {
        std::cout << "Alice = " << it->second << "\n";
    }
    std::cout << "count(Bob) = " << scores.count("Bob") << "\n";   // 0 或 1
    std::cout << "contains(Carol) = " << std::boolalpha
              << (scores.count("Carol") > 0) << "\n";              // C++20 有 contains()

    // 区间查询是 map 的独有能力
    auto lower = scores.lower_bound("B");
    if (lower != scores.end()) {
        std::cout << "第一个 >= B 的键: " << lower->first << "\n";
    }

    // 2) unordered_map:哈希表,无序但更快
    std::unordered_map<std::string, int> fast{
        {"apple", 5}, {"banana", 3}, {"cherry", 8}
    };
    for (const auto& [k, v] : fast) {
        std::cout << k << " ";
    }
    std::cout << "\n(顺序不确定)\n";

    // 自定义类型做 key 需要提供 hash 和 ==,内置类型已内置
    fast.reserve(1000);               // 预分配桶,减少 rehash

    // 3) set:有序去重;unordered_set:哈希去重
    std::set<int> unique_sorted{3, 1, 4, 1, 5, 9, 2, 6};
    std::cout << "set: ";
    for (int x : unique_sorted) {
        std::cout << x << " ";        // 1 2 3 4 5 6 9,有序且去重
    }
    std::cout << "\n";

    std::unordered_set<std::string> tags{"cpp", "qt", "cpp", "stl"};
    std::cout << "tags 去重后数量 = " << tags.size() << "\n";   // 3

    // 4) 统计词频:map 的经典用法(Python 的 collections.Counter)
    std::string text = "the quick brown fox jumps over the lazy dog the end";
    std::unordered_map<std::string, int> freq;
    {
        std::string word;
        for (char ch : text) {
            if (ch == ' ') {
                if (!word.empty()) { ++freq[word]; word.clear(); }
            } else {
                word += ch;
            }
        }
        if (!word.empty()) { ++freq[word]; }
    }
    std::cout << "the 出现 " << freq["the"] << " 次\n";
    return 0;
}

注意 operator[] 的副作用:用 m[key] 查找不存在的键会插入一个默认值,可能悄悄改变容器。只读查找一律用 find() 或 C++20 的 contains()。

#deque、list 与容器适配器

std::deque(double-ended queue)支持头尾 O(1) 增删,同时保留 O(1) 随机访问,是 std::stack 和 std::queue 的默认底层容器。std::list 是双向链表,任意位置插入 O(1) 且迭代器不会因插入而失效,但内存不连续、缓存命中率低——实际工程中它用得比想象中少,多数场景 vector 更快。Java 的 LinkedList 同理,社区也普遍建议优先 ArrayList。

容器适配器不是真正的容器,而是在已有容器上套一层受限接口:

  • std::stack<T>:后进先出,只暴露 push/pop/top。
  • std::queue<T>:先进先出,只暴露 push/pop/front/back。
  • std::priority_queue<T>:最大堆,top() 取最大元素。

它们对应 Python 的 collections.deque(当栈/队列用)和 heapq。

C++
#include <algorithm>
#include <deque>
#include <functional>    // std::greater
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>

int main() {
    // 1) deque:头尾都能高效增删
    std::deque<int> dq{2, 3, 4};
    dq.push_front(1);                 // 头部 O(1)
    dq.push_back(5);                  // 尾部 O(1)
    std::cout << "deque: ";
    for (int x : dq) { std::cout << x << " "; }
    std::cout << ",随机访问 dq[2] = " << dq[2] << "\n";

    // 2) list:链表,插入不失效已有迭代器
    std::list<std::string> tasks{"编译", "测试"};
    auto pos = tasks.begin();
    ++pos;
    tasks.insert(pos, "打包");        // O(1),且已有迭代器仍有效
    tasks.remove("测试");             // 按值删除,list 特有
    for (const auto& t : tasks) { std::cout << t << " "; }
    std::cout << "\n";

    // 3) stack:默认基于 deque
    std::stack<int> st;
    st.push(1); st.push(2); st.push(3);
    std::cout << "stack 出栈顺序: ";
    while (!st.empty()) {
        std::cout << st.top() << " ";
        st.pop();
    }
    std::cout << "\n";

    // 4) queue:先进先出
    std::queue<std::string> q;
    q.push("任务A"); q.push("任务B"); q.push("任务C");
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << "\n";

    // 5) priority_queue:默认大顶堆
    std::priority_queue<int> pq;
    for (int x : {5, 1, 9, 3, 7}) { pq.push(x); }
    std::cout << "priority_queue: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";   // 9 7 5 3 1
        pq.pop();
    }
    std::cout << "\n";

    // 小顶堆:换比较器(greater 需要 <functional>)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    for (int x : {5, 1, 9, 3, 7}) { min_heap.push(x); }
    std::cout << "最小值 = " << min_heap.top() << "\n";
    return 0;
}

#迭代器:容器与算法之间的胶水

迭代器是所有容器统一的访问接口,可以类比 Python 的迭代器协议(__iter__ / __next__)或 Java 的 Iterator。但 C++ 的迭代器更接近广义化的指针:支持 * 解引用、++ 前进,vector 的迭代器还支持 + n 随机跳跃。

所有容器都有 begin() / end(),注意 end() 指向最后一个元素之后的位置(尾后迭代器),不能解引用——这个半开区间 [begin, end) 设计和 Python 的切片 a[0:len(a)] 思路一致。

C++ 迭代器按能力分五类,从弱到强:输入 → 输出 → 前向 → 双向 → 随机访问。容器的迭代器类型决定了能用哪些算法(第 8 章详述)。简单记忆:vector/deque/array/string 是随机访问,list/set/map 是双向,forward_list 是前向,istream_iterator 是输入。

C++
#include <algorithm>     // std::copy
#include <iostream>
#include <iterator>      // std::distance, std::back_inserter
#include <list>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30, 40, 50};

    // 1) 显式迭代器遍历:begin() 指向首元素,end() 是尾后哨兵
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";       // *it 解引用拿到元素
    }
    std::cout << "\n";

    // 2) 需要修改元素时用非 const 迭代器
    for (auto it = v.begin(); it != v.end(); ++it) {
        *it *= 2;
    }

    // 3) 只读遍历用 cbegin()/cend(),返回 const_iterator
    for (auto it = v.cbegin(); it != v.cend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // 4) 随机访问迭代器支持算术运算(vector/string/deque 专属)
    auto mid = v.begin() + 2;
    std::cout << "中间元素 = " << *mid
              << ",两个迭代器距离 = " << std::distance(v.begin(), v.end()) << "\n";

    // 5) 反向迭代器:rbegin()/rend() 倒着走
    std::cout << "倒序: ";
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // 6) list 的迭代器是双向的,不支持 + n,只能用 ++
    std::list<std::string> names{"a", "b", "c"};
    auto lit = names.begin();
    ++lit;                             // OK
    // auto bad = lit + 1;             // 编译错误:双向迭代器没有 operator+
    std::cout << "list 第二个元素 = " << *lit << "\n";

    // 7) map 的迭代器指向 pair<const K, V>
    std::map<std::string, int> m{{"x", 1}, {"y", 2}};
    for (auto it = m.begin(); it != m.end(); ++it) {
        std::cout << it->first << "=" << it->second << " ";
    }
    std::cout << "\n";

    // 8) 插入迭代器:back_inserter 让算法可以往容器里追加(第 8 章会用到)
    std::vector<int> dst;
    std::copy(v.begin(), v.end(), std::back_inserter(dst));
    std::cout << "复制后目标大小 = " << dst.size() << "\n";
    return 0;
}

std::back_inserter 是插入迭代器,它让"只负责读取和写入元素的算法"能够自动扩容目标容器,是连接容器与算法的常用桥梁。

#选型决策

最后给一套实用的决策顺序:

  1. 默认 vector。它有最好的缓存局部性,sort/find 等算法配合起来也最简单。
  2. 需要频繁在头部增删且要随机访问 → deque。
  3. 需要频繁在中间插入且元素很大、已有迭代器必须保持有效 → list(先测性能,很多时候 vector 仍更快)。
  4. 需要 key-value 精确查找 → unordered_map;需要有序遍历或区间查询 → map。
  5. 需要去重 → unordered_set(快)或 set(有序)。
  6. 需要栈/队列语义 → 容器适配器,别自己用 vector 拼。

Qt 里对应的是 QVector(Qt 6 中已基本等于 std::vector 的别名)、QList、QMap、QHash、QStringList。Qt 6 的方向是尽量与 STL 统一,所以学好 STL 容器,迁移到 Qt 容器几乎没有成本。

#小结

  1. 容器映射:vector≈Python list/Java ArrayList,unordered_map≈Python dict/Java HashMap,map≈TreeMap,unordered_set≈Python set。
  2. C++ 容器存的是值:v[0] 取出来是副本概念,遍历用 const auto& 避免不必要的拷贝。
  3. std::string 可变(更像 StringBuilder),size() 返回字节数;只读参数用 C++17 的 string_view。
  4. vector 是默认容器:reserve() 预分配、emplace_back 原地构造,注意扩容会让所有迭代器失效。
  5. 关联容器查询用 find()/C++20 contains(),operator[] 会自动插入默认值,只读场景是坑。
  6. 迭代器是广义指针,end() 是尾后哨兵;vector/string 支持随机访问,list/set/map 只有双向。

#练习

  1. 用 std::vector<int> 读入 20 个整数,去掉重复值后排序输出。要求用 reserve 预处理,并在代码里说明为什么先去重再排序。
  2. 统计一段英文文本的词频,分别用 std::map 和 std::unordered_map 实现,输出前 5 个高频词。观察两种实现输出顺序的差异。
  3. 用 std::stack<char> 判断括号串 "{[()()]}" 是否匹配,支持 ()、[]、{} 三种括号。
  4. 写一个 std::vector<std::string>,故意在遍历过程中 push_back 触发扩容,观察之前保存的迭代器是否失效(打印前后地址对比)。再用 reserve 预留足够空间重试一次,并把练习 2 的词频统计改成返回 std::vector<std::pair<std::string,int>>、用 std::sort 按频次降序排列——这会把你引向第 8 章的算法。
我的学习笔记笔记总览
笔记保存在本机浏览器(localStorage),换设备或清理缓存会丢失;重要内容请点「导出全部笔记」存成 .md 文件。