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