快捷導(dǎo)航

C++中std::vector的具體使用

更新時間：2025年02月18日 09:53:42 作者：木宇（記得熱愛生活）

C++標(biāo)準(zhǔn)庫中的std::vector是一種動態(tài)數(shù)組容器,適用于算法競賽中的動態(tài)數(shù)據(jù)存儲、數(shù)組擴展和模擬棧/二維數(shù)組等場景,本文就來介紹一下,感興趣的可以了解一下

在 C++ 標(biāo)準(zhǔn)庫中，std::vector 是一個動態(tài)數(shù)組類。相較于靜態(tài)數(shù)組，std::vector 能夠根據(jù)需求自動擴展或縮小，非常適合在算法競賽中使用。在藍(lán)橋杯比賽中，std::vector 常用于存儲動態(tài)數(shù)據(jù)、處理數(shù)組擴展問題，甚至可以代替二維數(shù)組以簡化代碼。

1. std::vector 的基礎(chǔ)概念

std::vector 是一種動態(tài)數(shù)組容器，可以根據(jù)需要動態(tài)調(diào)整大小。其底層實現(xiàn)是連續(xù)的內(nèi)存塊，能夠支持隨機訪問（即通過索引訪問元素）。與普通數(shù)組相比，它不僅支持增刪操作，還能自動擴展容量，從而更靈活。

std::vector 的內(nèi)部機制std::vector 的動態(tài)擴展機制基于 容量（capacity） 的概念。vector 會在內(nèi)部維護一個預(yù)分配的內(nèi)存塊以存儲元素。當(dāng)容量不足時，vector 會自動擴展為原來的 1.5 倍或 2 倍，從而減少頻繁分配內(nèi)存的開銷。

2. 創(chuàng)建 std::vector

在創(chuàng)建 std::vector 時，可以通過不同的方式初始化它：

3. 動態(tài)擴展和容量管理

3.1 動態(tài)擴展

當(dāng)使用 push_back() 向 vector 中添加元素時，如果容量不夠，vector 會自動分配更多的內(nèi)存，重新拷貝現(xiàn)有元素，從而擴展容量。

std::vector<int> vec;
for (int i = 0; i < 10; i++) {
    vec.push_back(i);
    std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
}

3.2 手動管理容量

如果預(yù)先知道 vector 大小，可以使用 reserve() 函數(shù)來分配內(nèi)存，從而避免多次擴展的性能開銷：

std::vector<int> vec;
vec.reserve(10); // 預(yù)分配容量為10
for (int i = 0; i < 10; i++) {
    vec.push_back(i);
}

4. 常用操作和方法

4.1添加和刪除元素

push_back(): 在末尾添加元素
pop_back(): 刪除末尾元素
insert(): 在指定位置插入元素
erase(): 刪除指定位置的元素
clear(): 清空所有元素

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.push_back(6); // {1, 2, 3, 4, 5, 6}
vec.pop_back();   // {1, 2, 3, 4, 5}
vec.insert(vec.begin() + 2, 10); // {1, 2, 10, 3, 4, 5}
vec.erase(vec.begin() + 2); // {1, 2, 3, 4, 5}
vec.clear(); // 清空所有元素，size 為 0

4.2 訪問元素

隨機訪問：可以使用索引訪問 vector 中的元素。
邊界檢查：使用 at() 方法可以提供越界檢查，防止非法訪問。

std::vector<int> vec = {1, 2, 3, 4, 5};
std::cout << vec[0] << std::endl;   // 輸出: 1
std::cout << vec.at(1) << std::endl; // 輸出: 2，帶邊界檢查

4.3 迭代器遍歷

可以使用迭代器來遍歷 vector。使用 begin() 和 end() 可以獲取 vector 的首尾位置。

std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

5. std::vector 在競賽中的應(yīng)用場景

5.1 動態(tài)數(shù)據(jù)存儲

在算法競賽中，我們常常需要存儲未知數(shù)量的數(shù)據(jù)。例如，讀取輸入數(shù)據(jù)時，std::vector 可以輕松地進行動態(tài)擴展：

int n;
std::cin >> n;
std::vector<int> data;

for (int i = 0; i < n; i++) {
    int x;
    std::cin >> x;
    data.push_back(x);
}

// 輸出所有數(shù)據(jù)
for (int x : data) {
    std::cout << x << " ";
}

5.2 模擬棧結(jié)構(gòu)

std::vector 提供的 push_back() 和 pop_back() 操作，與棧的數(shù)據(jù)結(jié)構(gòu)操作類似，因此可以用 vector 模擬棧來解決括號匹配等問題。

std::string s = "((()))";
std::vector<char> stack;

for (char c : s) {
    if (c == '(') {
        stack.push_back(c);
    } else if (!stack.empty() && stack.back() == '(') {
        stack.pop_back();
    }
}

if (stack.empty()) {
    std::cout << "匹配成功！" << std::endl;
} else {
    std::cout << "匹配失?。? << std::endl;
}

5.3 模擬二維數(shù)組

在圖的算法中，可以用 std::vector<std::vector> 來表示鄰接矩陣。以下是一個示例：

int n = 5; // 頂點個數(shù)
std::vector<std::vector<int>> graph(n, std::vector<int>(n, 0));

// 添加邊
graph[0][1] = 1;
graph[1][2] = 1;
graph[2][3] = 1;
graph[3][4] = 1;

// 輸出鄰接矩陣
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        std::cout << graph[i][j] << " ";
    }
    std::cout << std::endl;
}