C++ STL容器操作:6種常用場景算法
[TOC]
引言
? 在日常軟件開發(fā)工作中,容器操作如查找眠菇、排序袱衷、和元素替換等任務(wù)極為常見致燥。幸運(yùn)的是,C++的標(biāo)準(zhǔn)化利器——STL(Standard Template Library断傲,標(biāo)準(zhǔn)模板庫)為我們封裝了一系列高效且靈活的算法认罩,極大簡化了這些操作续捂。特別是自C++11版本以來牙瓢,STL引入了一批新晉的通用算法矾克,它們不僅功能強(qiáng)大,而且設(shè)計(jì)得更加人性化差购,旨在進(jìn)一步提升我們的編碼效率與程序性能欲逃。本文列舉一些常用到的方法稳析,便于日后回顧和查閱彰居。
概述
? 日常開發(fā)中的容器操作撰筷,如查找毕籽、刪除关筒、排序蒸播、分割萍肆、拷貝和合并塘揣,均可借助STL中的精選算法高效完成勿负。本文將概覽這些核心STL算法,助力開發(fā)流程優(yōu)化铁孵。
查找與計(jì)數(shù)
std::find
- 作用: 找容器中第一個(gè)匹配給定值的元素
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
DumpVector("testArrgs", testArrgs);
auto find = std::find(testArrgs.begin(), testArrgs.end(), "XiaoMing");
if (find != testArrgs.end()) {
SPR_LOGD("find: dest = \"XiaoMing\", result = %s, index = %ld\n", find->c_str(), find - testArrgs.begin());
}
- 結(jié)果
D: find: dest = "XiaoMing", result = XiaoMing, index = 2
std::find_if
- 作用: 查找容器中第一個(gè)滿足謂詞條件的元素
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
auto findIf = std::find_if(testArrgs.begin(), testArrgs.end(), [](const std::string &str) { return str.find("Ming") != std::string::npos; });
if (findIf != testArrgs.end()) {
SPR_LOGD("find_if: dest = \"Ming\", result = %s, index = %ld\n", findIf->c_str(), findIf - testArrgs.begin());
}
③ 結(jié)果
D: find_if: dest = "Ming", result = XiaoMing, index = 2
std::find_if_not
- 作用: 尋找第一個(gè)不符合指定條件的元素
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
auto findIfNot = std::find_if_not(testArrgs.begin(), testArrgs.end(), [](const std::string &str) { return str.find("Xiao") != std::string::npos; });
if (findIfNot != testArrgs.end()) {
SPR_LOGD("find_if_not: dest = \"Xiao\", result = %s, index = %ld\n", findIfNot->c_str(), findIfNot - testArrgs.begin());
}
- 結(jié)果
D: find_if_not: dest = "Xiao", result = LiHua, index = 1
std::find_end
- 作用: 查找一個(gè)子序列最后一次出現(xiàn)的位置
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> subArrgs1 = {"XiaoMing", "XiaoHong"};
auto findEnd = std::find_end(testArrgs.begin(), testArrgs.end(), subArrgs1.begin(), subArrgs1.end());
if (findEnd != testArrgs.end()) {
SPR_LOGD("find_end: dest = {\"XiaoMing\", \"XiaoHong\"}, result = %s, index = %ld\n", findEnd->c_str(), findEnd - testArrgs.begin());
}
- 結(jié)果
D: find_end: dest = {"XiaoMing", "XiaoHong"}, result = XiaoMing, index = 3
std::find_first_of
- 作用: 查找序列中任何一個(gè)元素首次出現(xiàn)的位置
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> subArrgs2 = {"JianGuo"};
auto findFirstOf = std::find_first_of(testArrgs.begin(), testArrgs.end(), subArrgs2.begin(), subArrgs2.end());
if (findFirstOf != testArrgs.end()) {
SPR_LOGD("find_first_of: dest = {\"JianGuo\"}, result = %s, index = %ld\n", findFirstOf->c_str(), findFirstOf - testArrgs.begin());
}
- 結(jié)果
D: find_first_of: dest = {"JianGuo"}, result = JianGuo, index = 5
std::adjacent_find
- 作用: 查找相鄰重復(fù)的元素
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
auto adjacentFind = std::adjacent_find(testArrgs.begin(), testArrgs.end(), [](const std::string &str1, const std::string &str2) { return str1 == str2; });
if (adjacentFind != testArrgs.end()) {
SPR_LOGD("adjacent_find: result = %s, index = %ld\n", adjacentFind->c_str(), adjacentFind - testArrgs.begin());
}
- 結(jié)果
D: adjacent_find: result = XiaoMing, index = 2
std::count
- 作用: 計(jì)算容器中指定值出現(xiàn)的次數(shù)
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
auto cnt = std::count(testArrgs.begin(), testArrgs.end(), "XiaoFang");
if (cnt > 0) {
SPR_LOGD("count: dest = \"XiaoFang\", result = %ld\n", cnt);
}
- 結(jié)果
D: count: dest = "XiaoFang", result = 1
std::count_if
- 作用: 計(jì)算滿足謂詞條件的元素?cái)?shù)量
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
auto cntIf = std::count_if(testArrgs.begin(), testArrgs.end(), [](const std::string &str) { return str.find("Xiao") != std::string::npos; });
if (cntIf > 0) {
SPR_LOGD("count_if: dest = \"Xiao\", result = %ld\n", cntIf);
}
- 結(jié)果
D: count_if: dest = "Xiao", result = 6
移除與替換
std::remove
- 作用: 重新排列容器元素岖沛,使得所有不匹配特定值的元素被放置在容器的前端婴削。配合
earse
實(shí)現(xiàn)移除不匹配元素唉俗。 - 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> rmArrgs(testArrgs);
auto remove = std::remove(rmArrgs.begin(), rmArrgs.end(), "XiaoMing");
if (remove != rmArrgs.end()) {
rmArrgs.erase(remove, rmArrgs.end());
DumpVector("rmArrgs", rmArrgs);
}
- 結(jié)果
D: rmArrgs: "XiaoFang", "LiHua", "XiaoHong", "JianGuo", "XiaoFangFang",
std::remove_if
- 作用: 重新排列容器元素虫溜,使得所有不滿足謂詞條件的元素被放置在容器的前端衡楞。配合
earse
實(shí)現(xiàn)移除不匹配元素敦姻。 - 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> rmIfArrgs(testArrgs);
auto removeIf = std::remove_if(rmIfArrgs.begin(), rmIfArrgs.end(), [](const std::string &str) { return str.find("Xiao") != std::string::npos; });
if (removeIf != rmIfArrgs.end()) {
rmIfArrgs.erase(removeIf, rmIfArrgs.end());
DumpVector("rmArrgs", rmArrgs);
}
- 結(jié)果
D: rmIfArrgs: "XiaoFang", "LiHua", "XiaoHong", "JianGuo", "XiaoFangFang"
std::remove_copy
- 作用: 從源序列拷貝元素到目標(biāo)序列寄雀,排除滿足條件的元素陨献。
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> dstArrgs;
vector<std::string> rcArrgs(testArrgs);
std::remove_copy(rcArrgs.begin(), rcArrgs.end(), std::back_inserter(dstArrgs), "XiaoMing");
DumpVector("dstArrgs", dstArrgs);
- 結(jié)果
D: dstArrgs: "XiaoFang", "LiHua", "XiaoHong", "JianGuo", "XiaoFangFang"
std::replace
- 作用: 將所有出現(xiàn)的指定元素替換為新值。
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> rpArrgs(testArrgs);
std::replace(rpArrgs.begin(), rpArrgs.end(), "XiaoMing", "MingMing");
DumpVector("rpArrgs", rpArrgs);
- 結(jié)果
D: rpArrgs: "XiaoFang", "LiHua", "MingMing", "MingMing", "XiaoHong", "JianGuo", "XiaoFangFang", "MingMing",
std::replace_if
- 作用: 滿足謂詞條件的元素,替換為指定的替換值慷暂。
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> rpIfArrgs(testArrgs);
std::replace_if(rpIfArrgs.begin(), rpIfArrgs.end(), [](const std::string &str) { return (str == "XiaoFang"); }, "FangFang");
DumpVector("rpIfArrgs", rpIfArrgs);
- 結(jié)果
D: rpIfArrgs: "FangFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing",
std::replace_copy
- 作用:用于在指定范圍內(nèi)將所有匹配某個(gè)值的元素替換為另一個(gè)值行瑞,拷貝到另一個(gè)的容器中餐禁。
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> rpCpDstArrgs;
vector<std::string> rpCopyArrgs(testArrgs);
std::replace_copy(rpCopyArrgs.begin(), rpCopyArrgs.end(), std::back_inserter(rpCpDstArrgs), "XiaoMing", "MingMing");
DumpVector("rpCpDstArrgs", rpCpDstArrgs);
- 結(jié)果
D: rpCpDstArrgs: "XiaoFang", "LiHua", "MingMing", "MingMing", "XiaoHong", "JianGuo", "XiaoFangFang", "MingMing"
std::swap
- 作用:交換兩個(gè)變量的值氧吐。
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
vector<std::string> swapSrcArrgs(testArrgs);
vector<std::string> swapDstArrgs = {"Vince Carter", "Rose", "James"};
std::swap(swapSrcArrgs, swapDstArrgs);
DumpVector("swapSrcArrgs", swapSrcArrgs);
DumpVector("swapDstArrgs", swapDstArrgs);
- 結(jié)果
D: swapSrcArrgs: "Vince Carter", "Rose", "James",
D: swapDstArrgs: "XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing",
排序與組織
std::sort
- 作用:對容器元素進(jìn)行排序筑舅。
- 示例
vector<std::string> testArrgs = {"XiaoFang", "LiHua", "XiaoMing", "XiaoMing", "XiaoHong", "JianGuo", "XiaoFangFang", "XiaoMing"};
// sort
vector<std::string> sortArrgs(testArrgs);
std::sort(sortArrgs.begin(), sortArrgs.end());
DumpVector("sortArrgs", sortArrgs);
std::sort(sortArrgs.begin(), sortArrgs.end(), [](const std::string &str1, const std::string &str2) { return str1.size() > str2.size(); });
DumpVector("sortArrgs", sortArrgs);
- 結(jié)果
D: sortArrgs: "JianGuo", "LiHua", "XiaoFang", "XiaoFangFang", "XiaoHong", "XiaoMing", "XiaoMing", "XiaoMing",
D: sortArrgs: "XiaoFangFang", "XiaoFang", "XiaoHong", "XiaoMing", "XiaoMing", "XiaoMing", "JianGuo", "LiHua",
std::stable_sort
- 作用:穩(wěn)定排序翠拣,保持相等元素的原有順序心剥。
- 示例
// stable_sort
vector<Persion> srcPersions = {{"LiWei", 18}, {"LiHua", 20}, {"ZhangLei", 19}, {"WeiGuo", 19}, {"ZhenHua", 20}, {"JianGuo", 18}, {"ZhiGuo", 19}, {"JianHua", 19}};
vector<Persion> sPersions(srcPersions);
std::stable_sort(sPersions.begin(), sPersions.end(), [](const Persion &p1, const Persion &p2) { return p1.age > p2.age; });
DumpVector("sPersions", sPersions);
std::stable_sort(sPersions.begin(), sPersions.end(), [](const Persion &p1, const Persion &p2) { return p1.age < p2.age; });
DumpVector("sPersions", sPersions);
- 結(jié)果
D: sPersions = { {"LiHua", 20}, {"ZhenHua", 20}, {"ZhangLei", 19}, {"WeiGuo", 19}, {"ZhiGuo", 19}, {"JianHua", 19}, {"LiWei", 18}, {"JianGuo", 18}, }
D: sPersions = { {"LiWei", 18}, {"JianGuo", 18}, {"ZhangLei", 19}, {"WeiGuo", 19}, {"ZhiGuo", 19}, {"JianHua", 19}, {"LiHua", 20}, {"ZhenHua", 20}, }
std::partial_sort
- 作用:對部分區(qū)間排序优烧。
- 示例
vector<Persion> srcPersions = {{"LiWei", 18}, {"LiHua", 20}, {"ZhangLei", 19}, {"WeiGuo", 19}, {"ZhenHua", 20}, {"JianGuo", 18}, {"ZhiGuo", 19}, {"JianHua", 19}};
// partial_sort
vector<Persion> prtPersions(srcPersions);
vector<Persion> sortPersions(srcPersions);
std::partial_sort(prtPersions.begin(), prtPersions.begin() + 5, prtPersions.end(), [](const Persion &p1, const Persion &p2) { return p1.age > p2.age; });
std::sort(sortPersions.begin(), sortPersions.begin() + 5, [](const Persion &p1, const Persion &p2) { return p1.age > p2.age; });
DumpVector("prtPersions", prtPersions);
DumpVector("sortPersions", sortPersions);
- 結(jié)果
D: prtPersions = { {"ZhenHua", 20}, {"LiHua", 20}, {"WeiGuo", 19}, {"ZhiGuo", 19}, {"ZhangLei", 19}, {"JianGuo", 18}, {"LiWei", 18}, {"JianHua", 19}, }
D: sortPersions = { {"LiHua", 20}, {"ZhenHua", 20}, {"ZhangLei", 19}, {"WeiGuo", 19}, {"LiWei", 18}, {"JianGuo", 18}, {"ZhiGuo", 19}, {"JianHua", 19}, }
std::reverse
- 作用:對部分區(qū)間排序。
- 示例
vector<Persion> srcPersions = {{"LiWei", 18}, {"LiHua", 20}, {"ZhangLei", 19}, {"WeiGuo", 19}, {"ZhenHua", 20}, {"JianGuo", 18}, {"ZhiGuo", 19}, {"JianHua", 19}};
// reverse
vector<Persion> rPersions(srcPersions);
std::reverse(rPersions.begin(), rPersions.end());
DumpVector("rPersions", rPersions);
- 結(jié)果
D: rPersions = { {"JianHua", 19}, {"ZhiGuo", 19}, {"JianGuo", 18}, {"ZhenHua", 20}, {"WeiGuo", 19}, {"ZhangLei", 19}, {"LiHua", 20}, {"LiWei", 18}, }
std::rotate
- 作用:對部分區(qū)間排序熙卡。
- 示例
vector<Persion> srcPersions = {{"LiWei", 18}, {"LiHua", 20}, {"ZhangLei", 19}, {"WeiGuo", 19}, {"ZhenHua", 20}, {"JianGuo", 18}, {"ZhiGuo", 19}, {"JianHua", 19}};
// rotate
vector<Persion> rtPersions(srcPersions);
std::rotate(rtPersions.begin(), rtPersions.begin() + 3, rtPersions.end());
DumpVector("rtPersions", rtPersions);
- 結(jié)果
D: rPersions = { {"JianHua", 19}, {"ZhiGuo", 19}, {"JianGuo", 18}, {"ZhenHua", 20}, {"WeiGuo", 19}, {"ZhangLei", 19}, {"LiHua", 20}, {"LiWei", 18}, }
分割
std::partition
- 作用:分割容器驳癌,使?jié)M足謂詞的元素在前颓鲜,不滿足的在后甜滨。
- 示例
vector<std::string> testArrgs = {"LiHua", "ZhangHong", "HeDa", "LiWei", "ZhangLei", "WeiGuo", "ZhenHua"};
// partition
vector<std::string> partArrgs(testArrgs);
std::partition(partArrgs.begin(), partArrgs.end(), [](const std::string& str) { return (str.compare(0, 5, "Zhang") == 0); });
DumpVector("partArrgs", partArrgs);
- 結(jié)果
D: partArrgs: "ZhangLei", "ZhangHong", "HeDa", "LiWei", "LiHua", "WeiGuo", "ZhenHua",
std::stable_partition
- 作用:類似partition衣摩,但保持相同元素的相對順序不變艾扮。
- 示例
vector<std::string> testArrgs = {"LiHua", "ZhangHong", "HeDa", "LiWei", "ZhangLei", "WeiGuo", "ZhenHua"};
// stable_partition
vector<std::string> stPartArrgs(testArrgs);
std::stable_partition(stPartArrgs.begin(), stPartArrgs.end(), [](const std::string& str) { return (str.compare(0, 5, "Zhang") == 0); });
DumpVector("stPartArrgs", stPartArrgs);
- 結(jié)果
D: stPartArrgs: "ZhangHong", "ZhangLei", "LiHua", "HeDa", "LiWei", "WeiGuo", "ZhenHua",
拷貝與生成
std::copy
- 作用:拷貝容器或范圍內(nèi)的元素到另一位置栏渺。
- 示例
vector<std::string> srcArrgs = {"LiHua", "ZhangHong", "HeDa", "LiWei", "ZhangLei", "WeiGuo", "ZhenHua"};
// copy
vector<std::string> dstCopyArrgs;
std::copy(srcArrgs.begin(), srcArrgs.end(), std::back_inserter(dstCopyArrgs));
DumpVector("dstCopyArrgs", dstCopyArrgs);
- 結(jié)果
D: dstCopyArrgs: "LiHua", "ZhangHong", "HeDa", "LiWei", "ZhangLei", "WeiGuo", "ZhenHua",
std::copy_if
- 作用:根據(jù)謂詞條件拷貝元素磕诊。
- 示例
vector<std::string> srcArrgs = {"LiHua", "ZhangHong", "HeDa", "LiWei", "ZhangLei", "WeiGuo", "ZhenHua"};
// copy_if
vector<std::string> dstCopyIfArrgs;
std::copy_if(srcArrgs.begin(), srcArrgs.end(), std::back_inserter(dstCopyIfArrgs), [](const std::string& str) { return (str.compare(0, 5, "Zhang") == 0); });
DumpVector("dstCopyIfArrgs", dstCopyIfArrgs);
- 結(jié)果
D: dstCopyIfArrgs: "ZhangHong", "ZhangLei",
std::copy_n
- 作用:拷貝指定數(shù)量的元素霎终。
- 示例
vector<std::string> srcArrgs = {"LiHua", "ZhangHong", "HeDa", "LiWei", "ZhangLei", "WeiGuo", "ZhenHua"};
// copy_n
vector<std::string> dstCopyNArrgs;
std::copy_n(srcArrgs.begin(), 3, std::back_inserter(dstCopyNArrgs));
DumpVector("dstCopyNArrgs", dstCopyNArrgs);
- 結(jié)果
D: dstCopyNArrgs: "LiHua", "ZhangHong", "HeDa",
std::generate
- 作用:使用生成器函數(shù)填充容器莱褒。
- 示例
// generate
vector<std::string> genArrgs(5);
std::generate(genArrgs.begin(), genArrgs.end(), [](){ return "Hello"; });
DumpVector("genArrgs", genArrgs);
- 結(jié)果
D: genArrgs: "Hello", "Hello", "Hello", "Hello", "Hello",
std::generate_n
- 作用:生成指定數(shù)量的元素填充容器广凸。
- 示例
// generate_n
vector<std::string> genNArrgs;
std::generate_n(std::back_inserter(genNArrgs), 3, [](){ return "Hello"; });
DumpVector("genNArrgs", genNArrgs);
- 結(jié)果
D: genNArrgs: "Hello", "Hello", "Hello",
集合操作
std::merge
- 作用:生成指定數(shù)量的元素填充容器谅海。
- 示例
vector<std::string> srcArrgs = {"Vince Carter", "Rose", "James"};
// merge
vector<std::string> mergeArrgs;
vector<std::string> tmpArrgs = {"Irving"};
std::merge(srcArrgs.begin(), srcArrgs.end(), tmpArrgs.begin(), tmpArrgs.end(), std::back_inserter(mergeArrgs));
DumpVector("mergeArrgs", mergeArrgs);
- 結(jié)果
D: mergeArrgs: "Irving", "Vince Carter", "Rose", "James",
std::inplace_merge
- 作用:就地歸并兩個(gè)有序范圍扭吁。
- 示例
vector<std::string> srcArrgs = {"Vince Carter", "Rose", "James"};
// inplace_merge
vector<std::string> inplaceMergeArrgs(srcArrgs);
std::inplace_merge(inplaceMergeArrgs.begin(), inplaceMergeArrgs.begin() + 2, inplaceMergeArrgs.end());
DumpVector("inplaceMergeArrgs", inplaceMergeArrgs);
- 結(jié)果
D: inplaceMergeArrgs: "James", "Vince Carter", "Rose",