首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么我的"choose k from n“算法适用于std::vector而不适用于std::map?

"choose k from n"算法适用于std::vector而不适用于std::map的原因是因为std::vector是一个有序的线性容器,而std::map是一个基于红黑树实现的关联容器。

"choose k from n"算法是从n个元素中选择k个元素的组合算法。在std::vector中,元素是按照插入的顺序存储的,可以通过索引直接访问元素,因此可以通过下标操作来实现组合算法。例如,可以使用循环和递归的方式来生成所有可能的组合。

然而,在std::map中,元素是按照键值对的方式存储的,而不是按照插入的顺序。std::map使用红黑树来实现,这意味着元素是按照键的顺序进行排序的。由于std::map是基于二叉搜索树的数据结构,它不支持通过下标来访问元素。因此,在std::map中实现"choose k from n"算法会比较困难。

如果需要在std::map中实现"choose k from n"算法,可以考虑使用迭代器来遍历map中的元素,并使用递归的方式生成组合。但是这种方法效率较低,因为在红黑树中查找元素的时间复杂度是O(log n),而不是O(1)。因此,对于大规模的数据集,使用std::map来实现"choose k from n"算法可能会导致性能问题。

综上所述,"choose k from n"算法适用于std::vector而不适用于std::map的原因是std::vector是有序的线性容器,可以通过下标操作来访问元素,而std::map是基于红黑树实现的关联容器,不支持通过下标来访问元素,并且查找元素的时间复杂度较高。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

【c++】标准模板库STL入门简介与常见用法

cout<<"v.size()="<<v.size()<<endl;     for ( i=0;i<v.size();i++)        cout<<v[i]<<endl; } 3、高级操作 迭代器和<em>算法</em>同样<em>适用于</em>其它容器...for_each()<em>算法</em>、sort()<em>算法</em>、count()<em>算法</em>、find()<em>算法</em>同样<em>适用于</em>deque容器; 3、deque应用 练习:deque综合练习 #include #include...d.sort();           //list类<em>的</em>排序使用成员函数完成。<em>而</em>不是用通用<em>算法</em>函数。...2、<em>map</em><em>的</em>成员函数 (1)构造函数: <em>map</em> m2; // 创建一个名为m2<em>的</em>空<em>map</em>对象,其键和值<em>的</em>类型分别为<em>k</em>和v <em>map</em> m(m2); // 创建m2<em>的</em>副本m,m与m2必须有相同<em>的</em>键类型和值类型...<em>map</em> m(iter_F, iter_L); // 创建<em>map</em>类型<em>的</em>对象m,存储迭代器iter_F和 iter_L标记<em>的</em>范围内所有元素<em>的</em>副本。

68710

【C++】STL梳理

通过迭代器协助,我们只需撰写一次算法,就可以将它应用于任意容器之上,这是因为所有容器迭代器都提供一致接口。 STL 基本观念就是将数据和操作分离。...数据由容器进行管理,操作则由算法进行,迭代器在两者之间充当粘合剂,使任何算法都可以和任何容器交互运作。...) :vector(from) - 构造一个与vector from 相同vector vector(input_iterator start, input_iterator end):迭代器(start...总结:支持随机访问,但效率没有 vector 高,在头部和尾部插入或删除效率高,但在中间插入或删除效率低,适用于既要频繁随机访问,又要关心两端数据插入与删除场景。...(缺点) 总结:不支持随机访问,在任意位置插入和删除效率都较高,适用于经常进行插入和删除操作并且不经常随机访问场景。

66721

标准关联容器一定比vector查找速度快吗?

n,提供n不小于当前大小,强迫进行一次重新分配,增加容量 因此,可以得知 reserve 允许你最小化必须进行重新分配次数,避免真分配开销和迭代器/指针/引用失效 */ std::vector...,拒绝编译 //将循环中 * 改成 ** 可能输出你想要结果,也可能不是,因为它是按照指针值进行排序,不是 string值排序 //为什么会出现以上问题?...n"),Dereference()); //因此,可以得出 //1, 算法替代循环 //2,指针标准关联容器,容器是以指针值进行排序不是你想要,所以你需要建立自己仿函数类作为比较类型 /...//为什么必须创造一个仿函数类不是简单地为set写一个比较函数,你可能想这样试试 见 5 //5 bool stringPtrLessSS(const std::string* ps1, const...& k1, const Data::first_type& k2) const{ return k1 < k2; } }; //有序vector模拟map<string

1.8K10

Python快速实战机器学习(9) K近邻

引言 KNN(K近邻)算法是懒惰学习一个典型示例。...KNN算法 KNN算法本身非常简单,步骤如下: 1 确定k大小和距离度量。 2 对于测试集中一个样本,找到训练集中和它最近k个样本。 3 将这k个样本投票结果作为测试样本类别。...对每一个测试样本,基于事先选择距离度量,KNN算法在训练集中找到距离最近(最相似)k个样本,然后将k个样本类别的投票结果作为测试样本类别。...k选择对于KNN模型来说至关重要,除此之外,距离度量也是很有用。通常,欧氏距离用于实数域数据集,此时一定要对特征进行标准化,这样每一维度特征重要性等同。...虽然我们在逻辑回归中讨论了正则项来防止过拟合,但是正则项却不适用于KNN和决策树模型, 们只能通过特征选择和降维手段来避免维度诅咒。

42810

【C++】STL基本用法

STL提供了一组通用模板类和函数,用于实现常见数据结构和算法,如向量(vector)、链表(list)、栈(stack)、队列(queue)、映射(map)等,以及包括排序、搜索、算法等在内各种算法操作...容器用于存储和组织数据,不同类型容器适用于不同数据访问和操作需求。 算法(Algorithms):STL包含了一系列通用算法用于操作容器中数据,例如排序、查找、复制、变换等。...这些算法是高度优化,可适用于不同类型容器,使开发人员能够更轻松地进行常见操作。 迭代器(Iterators):迭代器是用于访问容器中元素通用接口。...它们提供了统一方法来遍历容器,并使算法能够与不同类型容器一起使用,不需要了解底层容器细节。...i++){ cin>>myVector[i]; } //解决 for(int i=0;i<n;i++){ int k; cin>>k; myVector.push_back

11810

map 学习(下)——C++ 中 hash_map, unordered_map

hash[numbers[i]] = i; } return result; } }; 算法本身遍历一次,花费了 O(n) 时间复杂度,遍历过程中 find(...) 方法本身花费 O(log n),所以该算法总时间复杂度为 O(nlog n)。...,因此效率非常高; 缺点: 空间占用率高,因为 map 内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点,子节点以及红/黑性质,使得每一个节点都占用大量空间; 适用于具有顺序要求问题...); 缺点: 空间占用多,如果对内存使用很严格,需要认真考虑是否使用 hash_map ;特别是当 hash_map 对象特别多时,更加难以控制; 适用于对效率要求较高环境; unordered_map...: 优点: 内部实现了 Hash 表,所以查找速度很快; 缺点: Hash 表建立比较比较费时; 适用于查找问题;

12.9K91

C++17,标准库新引入并行算法

之前文章介绍了很多重载标准库算法,有兴趣朋友可以看看....这次,要介绍一下 C++17 新引入7个算法: std::for_each_n std::exclusive_scan std::inclusive_scan std::transform_exclusive_scan...A short detour C++17 新引入算法在纯函数式语言 Haskell 中都有对应方法. for_each_n 对应方法为 map. exclusive_scan 和 inclusive_scan...第一个函数将列表中元素映射为元素长度,第二个函数则将这些映射长度相加.(9) 中操作和 (7) 很相似,不同之处在于 foldl 只产生一个数值(不是列表)并且需要一个初始元素(指定初始元素为...想你也许好奇为什么要在介绍C++文章中写这么多 Haskell 内容(这些内容还颇具挑战性),那是因为两个原因: 你可以知道 C++ 中相应算法历史 比照 Haskell 对应方法可以帮助我们理解

99320

C++ STL (标准模板库) 详细内容讲解

C++标准库(Standard Template Library,STL) 里面有很多常用数据结构和算法模板,可直接使用。 容器(container):是用于存放数据类模板。...其实comp比较函数才是整个count_if函数核心,comp比较函数是编程的人写,返回值是一个布尔型,相信看完例题后,就可以理解这个函数应用。...PrintVector(const vector & v) { //用于输出vector容器全部元素函数模板 typename vector ::const_iterator...容器适配器是没有迭代器,因此 STL 中各种排序、查找、变序等算法不适用于容器适配器。 stack 例题:编写程序,输入一个十进制数 n 和进制 kk≤10),输出 n 对应 k 进制数。...k; stack stk; cin >> n >> k; //将n转换为k进制数 if (n == 0) { cout << 0;

2K10

OpenGl 导入读取多个3D模型 并且添加鼠标控制移动旋转

前言:   因为接下来项目需求是要读取多个3D模型,并且移动拼接,那么就先把基本小demo给写好当做前期测试。   ...在之前网上博客都只有读取移动旋转单个3d模型, 导致根本查不到有关资料,只能自己写了。   前人栽树,后人乘凉。   ...由于多边形都可以划分为三角形,三角形是图形处理器中都支持基本图元,因此使用得较多就是三角形网格来建模。例如下面的图(来自:What is a mesh in OpenGL?)...,这里索引是前面用v,vt,vn定义数据 注意这里Obj索引是从1开始不是0 那么我们只要拿到这些数据,按照opengl绘制规则,不就可以把他们都绘制出来了吗?...else std::cout << "not choose" << std::endl; } } 这些基本就是这个博客讲所有内容了,让我们最后看看成果。

3K30

如何优雅传递 stl 容器作为函数参数来实现元素插入和遍历?

后台为了保证消息一定可以推到客户端,它采取了一种重复推送策略,也就是说,每次当我重新连接上后台时,后台会把一段时间内消息都推给我、不论这些消息之前是否已经推送过,如果不加处理直接推给产品,可能造成同一个消息重复展示多次问题...> 这个容器作为参数(有的人可能觉得多此一举,直接在函数里访问 m_svrmsgs 成员不就行了,为什么要通过参数传递呢?...= vec.end (); ++ it) 7 printf ("%d\n", *it); 8 9 return 0; 10 } 为了在容器尾部插入元素,标准库算法借助了...return map_inserter(m); 58 } 59 }; 这段代码是从网上抄来,具体请参考下面的链接:std::map inserter 实现。...三个模板参数,不是 map 本身这个参数,不太清楚是一种进步、还是一种退步,反正这个 map_inserter 有点儿怪,没有封装成 map_insert_iterator + map_inserter

3.6K20

两万字总结《C++ Primer》要点

将c1中元素替换为列表中元素(不适用于array) a.swap(b) 交换a和b元素 swap(a, b) 与a.swap(b)等价 大小 c.size() c中元素数组(不支持forward_list...) c.max_size() c中可保存最大元素数目 c.empty() 若c中存储了元素,返回false,否则返回true 添加/删除元素(不适用于array) c.insert(args) 将...返回e (4)map下标操作 map和unorder_map下标操作 c[k] 返回关键字为k元素;如果k不在c中,添加一个关键字为k元素,对其进行值初始化 c.at[k] 访问关键字为k元素...对于不允许重复关键字容器,返回值永远是0或1 c.lower_bound(k) // 返回一个迭代器,指向第一个关键字不小于k元素;不适用于无序容器 c.upper_bound(k) // 返回一个迭代器...,指向第一个关键字大于k元素;不适用于无序容器 c.equal_bound(k) // 返回一个迭代器pair,表示关键字等于k元素范围。

1.5K30

两万字总结《C++ Primer》要点

将c1中元素替换为列表中元素(不适用于array) a.swap(b) 交换a和b元素 swap(a, b) 与a.swap(b)等价 大小 c.size() c中元素数组(不支持forward_list...) c.max_size() c中可保存最大元素数目 c.empty() 若c中存储了元素,返回false,否则返回true 添加/删除元素(不适用于array) c.insert(args) 将...返回e (4)map下标操作 map和unorder_map下标操作 c[k] 返回关键字为k元素;如果k不在c中,添加一个关键字为k元素,对其进行值初始化 c.at[k] 访问关键字为k元素...对于不允许重复关键字容器,返回值永远是0或1 c.lower_bound(k) // 返回一个迭代器,指向第一个关键字不小于k元素;不适用于无序容器 c.upper_bound(k) // 返回一个迭代器...,指向第一个关键字大于k元素;不适用于无序容器 c.equal_bound(k) // 返回一个迭代器pair,表示关键字等于k元素范围。

1.6K20
领券