cpp重学(三)#

1
class Shape {
2
public:
3
    virtual double area() const { return 0; }
4
};
5

6
class Circle : public Shape {
7
    double r_;
8
public:
9
    Circle(double r) : r_(r) {}
10
    double area() const override { return 3.14159 * r_ * r_; }
11
};
12

13
void show(Shape s) {          // 注意：按值传
14
    std::cout << s.area() << "\n";
15
}
16

17
Circle c(5.0);
18
show(c);                      // 输出 0！不是预期的 78.5

1
std::vector<Shape> shapes;      // 容器装的是 Shape（按值）
2
shapes.push_back(Circle(5.0));  // 切片！Circle 变成 Shape 存进去

1
void show(const Shape& s) {     // 引用：不拷贝
2
    std::cout << s.area() << "\n";   // 78.5，多态正常
3
}
4

5
void show2(const Shape* s) {    // 指针同理
6
    std::cout << s->area() << "\n";
7
}
8

9
show(c);                        // 正常
10
show2(&c);                      // 正常

1
std::vector<int> v;
2
v.reserve(100);          // 预分配能装 100 个元素的内存
3

4
v.size();                // 大小：当前实际有多少个元素 = 0
5
v.capacity();            // 容量：当前分配的内存能装多少个 = 100

1
std::vector<int> v;
2
v.reserve(1000000);            // 先申请好
3
for (int i = 0; i < 1000000; ++i) {
4
    v.push_back(i);            // 全程不扩容，稳定 O(1)
5
}

1
std::string s = "hello world";
2
size_t pos = s.find("xyz");
3

4
if (pos != std::string::npos) {    // 查到了，pos 是下标
5
    // ...
6
} else {                           // 没查到
7
    // ...
8
}

1
const char* p = s.c_str();
2
s += " more text";          // 触发扩容，内部缓冲区换了位置
3
use(p);                     // p 指向已释放/无效的内存！悬垂

1
// 正确姿势：用完即丢，不存起来
2
printf("%s\n", s.c_str());          // 临时用，安全
3
// 或者先拷贝到自己的缓冲区
4
std::string copy = s;               // 要长期持有就自己存一份

1
std::string s = "a";
2
s += "b";          // 追加：尽量复用已有空间
3
s = s + "c";       // 加法：创建新对象再赋值

1
// 慢：每次 + 都新建一个 string（大量分配）
2
std::string r;
3
for (int i = 0; i < 10000; ++i) r = r + std::to_string(i);
4

5
// 快：reserve + append/+=（复用空间）
6
std::string r;
7
r.reserve(60000);
8
for (int i = 0; i < 10000; ++i) r += std::to_string(i);

1
for (char c : s) { /* 逐字符遍历 */ }
2
for (auto it = s.begin(); it != s.end(); ++it) { /* 迭代器 */ }
3
std::sort(s.begin(), s.end());     // 字符排序，算法库直接上

1
#include <array>
2

3
std::array<int, 10> data;       // 类型里直接写大小
4
data.size();                    // 10，随时可查
5

6
std::array<int, 5> a = {1, 2, 3, 4, 5};
7
a[0];                           // O(1) 访问
8
a.at(0);                        // 带边界检查
9

10
void process(const std::array<int, 10>& data) {
11
    // 长度是类型的一部分，不会丢
12
    for (int x : data) { /* ... */ }
13
}

1
std::array<std::array<int, 3>, 3> grid{};   // 3×3 二维数组
2

3
// 遍历
4
for (const auto& row : grid) {
5
    for (int x : row) { /* ... */ }
6
}

1
#include <list>
2

3
std::list<int> l = {1, 2, 3};
4
l.push_back(4);           // 尾插 O(1)
5
l.push_front(0);          // 头插 O(1)——这是 list 比 vector 强的地方
6
l.insert(++l.begin(), 99); // 中间插入 O(1)，不用搬元素
7

8
for (int x : l) { /* 遍历 */ }

1
// 各插入 100 万个元素，然后遍历
2
std::list<int> l;
3
for (int i = 0; i < 1000000; ++i) l.push_back(i);
4

5
std::vector<int> v;
6
v.reserve(1000000);
7
for (int i = 0; i < 1000000; ++i) v.push_back(i);

1
#include <deque>
2

3
std::deque<int> d;
4
d.push_back(1);          // 尾插 O(1)
5
d.push_front(0);         // 头插 O(1)——vector 做不到
6
d[2];                    // 还能随机访问 O(1)！
7

8
for (int x : d) { /* ... */ }

1
#include <map>
2

3
std::map<std::string, int> scores;
4
scores["alice"] = 95;         // 插入/更新
5
scores["bob"] = 88;
6

7
std::cout << scores["alice"];          // 读取：95
8
auto it = scores.find("bob");          // 查找
9
if (it != scores.end()) { /* 找到了 */ }
10

11
for (const auto& [name, score] : scores) {   // 有序遍历（按键排序）
12
    std::cout << name << ": " << score << "\n";
13
}

1
if (scores["nobody"] > 100) { ... }   // 副作用：插入了 "nobody"！

1
auto it = scores.find("lihua");
2
if(it != scores.end()){}//存在
3
// scores.at("nobody");  // 不存在会抛异常

1
#include <set>
2

3
std::set<int> s = {5, 1, 3, 1};    // 重复的 1 会被忽略
4
s.insert(2);
5
s.erase(1);
6

7
s.size();                          // 去重后的大小
8
if (s.count(3)) { /* 在不在集合里 */ }
9
for (int x : s) { /* 有序遍历：1 2 3 5 */ }

1
#include <unordered_map>
2
#include <unordered_set>
3

4
std::unordered_map<std::string, int> u;
5
u["alice"] = 95;
6
u["bob"] = 88;
7

8
auto it = u.find("alice");      // 平均 O(1)
9
u.count("alice");               // 0 或 1
10

11
std::unordered_set<int> s = {3, 1, 2};
12
s.insert(5);
13
s.erase(3);

1
std::vector<int> v = {3, 1, 2};
2

3
for (auto it = v.begin(); it != v.end(); ++it) {
4
    std::cout << *it;        // *it 解引用，跟指针一模一样
5
}

1
// 这段代码换成 list、deque、map、set 都能跑
2
for (auto it = c.begin(); it != c.end(); ++it) {
3
    std::cout << *it;
4
}

1
for (int x : v) { ... }

1
for (auto it = v.begin(); it != v.end(); ++it) {
2
    int x = *it;      // 拷贝（int 便宜）
3
    ...
4
}

1
std::vector<int> v = {1, 2, 3, 4};
2
auto it = v.begin();        // 指向 1
3

4
v.push_back(5);             // 可能触发扩容（第 32 篇）
5
// *it;                     // 危险！扩容后内存换了地方，it 悬垂

1
// 删除所有偶数（vector）
2
for (auto it = v.begin(); it != v.end(); ) {
3
    if (*it % 2 == 0) it = v.erase(it);   // erase 返回下一个有效迭代器
4
    else ++it;
5
}

1
#include <algorithm>
2
#include <vector>
3

4
std::vector<int> v = {5, 2, 8, 1};
5

6
std::sort(v.begin(), v.end());              // 排序
7
auto it = std::find(v.begin(), v.end(), 8); // 查找
8
int n = std::count(v.begin(), v.end(), 1);  // 计数
9
bool any = std::any_of(v.begin(), v.end(),  [](int x){ return x < 0; });  // 判断

1
std::sort(v.begin(), v.end());          // 升序
2
std::sort(v.begin(), v.end(), std::greater<int>());   // 降序

1
struct Student { std::string name; int score; };
2

3
std::vector<Student> students = {{"alice", 95}, {"bob", 88}, {"carol", 92}};
4

5
std::sort(students.begin(), students.end(),
6
          [](const Student& a, const Student& b) {
7
              return a.score > b.score;   // 按分数降序
8
          });

1
std::vector<int> v = {3, 1, 4, 1, 5, 9};
2

3
auto it = std::find(v.begin(), v.end(), 4);    // 找 4，返回迭代器
4
if (it != v.end()) { /* 找到了，*it == 4 */ }
5

6
int ones = std::count(v.begin(), v.end(), 1);   // 1 出现 2 次
7

8
std::sort(v.begin(), v.end());                  // 排序后：
9
std::binary_search(v.begin(), v.end(), 5);      // 二分查找 O(log n)（要求已排序）
10

11
std::min_element(v.begin(), v.end());           // 最小元素位置
12
std::max_element(v.begin(), v.end());           // 最大元素位置
13
std::accumulate(v.begin(), v.end(), 0);         // 求和（<numeric>）
14
std::reverse(v.begin(), v.end());               // 反转

1
#include <stack>
2

3
std::stack<int> s;
4
s.push(1);        // 入栈
5
int x = s.top();  // 读栈顶（不弹）
6
s.pop();          // 弹栈顶（不返回值）
7
s.empty();        // 是否为空
8
s.size();         // 元素个数

1
#include <stack>
2
#include <vector>
3

4
std::stack<int, std::vector<int>> sv;  // 用 vector 当底层

1
#include <queue>
2

3
std::queue<int> q;
4
q.push(1);        // 队尾入队
5
q.push(2);
6
int f = q.front(); // 队头（最先进入的）
7
int b = q.back();  // 队尾（最后进入的）
8
q.pop();          // 队头出队

1
#include <queue>
2
#include <iostream>
3

4
std::priority_queue<int> pq;
5
pq.push(3);
6
pq.push(1);
7
pq.push(4);
8
pq.push(1);
9
pq.push(5);
10

11
while (!pq.empty()) {
12
    std::cout << pq.top() << " ";  // 5 4 3 1 1
13
    pq.pop();
14
}

1
#include <queue>
2
#include <vector>
3

4
// 小顶堆：用 std::greater 反转比较方向
5
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
6

7
// 自定义类型：按某个字段比较
8
struct Task {
9
    int priority;
10
    int id;
11
};
12

13
struct TaskCmp {
14
    bool operator()(const Task& a, const Task& b) const {
15
        return a.priority < b.priority;  // 优先级大的先出
16
    }
17
};
18

19
std::priority_queue<Task, std::vector<Task>, TaskCmp> tasks;