[[413003]]

整理了一下 CPP 做算法題時常用的容器技巧。遇到一門新語言時，我首先都會思考如何實現(xiàn)下屬功能。關(guān)于算法的筆記放在 GitHub[1] 上。

定長數(shù)組

• 數(shù)組

變長數(shù)組

• vector

哈希表

• 有序字典

優(yōu)先隊列

• 優(yōu)先隊列重載

排序

• 排序返回索引

定長數(shù)組

要求：

• 聲明與取數(shù)

數(shù)組

int dx[4] = {0, 1, 0, -1}; 
int a[N]; 
 
dx[0]; 

變長數(shù)組

要求：

• 取值：取頭取尾取索引
• 追加
• 掐頭去尾

vector

vector<int> ans(n);  // 初始長度 n ，默認(rèn)值為 0 
 
// 取值：取頭取尾取索引 
ans.front(); 
ans.back(); 
ans[i] += 1; 
 
// 追加 
// 為什么 std::vector 不支持 push_front？ - Milo Yip的回答 - 知乎 
// https://www.zhihu.com/question/51555037/answer/126373709 
ans.push_back(5);  // O(1) 
 
// 去尾 
ans.pop_back(); 

哈希表

要求：

• 鍵值已存在
• 有序字典

map<int, int> S; 
// 鍵值已存在 
if (S.count(5)) 
    // S[5] 被定義過 
else 
    // S[5] 未被定義過 

有序字典

• map 有序，基于紅黑樹
• unordered_map 無序，基于映射，效率可能更高

優(yōu)先隊列

要求：

• 空尺看存彈
• 重載存儲對象
• 重載比較函數(shù)

// 默認(rèn)是大根堆 
priority_queue<int> heap; 
 
// 改為小根堆 
priority_queue<int, vetor<int>, greater<int> > min_heap; 
 
// 空尺看存彈 
heap.empty(); 
heap.size(); 
heap.top(); 
heap.push(5); 
heap.pop(); 

優(yōu)先隊列重載

// 重載比較函數(shù) 
struct cmp { 
    template<typename T, typename U> 
    bool operator()(T const& left, U const &right) { 
        if (left.second < right.second) return true; 
        return false; 
    } 
}; 
 
int main() { 
    unordered_map<int, int> mp; 
    mp[3] = 4; 
    mp[2] = 44; 
    mp[12] = 432; 
    // 重載存儲對象 pair<int, int> 
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>  pq(mp.begin(), mp.end());  //完成pq的初始化 
} 
 
// 版權(quán)聲明：本文為CSDN博主「leagalhigh」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。 
// 原文鏈接：https://blog.csdn.net/u014257954/article/details/78623215 

排序

要求：

• 重載排序規(guī)則
• 排序返回索引

vector<int> ans; 
sort(ans.begin(), ans.end());  // 默認(rèn)從小到大 
 
vector<pair<int, int>> res; 
sort(res.begin(), res.begin());  // 默認(rèn)比較第一個元素 

排序返回索引

vector<int> data = {5, 16, 4, 7};    
vector<int> index(data.size(), 0); 
for (int i = 0 ; i != index.size() ; i++) { 
    index[i] = i; 
} 
sort(index.begin(), index.end(), 
    [&](const int& a, const int& b) { 
        return (data[a] < data[b]); 
    } 
); 
for (int i = 0 ; i != index.size() ; i++) { 
    cout << index[i] << endl; 
} 
// 版權(quán)聲明：本文為CSDN博主「liangbaqiang」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。 
// 原文鏈接：https://blog.csdn.net/qq_36523492/article/details/114122256 

參考資料

[1]算法的筆記: https://github.com/PiperLiu/ACMOI_Journey