如何高效移除C++關(guān)聯(lián)容器中的元素
一、簡(jiǎn)介
關(guān)聯(lián)容器將鍵與值關(guān)聯(lián)起來(lái)，包括：
std::map，具有唯一鍵；std::multimap，可以有幾個(gè)相同的鍵；std::unordered_map，具有唯一鍵的哈希映射；std::unordered_multimap，可以有幾個(gè)相同鍵的哈希映射。
關(guān)聯(lián)容器還包括集合（set）：
std::set，包含唯一元素；std::multiset，包含多個(gè)等價(jià)元素；std::unordered_set，包含唯一元素的哈希集；std::unordered_multiset，包含多個(gè)相同元素的哈希集。
集合包含在關(guān)聯(lián)容器中，因?yàn)樗鼈兛梢员灰暈閷㈡I和值融合到一個(gè)元素中。
二、移除給定位置的元素
如果通過(guò)迭代器位置知道關(guān)聯(lián)容器元素的位置（position），那么從關(guān)聯(lián)容器中刪除元素就非常容易。例如：
// 移除該位置的條目。 a.erase(position); // 刪除第一個(gè)(包括在內(nèi))和最后一個(gè)(不包括在內(nèi))之間的所有元素。 a.erase(first, last);
這時(shí)候，指向被刪除元素的迭代器失效，但指向容器的所有其他迭代器仍然有效。這是關(guān)聯(lián)容器的不同之處。
三、移除與特定鍵值等價(jià)的元素
對(duì)于關(guān)聯(lián)容器，不談?wù)?ldquo;等于特定鍵值”，而是“等價(jià)于特定鍵值”。
如果知道要移除的元素的鍵值，移除操作非常簡(jiǎn)單：
a.erase(myKey);
這將移除所有鍵值與 myKey 等價(jià)的元素（對(duì)于multi容器）。
移除根據(jù)值而不是鍵值標(biāo)識(shí)的元素：如果想移除一個(gè) map （或其multi或哈希對(duì)應(yīng)容器）中根據(jù)值而不是鍵值標(biāo)識(shí)的元素，操作就不那么直觀了。
需要移除所有滿足特定條件的元素，即它們的值等于某個(gè)值。
四、移除滿足特定條件的元素
4.1、與序列容器的結(jié)構(gòu)差異
為了根據(jù)特定條件移除序列容器中的元素，可以使用 std::remove_if。但在這里不能這樣做。
在序列容器中，將要保留的元素向上移動(dòng)是可行的，因?yàn)樗鼈兊闹抵皇前错樞蚺帕械模ㄟ@是序列容器的定義）。
但關(guān)聯(lián)容器有更強(qiáng)的約束：它們需要快速查找鍵值（對(duì)于非哈希容器，時(shí)間復(fù)雜度為 O(log(n))；對(duì)于哈希容器，時(shí)間復(fù)雜度為 O(1)）。為了達(dá)到這個(gè)目的，它們以更復(fù)雜的方式組織數(shù)據(jù)，通常非哈希容器使用樹(shù)，而哈希容器使用表，其中精確的位置很重要。
因此，不能像 std::remove_if 那樣簡(jiǎn)單地重新排列元素，否則會(huì)破壞內(nèi)部結(jié)構(gòu)。所以必須遵循接口。而接口中提供的是上面看到的 erase 方法。
4.2、遵循接口
移除滿足特定條件的元素的一般思路是遍歷容器，對(duì)每個(gè)元素檢查條件，并移除返回 true 的元素。但問(wèn)題是如何在遍歷的同時(shí)移除元素？
考慮一下這種遍歷的樸素版本：
template<typename AssociativeContainer, typename Predicate>
void erase_if(AssociativeContainer& container, Predicate shouldRemove)
{
for (auto it = begin(container); it != end(container); ++it) {
if (shouldRemove(*it)) {
container.erase(it);
}
}
}
注意，這是一種非常罕見(jiàn)的情況，在這種情況下，對(duì)迭代器所知不多，只知道它們是迭代器。這是永遠(yuǎn)不應(yīng)該出現(xiàn)的代碼。
看看上面示例的這一行代碼：
container.erase(it);
這會(huì)使 it 失效。然后看for循環(huán)的結(jié)尾位置：
for (auto it = begin(container); it != end(container); ++it)
在 it 失效后立即執(zhí)行 ++it。這會(huì)導(dǎo)致未定義行為。
4.3、迭代器操作
需要找到一種方法，在移除元素之前遞增迭代器。為此，有幾種選擇。在 C++98 中，可以使用后綴遞增運(yùn)算符，它將首先遞增迭代器，然后將未遞增迭代器的副本傳遞給 erase：
template<typename AssociativeContainer, typename Predicate>
void erase_if(AssociativeContainer& container, Predicate shouldRemove)
{
for (auto it = begin(container); it != end(container);) {
if (shouldRemove(*it))
container.erase(it++);
else
++it;
}
}
但操作迭代器的危險(xiǎn)行同樣非常高。在 C++11 中，得到了一個(gè)風(fēng)險(xiǎn)更小的實(shí)現(xiàn)，因?yàn)?nbsp;erase 返回移除元素后的迭代器?？梢杂眠@種方式重寫(xiě)代碼：
template<typename AssociativeContainer, typename Predicate>
void erase_if(AssociativeContainer& container, Predicate shouldRemove)
{
for (auto it = begin(container); it != end(container);) {
if (shouldRemove(*it))
it = container.erase(it);
else
++it;
}
}
為了確保此函數(shù)僅用于關(guān)聯(lián)容器，C++標(biāo)準(zhǔn)應(yīng)該出現(xiàn)相關(guān)概念，但在此之前，可以顯式地編寫(xiě)各種情況：
namespace details
{
template<typename AssociativeContainer, typename Predicate>
void erase_if_impl(AssociativeContainer& container, Predicate shouldRemove)
{
for (auto it = begin(container); it != end(container); /* nothing here, the increment in dealt with inside the loop */ )
{
if (shouldRemove(*it))
{
it = container.erase(it);
}
else
{
++it;
}
}
}
}
template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::map<Key, Value, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::multimap<Key, Value, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::unordered_map<Key, Value, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::unordered_multimap<Key, Value, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::set<Key, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::multiset<Key, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::unordered_set<Key, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::unordered_multiset<Key, Comparator>& container, Predicate shouldRemove)
{
return details::erase_if_impl(container, shouldRemove);
}
五、總結(jié)
- 移除給定位置的元素： 使用
erase(position)或erase(first, last)方法，可以移除指定位置的元素或指定范圍內(nèi)的元素。 - 移除與特定鍵值等價(jià)的元素： 使用
erase(myKey)方法，可以移除所有鍵值與myKey等價(jià)的元素。 - 移除滿足特定條件的元素： 由于關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)，無(wú)法直接使用
std::remove_if方法移除滿足特定條件的元素。需要使用迭代器并手動(dòng)遍歷容器，檢查每個(gè)元素是否滿足條件，并使用erase方法移除滿足條件的元素。
在移除元素時(shí)，需要注意迭代器失效的問(wèn)題，并使用正確的迭代器操作方式來(lái)避免未定義行為。
本文還提供了 erase_if 函數(shù)的實(shí)現(xiàn)，該函數(shù)可以用于移除關(guān)聯(lián)容器中滿足特定條件的元素。該函數(shù)使用 erase 方法和迭代器操作來(lái)實(shí)現(xiàn)，并針對(duì)不同的關(guān)聯(lián)容器類型進(jìn)行了重載。
以上就是如何高效移除C++關(guān)聯(lián)容器中的元素的詳細(xì)內(nèi)容，更多關(guān)于移除C++關(guān)聯(lián)容器元素的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了c++ 基于opencv 識(shí)別、定位二維碼，幫助大家更好的理解和學(xué)習(xí)使用c++，感興趣的朋友可以了解下2021-03-03
Qt實(shí)戰(zhàn)案例之如何利用QProcess類實(shí)現(xiàn)啟動(dòng)進(jìn)程
這篇文章主要介紹了Qt實(shí)戰(zhàn)案例之如何利用QProcess類實(shí)現(xiàn)啟動(dòng)進(jìn)程,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-02-02
C++實(shí)現(xiàn)數(shù)字轉(zhuǎn)換為十六進(jìn)制字符串的方法
這篇文章主要介紹了C++實(shí)現(xiàn)數(shù)字轉(zhuǎn)換為十六進(jìn)制字符串的方法,涉及C++操作數(shù)字與字符串轉(zhuǎn)換的相關(guān)技巧,需要的朋友可以參考下2015-06-06
本文主要介紹了c語(yǔ)言單詞搜索的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
快速壓縮工具zstd（zstandard）是由facebook開(kāi)源的快速無(wú)損壓縮算法，主要應(yīng)用于zlib級(jí)別的實(shí)時(shí)壓縮場(chǎng)景，并且具有更好的壓縮比。本文將來(lái)講講ZSTD算法的使用，需要的可以參考一下2022-08-08
C語(yǔ)言實(shí)現(xiàn)數(shù)組的循環(huán)左移,右移,翻轉(zhuǎn)的示例
今天小編就為大家分享一篇C語(yǔ)言實(shí)現(xiàn)數(shù)組的循環(huán)左移,右移,翻轉(zhuǎn)的示例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-07-07
這篇文章主要介紹了C 讀取ini文件的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家，讓大家實(shí)現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10
本文給大家講解的是在從C語(yǔ)言過(guò)渡到C++中的引用的區(qū)別及簡(jiǎn)單示例，有需要的小伙伴可以參考下2017-07-07
詳解C++內(nèi)存的代碼區(qū),全局區(qū),棧區(qū)和堆區(qū)
這篇文章主要為大家介紹了C++內(nèi)存的代碼區(qū),全局區(qū),棧區(qū)和堆區(qū)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12
Qt 信號(hào)自定義槽函數(shù)的實(shí)現(xiàn)
Qt中實(shí)現(xiàn)自定義信號(hào)與槽函數(shù)，信號(hào)用于發(fā)送并觸發(fā)槽函數(shù)，槽函數(shù)則是具體的功能實(shí)現(xiàn)，本文就詳細(xì)的介紹一下如何使用，感興趣的可以了解一下2021-11-11