1. 數(shù)組（Array）

數(shù)組是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)一組相同類(lèi)型的數(shù)據(jù)。

• 特點(diǎn)：
• 固定大小，一旦聲明，大小不能改變。
• 直接訪問(wèn)元素，時(shí)間復(fù)雜度為 O(1)。
• 適合處理大小已知、元素類(lèi)型相同的集合。

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // 輸出第一個(gè)元素

2. 結(jié)構(gòu)體（Struct）

結(jié)構(gòu)體允許將不同類(lèi)型的數(shù)據(jù)組合在一起，形成一種自定義的數(shù)據(jù)類(lèi)型。

• 特點(diǎn)：
• 可以包含不同類(lèi)型的成員變量。
• 提供了對(duì)數(shù)據(jù)的基本封裝，但功能有限。

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // 輸出 Alice

3. 類(lèi)（Class）

類(lèi)是 C++ 中用于面向?qū)ο缶幊痰暮诵慕Y(jié)構(gòu)，允許定義成員變量和成員函數(shù)。與 struct 類(lèi)似，但功能更強(qiáng)大，支持繼承、封裝、多態(tài)等特性。

• 特點(diǎn)：
• 可以包含成員變量、成員函數(shù)、構(gòu)造函數(shù)、析構(gòu)函數(shù)。
• 支持面向?qū)ο筇匦?，如封裝、繼承、多態(tài)。

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // 輸出: Name: Bob, Age: 30

4. 鏈表（Linked List)

鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。

• 特點(diǎn)：
• 動(dòng)態(tài)調(diào)整大小，不需要提前定義容量。
• 插入和刪除操作效率高，時(shí)間復(fù)雜度為 O(1)（在鏈表頭部或尾部操作）。
• 線性查找，時(shí)間復(fù)雜度為 O(n)。

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // 插入新節(jié)點(diǎn)

5. 棧（Stack）

列是一種先進(jìn)先出（FIFO, First In First Out）的數(shù)據(jù)結(jié)構(gòu)，常用于廣度優(yōu)先搜索、任務(wù)調(diào)度等場(chǎng)景。

• 特點(diǎn)：
• 插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行。
• 時(shí)間復(fù)雜度為 O(1)。

#include <iostream>  
#include <stack>
using namespace std;  
int main(){
     stack<int> sti;
     sti.push(1);
     sti.push(2);
        cout<<"棧查看棧頂元素："<<sti.top()<<endl;
     sti.pop();
      cout<<"棧查看棧頂元素："<<sti.top()<<endl;
    return 0;
};

7. 雙端隊(duì)列（Deque）

雙端隊(duì)列允許在兩端進(jìn)行插入和刪除操作，是棧和隊(duì)列的結(jié)合體。

• 特點(diǎn)：
• 允許在兩端進(jìn)行插入和刪除。

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // 輸出 2
dq.pop_front();

8. 哈希表（Hash Table）

哈希表是一種通過(guò)鍵值對(duì)存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，支持快速查找、插入和刪除操作。C++ 中的 unordered_map 是哈希表的實(shí)現(xiàn)。

• 特點(diǎn)：
• 使用哈希函數(shù)快速定位元素，時(shí)間復(fù)雜度為 O(1)。
• 不保證元素的順序。

重點(diǎn)

• 插入

 // unordered_map - 哈希表，無(wú)序
    unordered_map<int, string> um;
    um.insert({3, "three"});
    um.emplace(1, "one");
    um[2] = "two";  // 順序不確定

• 刪除

void eraseComparison() {
    map<int, string> m = {{1,"a"}, {2,"b"}, {3,"c"}, {4,"d"}};
    unordered_map<int, string> um = {{1,"a"}, {2,"b"}, {3,"c"}, {4,"d"}};
        // 通過(guò)鍵刪除 - 語(yǔ)法相同
    m.erase(2);
    um.erase(2);
        // 通過(guò)迭代器刪除 - 語(yǔ)法相同
    auto it_m = m.find(3);
    if (it_m != m.end()) m.erase(it_m);
        auto it_um = um.find(3);
    if (it_um != um.end()) um.erase(it_um);
        // 范圍刪除 - 語(yǔ)法相同
    m.erase(m.begin(), m.end());  // 清空
    um.erase(um.begin(), um.end()); // 清空
}

• 修改

void updateComparison() {
    map<int, string> m = {{1, "old1"}, {2, "old2"}};
    unordered_map<int, string> um = {{1, "old1"}, {2, "old2"}};
        // 修改值 - 語(yǔ)法相同
    m[1] = "new1";           // O(log n)
    um[1] = "new1";          // 平均 O(1)
        // 通過(guò)迭代器修改值（不能修改鍵）
    auto it_m = m.find(2);
    if (it_m != m.end()) it_m->second = "new2";  // O(log n)查找
        auto it_um = um.find(2);
    if (it_um != um.end()) it_um->second = "new2"; // 平均 O(1)查找
}

• 查找

#include <map>
#include <unordered_map>
using namespace std;

void searchComparison() {
    map<int, string> m = {{1,"a"}, {2,"b"}, {3,"c"}};
    unordered_map<int, string> um = {{1,"a"}, {2,"b"}, {3,"c"}};
    
    // 使用 find() - 語(yǔ)法相同
    auto it_m = m.find(2);  // O(log n)
    auto it_um = um.find(2); // 平均 O(1)
        if (it_m != m.end()) {
        cout << "map找到: " << it_m->second << endl;
    }
        if (it_um != um.end()) {
        cout << "unordered_map找到: " << it_um->second << endl;
    }
        // 使用 count() - 語(yǔ)法相同
    if (m.count(2)) {  // O(log n)
        cout << "map中存在鍵2" << endl;
    }
        if (um.count(2)) { // 平均 O(1)
        cout << "unordered_map中存在鍵2" << endl;
    }
        // 使用 [] 操作符 - 語(yǔ)法相同
    cout << "map[2] = " << m[2] << endl;     // O(log n)
    cout << "um[2] = " << um[2] << endl;     // 平均 O(1)
}

舉例

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
    unordered_map<string, int> map = {
        {"apple", 1},
        {"banana", 2},
        {"cherry", 3}
    };
        // 通過(guò)鍵刪除元素
    map.erase("banana");
        // 檢查元素是否存在后刪除
    if (map.find("apple") != map.end()) {
        map.erase("apple");
    }
        for (auto& pair : map) {
        cout << pair.first << ": " << pair.second << endl;
    }
    // 輸出: cherry: 3
}

9. 映射（Map）

map 是一種有序的鍵值對(duì)容器，底層實(shí)現(xiàn)是紅黑樹(shù)。與 unordered_map 不同，它保證鍵的順序，查找、插入和刪除的。

• 特點(diǎn)：
• 保證元素按鍵的順序排列。
• 使用二叉搜索樹(shù)實(shí)現(xiàn)。

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // 輸出 10

10. 集合（Set）

set 是一種用于存儲(chǔ)唯一元素的有序集合，底層同樣使用紅黑樹(shù)實(shí)現(xiàn)。它保證元素不重復(fù)且有序。

• 特點(diǎn)：
• 保證元素的唯一性。
• 元素自動(dòng)按升序排列。

1. 創(chuàng)建和初始化

#include <iostream>
#include <set>
using namespace std;
int main() {
    // 創(chuàng)建空set
    set<int> s1;
        // 初始化列表
    set<int> s2 = {1, 3, 5, 2, 4};
        // 從數(shù)組初始化
    int arr[] = {6, 2, 8, 1, 5};
    set<int> s3(arr, arr + 5);
        // 從vector初始化
    vector<int> vec = {9, 7, 3, 1, 5};
    set<int> s4(vec.begin(), vec.end());
        // 自動(dòng)排序和去重
    set<int> s5 = {3, 1, 4, 1, 5, 9, 2, 6, 5}; 
    // 結(jié)果: 1, 2, 3, 4, 5, 6, 9
        for (int num : s5) {
        cout << num << " ";
    }
    // 輸出: 1 2 3 4 5 6 9
}

2. 增加/插入操作

#include <set>
#include <iostream>
using namespace std;

void insertDemo() {
    set<int> s;
    
    // 方法1: insert(value)
    s.insert(10);
    s.insert(20);
    s.insert(30);
    
    // 方法2: insert(iterator hint, value) - 帶提示插入
    auto hint = s.find(20);
    if (hint != s.end()) {
        s.insert(hint, 25);  // 在20附近插入25
    }
    
    // 方法3: emplace (C++11) - 原地構(gòu)造
    s.emplace(15);
    s.emplace(35);
    
    // 方法4: 插入范圍
    vector<int> new_nums = {5, 12, 18};
    s.insert(new_nums.begin(), new_nums.end());
    
    // 檢查插入結(jié)果
    auto result = s.insert(20);  // 重復(fù)插入
    if (!result.second) {
        cout << "插入失敗，元素已存在" << endl;
    }
    
    // 輸出結(jié)果
    cout << "set元素: ";
    for (int num : s) {
        cout << num << " ";
    }
    // 輸出: 5 10 12 15 18 20 25 30 35
}

3. 刪除操作

#include <set>
#include <iostream>
using namespace std;

void eraseDemo() {
    set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    cout << "原始set: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 方法1: 通過(guò)值刪除
    s.erase(5);  // 刪除元素5
    cout << "刪除5后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 方法2: 通過(guò)迭代器刪除
    auto it = s.find(3);
    if (it != s.end()) {
        s.erase(it);  // 刪除元素3
    }
    cout << "刪除3后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 方法3: 刪除范圍 [first, last)
    auto first = s.find(6);
    auto last = s.find(9);
    if (first != s.end() && last != s.end()) {
        s.erase(first, last);  // 刪除6,7,8 (不包含9)
    }
    cout << "刪除6-8后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 遍歷時(shí)刪除
    for (auto it = s.begin(); it != s.end(); ) {
        if (*it % 2 == 0) {  // 刪除偶數(shù)
            it = s.erase(it);
        } else {
            ++it;
        }
    }
    cout << "刪除偶數(shù)后: ";
    for (int num : s) cout << num << " ";
    cout << endl;
    
    // 清空set
    s.clear();
    cout << "清空后大小: " << s.size() << endl;
}

4. 查找操作

#include <set>
#include <iostream>
using namespace std;

void searchDemo() {
    set<int> s = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    
    // 方法1: find() - 查找元素
    auto it = s.find(50);
    if (it != s.end()) {
        cout << "找到元素: " << *it << endl;
    } else {
        cout << "未找到元素" << endl;
    }
    
    // 方法2: count() - 檢查元素是否存在
    if (s.count(30) > 0) {
        cout << "元素30存在" << endl;
    }
    
    // 方法3: lower_bound() - 第一個(gè) >= value 的元素
    auto lb = s.lower_bound(35);
    if (lb != s.end()) {
        cout << "lower_bound(35): " << *lb << endl;  // 輸出: 40
    }
    
    // 方法4: upper_bound() - 第一個(gè) > value 的元素
    auto ub = s.upper_bound(35);
    if (ub != s.end()) {
        cout << "upper_bound(35): " << *ub << endl;  // 輸出: 40
    }
    
    // 方法5: equal_range() - 返回包含value的范圍
    auto range = s.equal_range(50);
    if (range.first != s.end()) {
        cout << "equal_range(50): [" << *range.first;
        if (range.second != s.end()) {
            cout << ", " << *range.second << ")" << endl;
        }
    }
    
    // 檢查邊界情況
    if (s.find(999) == s.end()) {
        cout << "元素999不存在" << endl;
    }
}

5. 遍歷操作

#include <set>
#include <iostream>
using namespace std;

void traverseDemo() {
    set<string> fruits = {"apple", "banana", "orange", "grape", "kiwi"};
    
    cout << "=== 遍歷方式 ===" << endl;
    
    // 方法1: 迭代器遍歷
    cout << "1. 迭代器遍歷: ";
    for (auto it = fruits.begin(); it != fruits.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 方法2: 反向迭代器
    cout << "2. 反向遍歷: ";
    for (auto rit = fruits.rbegin(); rit != fruits.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // 方法3: 范圍for循環(huán) (C++11)
    cout << "3. 范圍for循環(huán): ";
    for (const auto& fruit : fruits) {
        cout << fruit << " ";
    }
    cout << endl;
    
    // 方法4: 使用auto
    cout << "4. 使用auto: ";
    for (auto& fruit : fruits) {
        cout << fruit << " ";
    }
    cout << endl;
}

6. 容量和大小操作

#include <set>
#include <iostream>
using namespace std;

void capacityDemo() {
    set<int> s = {1, 2, 3, 4, 5};
    
    cout << "set大小: " << s.size() << endl;
    cout << "最大大小: " << s.max_size() << endl;
    cout << "是否為空: " << (s.empty() ? "是" : "否") << endl;
    
    s.insert(6);
    cout << "插入后大小: " << s.size() << endl;
    
    s.erase(1);
    cout << "刪除后大小: " << s.size() << endl;
    
    s.clear();
    cout << "清空后是否為空: " << (s.empty() ? "是" : "否") << endl;
}