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

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

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

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

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

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

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

3.1 動(dòng)態(tài)擴(kuò)展

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

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 手動(dòng)管理容量

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

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 訪問元素

• 隨機(jī)訪問：可以使用索引訪問 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 在競(jìng)賽中的應(yīng)用場(chǎng)景

5.1 動(dòng)態(tài)數(shù)據(jù)存儲(chǔ)

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

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 模擬棧來解決括號(hào)匹配等問題。

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> 來表示鄰接矩陣。以下是一個(gè)示例：

int n = 5; // 頂點(diǎn)個(gè)數(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;
}

6.注意事項(xiàng)

• 性能優(yōu)化：頻繁的動(dòng)態(tài)擴(kuò)展可能會(huì)導(dǎo)致性能下降?？梢栽谝阎笮〉那闆r下提前 reserve() 容量。
• 邊界檢查：at() 提供了安全訪問，但如果對(duì)性能要求高，可以直接使用 [] 操作符。
• 二維 vector：在圖的算法中，盡量選擇合適的數(shù)據(jù)結(jié)構(gòu)以提高代碼效率。

到此這篇關(guān)于C++中std::vector的具體使用的文章就介紹到這了,更多相關(guān)C++ std::vector使用內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！ 

最新評(píng)論