stl_编程技术问答社区_程序员问答知识库

以下是关于 stl 的编程技术问答

C++ STL 下一步是组合式的互换

我知道我可以在包含元素[1, 2, 3]的某些容器上使用std::next_permutation，该容器将生成该序列的6个排列.我想做的是给出一些集合[1, 2, 3, 4, 5, 6]生成大小3的所有可能排列.因此，在此示例中，[4, 3, 2]将是该标准所产生的排列之一.我正在寻找一种(如果可能的话)的STL方式，而不是编写自己的组合功能.我应该阅读任何特定的STL实现? 解决方案当前(截至2016年)没有单一的STD功能可以这样做.您拥有的最接近的是您想要的功能称为next_partial_permutation，看起来像(来自N2639): template bool next_partial_permutation( BidirectionalIterator first , BidirectionalIterator middle , BidirectionalIterator

2 2023-05-25 编程技术问答社区 c++ algorithm stl combinations permutation

在O(1)内存中进行随机序列迭代？

说您想以随机顺序迭代序列[0至n]，精确访问每个元素一次.有什么方法可以在 o (1)内存中，即不创建使用std::iota的[1..n]序列并通过std::random_shuffle? 运行它某种迭代器以随机顺序吐出序列将是最佳的. 一个要求是，应该通过选择另一种种子来获得另一个随机订单. 解决方案从理论上讲，如果您构建了一个随机数发生器，其周期完全是 n ，并且覆盖了0..n中的所有值. 当然，这可能不是一个通用的解决方案，至少如果您正在寻找动态的东西，因为您必须预先创建prng以及如何做到这取决于n. 其他解决方案如果您可以将序列突变为就地，则可以简单地从0-n绘制一个随机数，然后删除您访问的元素，或将其交换至末尾或此类方案. 其他解决方案与大多数算法问题一样，时间空间的权衡；如果您乐于使用O(n^2)生成所有排列的时间，则可以在O(1)空间中解决.除了几个临时变量外，唯一需要的存储是随机数种子本身(或在这种情况下为PRNG对象)，

0 2023-05-25 编程技术问答社区 c++ stl iterator complexity-theory permutation

std::next_permutation的摊销复杂性？

我刚刚阅读 next_permunt的复杂性虽然我对响应(O(o(n)))感到满意，但似乎该算法可能具有很好的摊销分析，显示出较低的复杂性.有人知道这样的分析吗? 解决方案因此，我看起来我将在肯定地回答自己的问题 - 是，next_permutation在o(1)摊销时间中运行. 在我进行正式证明之前，这是关于算法如何工作的快速复习.首先，它从范围的末端向后扫描，直到开始，识别在最后一个元素结束的范围内最长的连续减小子序列.例如，在0 3 4 2 1中，该算法将4 2 1识别为此子序列.接下来，它查看该子序列之前的元素(在上面的示例3中)，然后在子序列中找到比其大的元素(在上面的示例中，4).然后，它交换了这两个元素的位置，然后逆转确定的序列.因此，如果我们从0 3 4 2 1开始，我们将交换3和4以产生0 4 3 2 1，然后将最后三个元素逆转以产生0 4 1 2 3. . 表明该算法在摊销的O(1)中运行，我们将使用潜在方法.将φ定义为序列结束时最长连续降低子序列

0 2023-05-25 编程技术问答社区 c++ algorithm stl big-o permutation

用于快速插入和查找n维实数向量的适当容器（提供初始基准）。

1.问题的描述我正在尝试选择最合适的(有效)容器来存储 unique n - 维矢量由浮数组成. 解决整个问题，最重要的步骤(与问题有关)涉及: 从外部程序中获取新向量(在同一运行期间，所有向量都具有相同的维度). 检查(尽快)是否已经在此容器中有一个新点: 如果存在 - 跳过许多昂贵的步骤并执行其他步骤；如果没有 - 插入中的容器(在容器中订购并不重要)，并且执行其他步骤. 提前，我不知道我将拥有多少个向量，但是提前规定了最大数字= 100000.因此，一开始，这些新向量中的大多数都是独一无二的，并且会插入容器中，但是后来很难预先预测.很大程度上取决于唯一的向量和公差值的定义. 因此，我的目标是为这种情况选择合适的容器(S). 2.选择正确的容器我做了一些评论，并且从 s. Meyers-有效的STL 项目1:选择您的容器查找速度是关键的考虑因素吗?如果是这样，你想看在Hashed容器(请参阅第25项)，分类向量(请参阅第23项

0 2023-05-24 编程技术问答社区 c++ performance stl performance-testing

带有std::priority_queue的Min heap是我的瓶颈。

替代标题: 与std::priority_queue更快的东西实现最小堆. grpof给了我: 时间秒秒呼叫S/呼叫S/呼叫名称 84.12 105.54 105.54 320000 0.00 0.00 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i 我认为这是我唯一在项目中使用的std::priority_queue. " distry_euclidean_space"部分使我感到困惑，因为它是我项目中不再使用的类/文件. 这是我确切使用的: /** * Min_heap is actually a std::priority_queue, * wi

0 2023-05-24 编程技术问答社区 c++ performance stl gprof

使用索引安全方式在STL容器上进行迭代，以避免使用锁？

想知道以下方式在诸如向量之类的STL容器上迭代是否安全，以避免锁定读取/写入，但仅允许使用任何"写入"线程. for (size_t i = 0; i

0 2023-05-24 编程技术问答社区 c++ performance stl locking

用std::priority_queue推入min heap是瓶颈。

比std::priority_queue更快的东西? 最初的问题是在这里.您可以通过/** * Min_heap is actually a std::priority_queue, * with std::greater as a parameter. */ typedef std::priority_queue, std::vector >, std::greater > > Min_heap; ... void nn(..) { // the core function of my project if(...) { branch.push(std::make_tuple(new_dist, other_child_i, tree_i)); } } 似乎是我项目的瓶颈(i think )，正如我在调用此事

0 2023-05-24 编程技术问答社区 c++ performance stl gprof

为什么STD ::向量比动态分配的数组更快?

与同事讨论的结果，我最终编写了基准测试std::vector vs原始分配的数组，最终感到惊讶. 我的测试如下: #include "testconsts.h" // defines NUM_INTS across all tests #include int main() { const int numInts = NUM_INTS; std::vector intVector( numInts ); int * const intArray = new int[ numInts ]; ++intVector[0]; // force access to affect optimization ++intArray[0]; // force access to affect optimization

0 2023-05-24 编程技术问答社区 c++ performance stl vector profiling

为什么将一个函数包装成lambda有可能使程序更快？

标题可能太笼统了.我正在基准在一个大vector v上进行以下2个语句: sort(v.begin(), v.end(), l); sort(v.begin(), v.end(), [](unsigned a, unsigned b) { return l(a, b); }); 其中l定义为 bool l(unsigned a, unsigned b) { return a ());，而第一个的速度也明显慢. 我的问题是为什么将功能包装在lambda中会加快程序的速度. 此外，sort(v.begin(), v.end(), [](unsigned a, unsigned b) { return l(b, a); });也一样快. 相关代码: #include

0 2023-05-24 编程技术问答社区 c++ performance lambda stl inlining

Dijkstra最短路径算法在std::priority_queue Vs std::set中的表现

我想了解这些容器关于它们的时间复杂性的主要区别. 我尝试了3种Dijkstra算法的实现，如下所述: 1-用简单的数组用作队列 2-带有stl Priority_queue 3-与STL Set 我测试的图形很大，其中包含超过150000个顶点，面向和所有边缘的重量都是正的. 我得到的结果如下: 1-使用数组算法非常慢 - >预期 2-使用stl Priority_queue算法运行速度比数组 - >也可以预期 > 3-使用STL设置算法运行速度令人难以置信，我谈论的几个比Priority_queue快100倍 - >我没想到会看到这种巨大的性能... 知道std :: Priority_queue和STD :: SET是存储元素的数据容器，并且基本上都具有相同的插入复杂性o(log n)，我不明白它们之间的这种巨大性能差异.您对此有任何解释吗? 感谢您的帮助，编辑: 这是我实现的摘要: 使用STD :: Set:

2 2023-05-23 编程技术问答社区 c++ algorithm performance graph stl

为什么std::vector这么快（还是我的实现太慢）？

我前几天正在玩，试图看看我可以优化一些东西.我决定从一个简单的地图开始，该地图仅进行线性搜索以查找是否存在元素，然后尝试优化其中的大部分.另外，为了比较，我使用std :: find的std :: map和std ::向量也这样做. 与我的地图相比，地图的结果是预期的，创建速度较慢和破坏，但是速度要高得多(实际上，我无法修饰它，它返回0. 问题在于std :: vector.我期望它比我的实施慢，但不是，我真的不明白它是如何相同或更快的，因为我的实施是跳过最坏的情况(该值不在矢量中)，并且是使用结果缓存. 任何人都可以在这里散发一些灯光吗?我知道STL背后的家伙是半神，但这仍然没有意义. 基准结果(i3，Windows 8.1 Pro 64，Visual Studio 2013): std::vector : Build : 85.0042 ms Loop : 37.0011 ms Find : 1.82259 ms -> First :

0 2023-05-23 编程技术问答社区 c++ performance c++11 stl

OpenMP中的共享向量

我试图使我正在使用的程序一致，并得到以下问题. 如果多个线程需要在同一向量上读/写入/写入，我是否会损失性能?我有这种感觉，这是我的程序在平行时几乎不会更快的原因.采用以下代码: #include int main(){ vector numbers; vector results(10); double x; //write 10 values in vector numbers for (int i =0; i

0 2023-05-23 编程技术问答社区 c++ performance stl openmp

STD ::向量比STD快:: unordered_set?

在我的自定义物理引擎中，最大的瓶颈是一种从空间分区(2D网格)中获取所有身体的方法，并将仅包含独特指针的集合返回到身体. template bool contains(const T& mContainer, const V& mValue) { return std::find(std::begin(mContainer), std::end(mContainer), mValue) != std::end(mContainer); } const vector& GridInfo::getBodiesToCheck() { bodiesToCheck.clear(); for(auto& query : queries) for(auto& body : *query) if(!contains(bodies

0 2023-05-23 编程技术问答社区 c++ performance vector stl unordered-set

stl数据结构的输出参数与堆栈中的返回值的效率

可以说我有功能 std::Vector calculate() { std::Vector points; //do stuff with points return points; } 和 void calculate(std::Vector& points) { //do stuff with points } 因此，我的问题是特定于堆栈上初始初始的对象，并且是STL对象.性能是否有任何差异，以及这样做的流行方法问候解决方案以该值作为参考参数具有以下属性: 将不会进行复制，移动或任何其他操作. 不能立即将返回值放在用户方面.他们不能仅仅在您的功能的参考参数或其他内容上推出临时性.他们必须必须声明一个变量，因此他们必须给它一个名称，该名称将在当前范围内. API 建议该值是输入/输出参数.也就是说，有一个价值将被阅读和书写.如果不是这种情况，那么使用它代表一个次优的API设计元

0 2023-05-23 编程技术问答社区 c++ performance stl c++11

STL bitset::count()方法的性能是什么？

我四处搜索，找不到bitset :: count()的性能时间规格.有人知道它是什么(o(n)或更好)，在哪里可以找到它? 编辑由STL我仅参考标准模板库. 解决方案 I read this file (C:\cygwin\lib\gcc\i686-pc-cygwin\3.4.4\include\c++\bitset) on my computer. 查看这些 /// Returns the number of bits which are set. size_t count() const { return this->_M_do_count(); } size_t _M_do_count() const { size_t __result = 0; for (size_t __i = 0; __i

0 2023-05-23 编程技术问答社区 c++ performance stl bitset

从Microsofts STL转换到STLport

我在Windows下的Performance Critical C ++代码中使用了很多STL.获得额外性能的一种可能的"便宜"方法是更改为更快的STL库. 根据此更快，使用较少的内存，但是已经使用了几年. 最近有人做出了这一更改，您的结果是什么? 解决方案我尚未将Stlport的性能与MSCVC进行比较，但是如果存在显着差异，我会感到惊讶. (当然，在发布模式下 - 调试构建可能会大不相同.)不幸的是，您提供的链接 - 以及我所看到的任何其他比较 - 细节上都太轻松了. 甚至在考虑更改标准库提供商之前，我建议您重大介绍您的代码，以确定瓶颈在哪里.这是标准建议；尝试进行任何绩效改进之前，请始终配置！即使分析确实在标准库容器或算法中揭示了性能问题，我建议您首先分析如何使用它们.算法改进和适当的容器选择，尤其是考虑到Big-O成本，可能会带来更大的性能回报. 其他解决方案在进行切换之前，请确保使用其他解决方案我们最近完成了相反的任务.我

0 2023-05-23 编程技术问答社区 c++ windows visual-studio performance stl

STL地图与矢量的迭代器访问性能？

使用迭代器通过STL图与向量循环循环之间有什么性能差异?我想使用地图密钥进行插入，删除和一些访问，但是我还需要定期访问地图中的每个元素. 解决方案在地图和向量的情况下，整个集合的迭代为o(n).但是(喜欢列表vs vector)向量元素连续存储元素，因此访问下一个元素要便宜得多，因为它将最佳地使用缓存，而地图则不会. 但是，由于您需要根据键进行查找，因此实际上没有其他选择.您可以在第一个元素上使用成对的向量，但是如果需要变形，这将非常慢.只需使用地图. 其他解决方案遍历地图的每个元素都需要O(n)时间. wikipedia 其他解决方案此链接有一个很好的性能表，可用于各种操作所有STL容器. 一般来说，如果您需要根据键进行大量插入，删除或搜索，那么地图就是要走的方式. 如果您只需要设置一次容器，然后像数组一样访问它，则使用向量. 编辑:STL容器操作的性能表:

0 2023-05-23 编程技术问答社区 c++ performance stl dictionary iterator

STL替代品

我真的很讨厌使用STL容器，因为它们使我的代码的调试版本非常缓慢.其他人使用什么而不是具有合理性能的STL? ? 我是游戏程序员，这在我从事的许多项目上都是一个问题.当您将STL容器用于所有内容时，很难获得60 fps. 我在大部分工作中都使用MSVC. 解决方案 Eastl是一种可能性，但仍然不完美.电子艺术的保罗·佩德里亚娜(Paul Pedriana)对游戏应用中的性能进行了各种STL实现的调查. 其中一些调整正在审查中，以纳入C ++标准. 和注意，即使是EASTL也没有针对非优化情况进行优化.不久前我有一个带有一些时间的excel文件，但我认为我已经丢失了它，但是访问它是类似的: debug release STL 100 10 EASTL 10 3 array[i] 3 1 我最成功的是滚动自己的容器.您可以将它们降到附近的数组[x]性能. 其他解

0 2023-05-23 编程技术问答社区 c++ visual-studio performance stl

C++ STL中set和hashset的区别是什么？

我什么时候应该选择另一个? 您是否建议使用正确的STL容器? 解决方案 hash_set是不属于C ++标准的扩展名.查找应为o(1)，而不是set的O(log n)，因此在大多数情况下会更快. 当您通过容器迭代时，将看到另一个差异. set将按顺序交付内容，而hash_set本质上是随机的(感谢Lou Franco). 编辑:C ++ 11更新到C ++标准引入其他解决方案 stl::set被实现为二进制搜索树. hashset被实现为哈希表. 这里的主要问题是，许多人使用stl::set认为这是一张带有O(1)查找的哈希表，不是，也没有.它确实具有o(log(n))查找.除此之外，还要阅读有关二进制与哈希表的信息，以更好地了解数据结构. 其他解决方案要记住的另一件事是，使用Hash_Set，您必须提供哈希功能，而集合仅需要一个比较函数('

6 2023-05-23 编程技术问答社区 c++ performance stl set hashset

什么时候使用std::multimap才有意义

我目前正在尝试一些STL-DATTRUCTURS的使用.但是，我仍然不确定何时使用哪个以及何时使用某种组合.目前，我正在尝试弄清楚，当使用std::multimap时，我确实有意义.据我所知，通过组合std::map和std::vector，可以轻松地构建自己的多胶合实现.因此，当应该使用这些数据架构中的每个数据架构时，我都遇到了一个问题. 简单性:STD :: Multimap绝对更易于使用，因为不必处理其他嵌套.但是，访问一系列元素是一个批量，可能需要将数据从迭代器复制到另一个数据架构(例如std::vector). 速度:矢量的局部性很可能会使相等元素范围内的迭代更快，因为高速缓存的用法已优化.但是，我猜想std::multimaps在背后也有很多优化技巧，以使迭代尽可能快地迭代.也可能针对std::multimaps进行了正确的元素范围. 为了尝试使用以下程序进行一些简单比较的速度问题: #include #include

0 2023-05-23 编程技术问答社区 c++ performance stl multimap

首页
<
1
2
3
4
5
6
7
8
>
尾页