如何高效移除C++關(guān)聯(lián)容器中的元素
一、簡(jiǎn)介
關(guān)聯(lián)容器將鍵與值關(guān)聯(lián)起來，包括：
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ā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ù)，通常非哈希容器使用樹，而哈希容器使用表，其中精確的位置很重要。
因此，不能像 std::remove_if 那樣簡(jiǎn)單地重新排列元素，否則會(huì)破壞內(nèi)部結(jié)構(gòu)。所以必須遵循接口。而接口中提供的是上面看到的 erase 方法。
4.2、遵循接口
移除滿足特定條件的元素的一般思路是遍歷容器，對(duì)每個(gè)元素檢查條件，并移除返回 true 的元素。但問題是如何在遍歷的同時(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);
}
}
}
注意，這是一種非常罕見的情況，在這種情況下，對(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 返回移除元素后的迭代器?？梢杂眠@種方式重寫代碼：
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)概念，但在此之前，可以顯式地編寫各種情況：
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)，無法直接使用
std::remove_if方法移除滿足特定條件的元素。需要使用迭代器并手動(dòng)遍歷容器，檢查每個(gè)元素是否滿足條件，并使用erase方法移除滿足條件的元素。
在移除元素時(shí)，需要注意迭代器失效的問題，并使用正確的迭代器操作方式來避免未定義行為。
本文還提供了 erase_if 函數(shù)的實(shí)現(xiàn)，該函數(shù)可以用于移除關(guān)聯(lián)容器中滿足特定條件的元素。該函數(shù)使用 erase 方法和迭代器操作來實(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++遍歷磁盤驅(qū)動(dòng)器的示例代碼，幫助大家更好的理解和使用c++，感興趣的朋友可以了解下2021-01-01
這篇文章主要介紹了C++中指針的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
以下是對(duì)C++中單鏈表的建立與基本操作進(jìn)行了詳細(xì)的介紹，需要的朋友可以過來參考下，希望對(duì)大家有所幫助2013-10-10
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)簡(jiǎn)單的TCP通信，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
深入了解C++優(yōu)先隊(duì)列(priority_queue)的使用方法
在計(jì)算機(jī)科學(xué)中，優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型，它與隊(duì)列相似，但是每個(gè)元素都有一個(gè)相關(guān)的優(yōu)先級(jí)。C++中的優(yōu)先隊(duì)列是一個(gè)容器適配器(container adapter)，它提供了一種在元素之間維護(hù)優(yōu)先級(jí)的方法。本文帶你深入了解C++優(yōu)先隊(duì)列的使用方法，需要的可以參考下2023-05-05
今天小編就為大家分享一篇關(guān)于C++Primer中變量和基本類型的文章，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2021-08-08
這篇文章主要介紹了C語言strtod()函數(shù)案例詳解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++基礎(chǔ)知識(shí)之運(yùn)算符重載詳解
這篇文章主要為大家詳細(xì)介紹了C++基礎(chǔ)知識(shí)之運(yùn)算符重載，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
c++中string類成員函數(shù)c_str()的用法
c_str()函數(shù)返回一個(gè)指向正規(guī)c字符串的指針,內(nèi)容和string類的本身對(duì)象是一樣的,通過string類的c_str()函數(shù)能夠把string對(duì)象轉(zhuǎn)換成c中的字符串的樣式2013-09-09
C語言 動(dòng)態(tài)內(nèi)存分配的詳解及實(shí)例
這篇文章主要介紹了C語言 動(dòng)態(tài)內(nèi)存分配的詳解及實(shí)例的相關(guān)資料,需要的朋友可以參考下2016-09-09