在set容器键值key和实值value是相同的,且在容器里面的元素是根据元素的键值自动排序的,同时我们不能修改set容器里面的元素值,所以set的迭代器是采用RB-Tree的const_iterator...= std::less> class set{ public: typedef Key key_type; typedef Key value_type...rb_tree1 rep_type; // set的成员变量 rep_type t; }; 在map...std::pair value_type; typedef Compare key_compare; // 对于map而言,Key, Value...类型不一样,一个排序,另一个节点实值 typedef rb_tree1 rep_type; // map的成员变量
https://blog.csdn.net/xuzhina/article/details/46758253 看一下bits/stl_map和bits/stl_set可以看到map和set的定义如下...mapped_type; 91 typedef std::pair value_type; 92 typedef...>::other 122 _Pair_alloc_type; 123 124 typedef _Rb_tree, 86 typename _Alloc = std::allocator > 87 class set 88 { 89 //...每一个节点的值都紧跟着_M_right 看一下例子: 1 #include 2 3 int main() 4 { 5 std::set iSet;
为什么 set 的底层不用hash? set.lower_bound(x)/upper_bound(x) 有一个结构体,里面有两个字符串,如何在一个set中查找这个结构体?...{ public: //key_type 和 value_type 的类型是一样的 typedef Key key_type; typedef Key value_type; //key_compare...//底层采用红黑树来实现 typedef rb_tree<key_type, value_type, identity, key_compare...} ---- 为何map和set的插入删除效率比其他序列容器高,而且每次insert之后,以前保存的iterator不会失效? 1、因为存储的是结点,不需要内存拷贝和内存移动。...2、map和set的增删改查速度为都是logn,是比较高效的。 ---- 为什么 set 的底层不用hash? 1、用,干嘛不用。用完改名字了,叫 unordered_set。
关联式容器 之前我们学的list,vector等等是序列式容器,这里的set和map和之后的哈希表都是关联式容器,比如说搜索二叉树我们想插入一个值,不能随意的插入,因为每个数都是有关联的,需要找到准确位置才能进行插入...template < class T, // set::key_type/value_type class Compare = less, // set::key_compare/value_compare...> using namespace std; int main() { settree; tree.insert(1); tree.insert(3); tree.insert(9)...这个接口的作用是统计这棵树中有多少个这个值的结点。 这个接口是为了multiset存在的。...key_type/value_type class Compare = less, // multiset::key_compare/value_compare class Alloc = allocator
4.0 map基本访问单元为pair,pair只有二个成员变量,first和key 分别表示key和value。...; map::value_type : 表示一个pair类型, 它的first元素具有const map::key_type类型, 而second...( const pair &val ); 插入val到pos的后面,然后返回一个指向这个元素的迭代器。...返回值是一个指向被插入 元素的迭代器和一个描述是否插入的bool值。...code如下: ---- #include #include #include #include using namespace std
0) // 需要find一次 { map.erase(X); // 需要find一次 } else { // 不存在时的处理 } 2、高效率的用法 // 解决办法,充分利用insert和erase
但是set会对元素自动排序,而hash_set没有 hash_set和set的使用方法相同 在介绍hash table的hash functions的时候说过,hash table有一些无法处理的类型...key_type; typedef typename _Ht::value_type value_type; typedef typename _Ht::hasher hasher; typedef...= Set.end(); ++iter) std::cout << *iter << ""; //banana plum mango apple kiwi apricot std::cout << std...= Set.end(); ++iter) std::cout << *iter << ""; //387 194 1 389 196 3 std::cout << std::endl; return 0...key_type; typedef _Tp data_type; typedef _Tp mapped_type; typedef typename _Ht::value_type value_type
我们之前在学习 set 和 map 基本使用时就介绍了 set 和 map 底层都是红黑树,但这里有一个问题 – set 是K模型的容器,而 map 是KV模型的容器,那它们底层为什么能同样都使用红黑树呢...multiset;这就是为什么我们使用 multiset 和 multimap 时只需要包 set 和 map 头文件的原因。..._Key 和 _Tp,也就是我们认为的传递给 map 的 K 和 V; 而对于 set 来说,key_type 也是我们平时认为的 K,但是我们发现 set 中居然还有一个变量 value_type,...并且 value_type 的类型就是 key_type 的类型,但是 set 不是K模型的容器吗?...set 传递过来的 value_type,如下: 通过这张图相信大家就可以很容易理解为什么 set 和 map 虽然是不同模型的容器,但都可以使用 红黑树 作为底层容器了 – 如果是 map,则红黑树的模板参数
排序的依据是key,而set/multiset元素的value和key合二为一:value就是key。...template, typename _Alloc = std::allocator > class set { // concept requirements typedef typename _Alloc::value_type...typedef _Key key_type; typedef _Key value_type; // value也是key typedef _Compare key_compare...> > class set { private: typedef _Rb_tree,
STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); public: // typedefs: typedef _Key key_type...typedef _Rb_tree<key_type, value_type, _Identity, key_compare, _Alloc> _Rep_type; _Rep_type...(const value_type* __first, const value_type* __last) : _M_t(_Compare(), allocator_type()) { _M_t.insert_unique...(__first, __last); } set(const value_type* __first, const value_type* __last, const _Compare& __comp...<< iset.count(3) << std::endl; std::cout << "1 count" << iset.count(1) << std::endl << std::endl; set
value>才是rb_tree的节点,同样成员就一个rb_tree足已表现整个map: template > class map{ // 用于re_tree排序 typedef Key key_type; // rb_tree节点的value typedef...std::pair value_type; typedef Compare key_compare; // 对于map而言,Key, Value...类型不一样,一个排序,另一个节点实值 typedef rb_tree1 rep_type; // map的成员变量...定义和multimap容器和map基本相同,只不过插入调用的是函数:insert_equal, 允许插入相同的值。
对于本节,我们将从下面几个内容阐述: map的key为key,value为key+data,与set是不同的,set是key就是value,value就是key。...key_type; typedef _Tp mapped_type; typedef std::pair...typedef std::pair value_type; 2.insert ★insert里面采用_M_insert_unique... > > class multimap { public: typedef std::pair value_type...(__k), std::tuple()); #else __i = insert(__i, value_type(__k, mapped_type
一、multiset multiset的特性以及用法和set完全相同,唯一的差别在于它允许键值重复,因此它的插入操作采用的是底层RB-tree的insert_equal()而非insert_unique...STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); public: // typedefs: typedef _Key key_type...typedef _Rb_tree<key_type, value_type, _Identity, key_compare, _Alloc> _Rep_type; _Rep_type...operator== __STL_NULL_TMPL_ARGS (const multiset&, const multiset&); friend bool __STD_QUALIFIER operator...const multiset&, const multiset&); #endif /* __STL_TEMPLATE_FRIENDS */ }; 二、multimap multimap的特性以及用法和map
与顺序容器不同的是,关联容器中元素是按照关键字来保存和访问的。与之相对的顺序容器是按它们在容器中的位置来顺序的保存和访问的。 关联容器支持高效的查找和访问。两个主要的关联容器类型是map和set。...关联容器的操作 关联容器定义了额外的类型别名 key_type: 此容器类型的关键字类型 mapped_type: 每个关键字关联的类型:只适用与map value_type: 对于set,与key_value...相同;对于map,为 pair set::value_type v1; //v1 是一个string set:...由于关联容器中的元素不能通过它们的关键字进行快速查找,因此对其使用泛型算法几乎总是一个坏主意 关联容器中有一个find的成员,我们可以使用find算法来根据关键字查找元素。...对于map和unordered_map 容器提供了下标运算,下标中填入key_type的值,得到value_type,如果关键字不在map中,会为它创建一个元素并插入map中。
关联容器最常见的是map、set、multimap、multiset map的元素以键–值【key-value】对的形式组织:键用作元素在map中的索引,而值则表示所存储和读取的数据。...set仅包括一个键。并有效的支持关于某个键是否存在的查询。...注意K和V的值要同样 mapm(b,e);//——创建map类型的对象m,存储迭代器b和e标记的范围内全部元素的副本。...关联容器操作: key_type——此容器类型的keyword类型 mapped_type——每一个keyword关联的类型;仅仅适用于map value_type——对于set。...为pair类型:pair #include #include using namespace std; int
map的特性 所有元素都会根据元素的键值自动被排序 map中的pair结构 map的所有元素类型都是pair,同时拥有实值(value)和键值(key) pair的第一个元素视为键值,第二个元素视为实值...STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); // typedefs: typedef _Key key_type...以map元素类型(一个pair)的第一类型,作为RB-tree节点的键值类型 typedef _Rb_tree<key_type, value_type, _Select1st,...Rep_type::const_reference const_reference; typedef typename _Rep_type::iterator iterator; //注意上面一行,map不像set..., __last); } map(const value_type* __first, const value_type* __last, const _Compare& __comp, const
,VALUE_TYPE> &val ); //插入start到end的元素到map中 void insert( input_iterator start, input_iterator end ); /...返回值是一个指向被插入元素的迭代器和一个描述是否插入的bool值 pair insert( const pair &val );...map_del_str.cpp -o map_del_str * @Reference */ #include #include using namespace std...map_del_int.cpp -o map_del_int * @Reference */ #include #include using namespace std...Associative Container(包含set,multiset,map,multimap容器)。
const Cont &) -> typename std::enable_if::value, bool>::type {...is_pair::value, bool>::type { int etype = ischarOrString(element);...::declval(), os) { os " << element.second;...{3, 9}}; cout << vv << endl; pair p{1, 2}; cout << p << endl; set... s{1, 2, 3}; cout << s << endl; vector v{'a', 'b'}; cout << v << endl; set
STL中基本的关联式容器有map和set,它们都是以红黑树作为其底层的结构,具有非常高的查找、删除效率,内容会按照键值自动排序。...include 2 #include 3 #include//pair的头文件 4 #include 5 using namespace std...//返回值中pair,第一个是一个map的迭代器表示插入数据在容器中的位置,第二个是bool类型,插入成功返回1,否则返回0; 13 mapsecond<<" "<<r3.second<<endl; 24 //insert版本2 iterator insert(iterator pos,const pair<key_type...//遍历,如果键值比较有规律可以使用[]结合循环,否则使用迭代器 79 80 81 //删除数据 82 //map中erase有三个版本可以删除键值指定的数据,迭代器指定的数据和迭代器指定区间的数据
3、map定义的类型 map对应的元素是键-值对,在学习map接口时,警记value_type是pair类型,键是key_type类型,为const,不可修改,而值是mapped_type类型,可以修改...如下: map::key_type 键的类型 map::mapped_type 值得类型 map::value_type pair类型,first元素为...const map::key_type类型,second元素为map::mapped_type类型 4、使用下标访问map对象 使用下标访问map与使用下标访问数组或vector的行为截然不同...8、在multimap和multiset中查找元素 可以用三种策略来解决查找问题: 第一种策略:使用find和count操作: count函数求出某键出现的次数,而find操作则返回一个迭代器,指向第一个拥有正在查找的键的实例...include 6 #include 7 #include 8 #include 9 10 using namespace std
领取专属 10元无门槛券
手把手带您无忧上云