为什么std::map::erase(iterator it)是分期常量？

std::map::erase(iterator it)是分期常量的原因是为了保证操作的时间复杂度为O(logN)。

在std::map中，元素是按照键值有序存储的，使用红黑树实现。当调用erase(iterator it)函数时，需要删除指定迭代器所指向的元素。由于红黑树的特性，删除一个节点可能会导致整个树的结构发生变化，需要进行平衡操作，以保持树的平衡性。

为了保证操作的时间复杂度为O(logN)，std::map::erase(iterator it)函数将删除操作分为两个阶段：标记和删除。在标记阶段，被删除节点的颜色会被标记为“删除”，但实际上并不会立即删除节点。在删除阶段，会根据需要进行平衡操作，最终删除节点并释放内存。

这种分期常量的设计可以保证删除操作的时间复杂度为O(logN)，但也意味着在调用erase函数后，被删除节点的内存并不会立即释放，直到整个删除过程完成才会释放。因此，std::map::erase(iterator it)是分期常量。

推荐的腾讯云相关产品：腾讯云数据库TencentDB、腾讯云云服务器CVM、腾讯云容器服务TKE。

腾讯云数据库TencentDB：https://cloud.tencent.com/product/cdb 腾讯云云服务器CVM：https://cloud.tencent.com/product/cvm 腾讯云容器服务TKE：https://cloud.tencent.com/product/tke

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

STL开发之迭代器（Iterator）

需要注意的是虽然指针是迭代器的一种形式，但并非所有迭代器都具有指针的相同功能。...常量正向迭代器：定义方式为：容器名::const_iterator。不可改变指向的元素的值。...常量反向迭代器：定义方式为：容器名::const_reverse_iterator下面的例子就通过常量反向迭代器遍历容器中的元素。...见如下代码： int main () { std::map mymap; std::map::iterator it; // insert some values...} 如上代码所示，可以解决map迭代器失效的问问题。

7321 0

C++ map和unordered_map详解

map的使用方法头文件：include 下面的代码中都包含了std：using namespace std; 创建map对象 // Method1 map map1...crbegin 返回常量迭代器逆序的第一个元素的迭代器 crend 返回常量迭代器逆序的最后一个元素的迭代器 int main() { mapmap1; map1...的结果 pair的第二个内容是upper_bound的结果 find用法如下： map::iterator it; it = map1.find('b'); cout 创建map对象 typedef unordered_map strIntMap...end 返回指向迭代器最后一个元素的迭代器 cbegin 返回常量迭代器的第一个元素的迭代器 cend 返回常量迭代器的最第一个元素的迭代器用法跟map是一样的，这里不再举例了 Capacity

2.8K2 0

C++认识容器的迭代器

所以，在删除一个元素的时候，是没有什么问题的。即： for(map::iterator it=countMap.begin();it!...map::iterator nextIt=countMap.begin(); for(map::iterator it=countMap.begin()...再者map.erase()返回指向紧接着被删除元素的下一个元素的迭代器，所以可以实现如下： for(map::iterator it=countMap.begin();it!...的交换的时间复杂度是常量级，一般情况下，拷贝带来的时间开销会大于删除指定元素的时间开销，并且临时map容器也增加了空间的开销。...Iterator的自增方法其实就是增加内部的一个索引值。判断！=的方法是和另外一个迭代器做比较，这个迭代器一般是集合的末尾，当我们的索引值等于末尾的索引值end时，认为迭代器已经达到了末尾。

1.2K1 0

C++ 认识容器的迭代器

所以，在删除一个元素的时候，是没有什么问题的。即： for(map::iterator it=countMap.begin(); it!...再者 map.erase() 返回指向紧接着被删除元素的下一个元素的迭代器，所以可以实现如下： for(map::iterator it=countMap.begin();it!...的交换的时间复杂度是常量级，一般情况下，拷贝带来的时间开销会大于删除指定元素的时间开销，并且临时map容器也增加了空间的开销。...: std::string str[10]; }; 我们定义了个内部的嵌套类Iterator,并为它重载了++、*、！...Iterator的自增方法其实就是增加内部的一个索引值。判断！=的方法是和另外一个迭代器做比较，这个迭代器一般是集合的末尾，当我们的索引值等于末尾的索引值end时，认为迭代器已经达到了末尾。

6012 0

再探 setmap

} void erase(iterator position) { typedef typename rep_type::iterator rep_iterator; t.erase...((rep_iterator&)position); } size_type erase(const key_type& x) { return t.erase(x);...> using namespace std; struct cmp { /* 这里将函数设置为常量函数，不然会报错： “const cmp”的表达式会丢失一些 const...2、map和set的增删改查速度为都是logn，是比较高效的。 ---- 为什么 set 的底层不用hash？ 1、用，干嘛不用。用完改名字了，叫 unordered_set。...std; /// map默认是从小到大排列，以下是让map从大到小排列 template struct greator { bool operator()(const

6862 0

STL之关联式容器map(二)

\n"; 4.获取元素获取 map 容器的开始和结束迭代器以及反向迭代器，它们都可以访问容器中的所有元素。 map 的成员函数 at() 返回的是参数键对应的对象。...6删除元素 map 的成员函数 erase() 可以移除键和参数匹配的元素，然后返回所移除元素的个数。...<< " was not found" << std::endl; map 容器的返回值只可能是 0 或 1，0 表明元素不在容器中。...也可以用指向删除元素的迭代器作为 erase() 的参数。这种情况下，返回的迭代器指向被删除元素的下一个位置。这个参数必须是容器中的有效迭代器，不能是结束迭代器。...auto iter = people.erase(++std::begin(people), --std::end(people));//Erase all except 1st & last 返回的迭代器指向这段元素中最后一个被删除的元素

5512 0

C++ STL之set的基本操作

set是集合，虽然也存在键值和实值，不过两者根本就是同一个值，键值的设置完全就是为了满足红黑树的底层结构，set操作与map很像不过也有些不同。...1、 set迭代器与map的不同： (1)set使用接引用运算符*取值，而map使用first和second取值。...(2)set的迭代器都是常量迭代器，不能用来修改所指向的元素，而map的迭代器是可以修改所指向元素的。...namespace std; 4 void print(setset_int) 5 { 6 set::iterator it=set_int.begin(); 7...(value) 移除set容器内元素值为value的所有元素，返回移除的元素个数 33 //2,void erase(&pos) 移除pos位置上的元素，无返回值 34 //3,void erase

2.9K5 0

【C++】STL 容器 - vector 动态数组容器 ⑧ ( vector 容器添加删除元素 | clear 函数 | insert 函数 | erase 函数 )

函数 iterator 迭代器类的 erase 函数删除指定索引位置的元素 ; iterator#erase() 函数原型如下 : iterator erase( const_iterator...pos ); 该 erase() 函数接受一个指向要删除的元素的常量迭代器作为参数 , 返回一个指向被删除元素之后元素的迭代器 ; 注意 : 返回的是新的迭代器 , 需要重新使用变量接收该迭代器...函数 iterator 迭代器类的 erase 函数删除指定范围区间的元素 ; 注意 : 迭代器范围是一个前闭后开区间 , 下面的代码只能删除 2 个元素 , 即第一个和第二个元素...; // 删除容器中第一个和第二个元素 vec.erase(vec.begin(), vec.begin() + 2); iterator#erase() 函数原型如下 : iterator...erase( const_iterator first, const_iterator last ); iterator#erase() 函数接受两个指向要删除的元素的常量迭代器作为参数 , 返回一个指向被删除元素范围的结束位置之后的迭代器

2.8K1 1

c++ 迭代器失效_c++迭代器是什么

正向迭代器，定义方法如下：容器类名::iterator 迭代器名; 常量正向迭代器，定义方法如下：容器类名::const_iterator 迭代器名; 反向迭代器，定义方法如下：容器类名:...:reverse_iterator 迭代器名; 常量反向迭代器，定义方法如下：容器类名::const_reverse_iterator 迭代器名; 1.3 迭代器的使用通过迭代器可以读取它指向的元素...；这是因为vetor,deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置，此时 iter 已经指向的是未知内存；解决方法是利用 erase方法可以返回下一个有效的 iterator...---- 节点式容器：关联式容器(如map, set,multimap,multiset) （1）删除当前的iterator，仅仅会使当前的iterator失效，只要在erase 时，递增当前 iterator...链表式容器(如list) （1）删除当前的iterator，仅仅会使当前的iterator失效，只要在erase 时，递增当前 iterator erase(iter++)或者利用 erase 返回的有效迭代器

1.1K4 0

深入浅出list容器

// erase 模拟实现 iterator erase(iterator pos) { assert(pos != end()); Node* prev = pos....容器：std::forward_list, std::unordered_map, std::unordered_set, std::unordered_multimap, std::unordered_multiset...std::forward_list fl = {1, 2, 3}; auto it = fl.begin(); // it 是单向迭代器 while (it !...容器：std::list, std::map, std::set, std::multimap, std::multiset std::list lst = {1, 2, 3}; auto it...这些参数允许用户根据需要定制迭代器的行为，例如是否允许修改数据（通过 Ref）或者返回常量或非常量指针（通过 Ptr），由此可以实例化出list_iterator和const_list_iterator

711 0

C++常见避坑指南

_CONSTEXPR20 iterator erase(const_iterator _First, const_iterator _Last) noexcept( is_nothrow_move_assignable_v...可以利用erase迭代器接口返回的是下一个有效的迭代器，或者将当前的迭代器指向下一个erase(iter++)。...值得一提的是，在最新的C++11标准中，已经新增了一个map::erase函数执行后会返回下一个元素的iterator，因此可以使用erase的返回值获取下一个有效的迭代器。...在实现上有两种模板，其一是通过 erase 获得下一个有效的 iterator，使用于序列式迭代器和链表式迭代器(C++11开始关联式迭代器也可以使用) for (auto it = elements.begin...，但是因为类型错了还是会发生拷贝，std::map 中的键值对是以 std::pair 的形式存储的，其中key是常量。

4531 0

C++(STL):31 ---关联式容器map源码剖析

由于RB-tree是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的STL map是以RB-tree为底层机制又由于map所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的map操作行为...，都只是转调用RB-tree的操作行为而已下面是map的结构： ?...iterator; //注意上面一行，map不像set，map使用的是RB-tree的iterator typedef typename _Rep_type::const_iterator const_iterator...*/ void erase(iterator __position) { _M_t.erase(__position); } size_type erase(const key_type& __x...) { return _M_t.erase(__x); } void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last

1.4K1 0

C++初阶：适合新手的手撕vector（模拟实现vector）

这里假设 T 是一个类或者结构体，那么这个语句会调用 T 的默认构造函数来创建一个临时对象。 const T& x 表示创建一个类型为 T 的常量引用 x。...这里的引用是 T 类型的引用，而且是常量引用，意味着 x 引用的对象是不可修改的。 const T& x = T() 将这个临时对象绑定到常量引用 x 上。...这样做的好处是可以避免不必要的拷贝，同时也可以确保 x 引用的对象是不可修改的。...erase(iterator pos)//删pos处 { assert(pos = _start); assert(size() > 0); /..._start); std::swap(_finish, v._finish); std::swap(_endOfStorage, v.

3481 0

QMap Class Reference

成员函数文件： QMap::QMap () QMap::QMap ( const QMap & other ) 这个操作发生在常量时间，因为QMap是隐式共享的。...QMap::QMap ( const std::map & other ) 这个函数只有当使能stl兼容性时，是可得的。...iterator QMap::end () 返回一个stl风格迭代器指向map最后一个项目之后的虚构项目。...const_iterator QMap::end () const iterator QMap::erase ( iterator pos ) iterator QMap::find ( const Key...其他的值是可进入的通过增加迭代器。例如，这是一些代码，迭代所有的项目使用相同的key： QMap map; ...

6471 0

C++11:基于std::unordered_map和共享锁构建线程安全的map

在上一篇博客中，实现threadsafe_queue主要是依赖std::mutex信号量来实现线程对threadsafe_queue的独占访问,不论是只读的函数还是写函数对threadsafe_queue...所以在实现线程安全的map时,我没有选择使用std::mutex控制所有的操作为独占访问，而是用RWLock来控制map对象的访问，RWLock是我以前自己写的一个类，将线程对资源的访问分为读取操作和写入操作两类...return map.erase(__position); } iterator erase(iterator __position){ auto guard=lock.write_guard...guard=lock.write_guard(); return map.erase(__x); } iterator erase(const_iterator __first..., const_iterator __last){ auto guard=lock.write_guard(); return map.erase(__first, __

8.8K1 0

高效缓存神器：简析最近最少使用（MRU）缓存模板及实践

iterator Erase(iterator pos) { index_.erase(pos->first); return ordering_.erase(pos); } 遍历操作：MRU...在这个变体中，映射是一个 std::unordered_map，而不是 std::map。这意味着键的查找速度更快，但是键必须是可哈希的。...iterator Erase(iterator pos) { index_.erase(pos->first); return ordering_.erase(pos); }...reverse_iterator Erase(reverse_iterator pos) { // 我们必须实际给出要删除的增量迭代器，因为 base() 返回的正向迭代器实际上是迭代的项目之后的一个...，而不是 std::map。

1271 0

C++ vector 使用详解(含C++20新特性)

& std::erase_if (std::vector) 简介 C++ 的 vector 本质上是一个动态数组，它的元素是连续存储的，这意味着不仅可以通过迭代器访问元素，还可以使用指向元素的常规指针来对其进行访问...介绍两个关键词 (1) constexpr 是 C++11 中新增的关键字，其语义是 "常量表达式"，也就是在编译期可求值的表达式。...最基础的常量表达式就是字面值或全局变量/函数的地址或 sizeof 等关键字返回的结果，而其它常量表达式都是由基础表达式通过各种确定的运算得到的。...begin、end 与 cbegin、cend的区别是后者是指向常量的指针，在使用的过程中不允许改变指向内容的值。此元素充当占位符；尝试访问它会导致未定义的行为。 ...() 从容器中删除指定的元素 iterator erase( const_iterator pos ); iterator erase( const_iterator first, const_iterator

1.9K3 0

C++ STL map容器值为指针时怎么释放内存

(iter++); // 从map中删除元素，注意iter++的写法 } } g_TcpConnMap.clear(); 在std::list中删除一个元素非常简单，直接使用erase方法即可...(std::remove_if(list.begin(), list.end(), shouldDelete), list_end()); 然而根据STL std::map中的定义void erase(...iterator pos)，此erase并不返回下一个元素的迭代器，因此不能采用std::list的方法 The truth is that ‘erase’ in associative containers...For this reason, you don’t really need ‘map::erase’ to return an iterator....= map.end();) { if (shouldDelete(*iter)) map.erase(iter++); else ++iter; } 当然此方法同样也适合于std

4.9K2 0

C++进阶：详细讲解容器set与map（pair、multiset、multimap）

1.关联式容器与序列式容器关联式容器和序列式容器是 C++ 中两种不同的容器类型关联式容器: 关联式容器主要包括 std::set, std::map, std::multiset, std:...插入、删除、查找等操作的平均时间复杂度是 O(log n)。序列式容器: 序列式容器包括 std::vector, std::list, std::deque, std::array 等。...3.3.2 erase（）删除函数声明功能介绍返回值 iterator erase(iterator position); 删除指定位置的元素，并返回指向被删除元素之后元素的迭代器。...iterator erase(iterator first, iterator last); 删除区间 [first, last) 中的所有元素，并返回最后一个被删除元素之后的迭代器。...const_iterator find(const key_type& k) const; 在常量 map 中查找键值为 k 的元素，并返回一个指向该元素的迭代器。

2431 0

【Example】C++ 标准库常用容器全面概述

在某个元素后插入新元素 emplace_after 在元素后原位构造元素 erase_after 擦除元素后的元素 std::deque 双端队列，是具有下标与逻辑相邻顺序的容器。...插入元素不会使任何 iterator 无效，删除元素只会使指向已删除元素的 iterator 失效。...Map 与 set 不同的是，map 系列是键值与值对应的形式，即 Key : Value 成对出现。基于红黑树的 map 会根据键的大小自动升序排序，基于哈希表的则无序。...(在std::multimap中不提供) begin 返回一个迭代器，此迭代器指向Map起始位置。 cbegin 返回一个常量迭代器，此常量迭代器指向Map起始位置。...第一个迭代器指向Map中其键大于指定键的第一个元素。第二个迭代器指向Map中其键等于或大于指定键的第一个元素。 erase 从指定位置移除Map中的元素或元素范围。

3.3K3 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云