这个问题有一个附加的约束.
我愿意允许不均匀的选择,只要它不偏不倚.
鉴于" 集合通常实现为二叉搜索树 ",我希望它们包含某种深度或大小信息以进行平衡,我希望你可以对树进行某种加权随机游走.但是,我不知道有任何远程可移植的方式来做到这一点.
编辑:约束不是分摊的时间.
std::min()使用空的初始化列表调用通常不会编译(所有问题都可以用相同的方式表示std::max()).这段代码:
#include <iostream>
#include <algorithm>
int main() {
std::cout << std::min({}) << "\n";
return 0;
}
使用clang会出现此错误:
test.cpp:6:17: error: no matching function for call to 'min'
std::cout << std::min({}) << "\n";
^~~~~~~~
algorithm:2599:1: note:
candidate template ignored: couldn't infer template argument '_Tp'
min(initializer_list<_Tp> __t)
我可以看出为什么不允许这种情况,因为在这种情况下难以就回归的合理价值达成一致.
但是,从技术上讲,代码不能编译,因为无法推导出模板参数.如果我强制参数代码编译但我崩溃了:
#include <iostream>
#include <algorithm>
int main() {
std::cout << std::min<int>({}) << "\n";
return 0;
}
$ clang++ -std=c++11 test.cpp -o test
$ ./test
Segmentation fault: 11
似乎崩溃是因为std::min()实现了崩溃std::min_element(),并且空的初始化列表导致无效 …
在阅读有关std :: inclusive_scan的内容时,似乎没有任何示例.
它让我觉得非常类似于std :: partial_sum.
partial_sum:
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first,
InputIt last, OutputIt d_first );
inclusive_scan:
template< class InputIt, class OutputIt >
OutputIt inclusive_scan( InputIt first,
InputIt last, OutputIt d_first );
有人可以详细说明他们的分歧吗？我何时会选择一个而不是另一个？
所以,我对std :: map,lambda和stl算法(remove_if)有疑问.实际上,与std :: list或std :: vector相同的代码运行良好.
我的测试示例:
#include <map>
#include <iostream>
#include <algorithm>
struct Foo
{
Foo() : _id(0) {}
Foo(int id) : _id(id)
{
}
int _id;
};
typedef std::map<int, Foo> FooMap;
int main()
{
FooMap m;
for (int i = 0; i < 10; ++i)
m[i + 100] = Foo(i);
int removeId = 6;
// <<< Error here >>>
std::remove_if(m.begin(), m.end(), [=](const FooMap::value_type & item) { return item.second._id == removeId ;} );
for (auto & item : …标准C++中有算法std::count/ std::count_if.
template<class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value);
template<class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred);
效果:返回以下相应条件所适用的[first,last]范围内的迭代器数量:*i == value,pred(*i)!= false.
difference_type是iterator's difference_type,可以是负数,但count只能返回值> = 0.为什么difference_type而不是size_t例如？
我有成对的int对
set<pair<int,int> > x1, x2, ... xn(n可以在2到20之间).找到这些集合的最快方法是什么？
对不起如果我一开始没说清楚,我的意思是性能快,内存分配不是问题.
在考虑这个问题时,我开始想知道是否std::copy()和/或是std::fill专门的(我真的意味着优化)std::vector<bool>.
这是C++标准所要求的,或者,它是C++ std库供应商的常用方法吗？
简单来说,我想知道以下代码:
std::vector<bool> v(10, false);
std::fill(v.begin(), v.end(), true);
以任何方式更好/不同于:
std::vector<bool> v(10, false);
for (auto it = v.begin(); it != v.end(); ++it) *it = true;
要非常严格 - 可以,可以说:std::fill<std::vector<bool>::iterator>()进入内部表示std::vector<bool>并设置整个字节而不是单个位？我认为交std::fill朋友std::vector<bool>不是图书馆供应商的大问题吗？
[UPDATE]
下一个相关的问题:我可以(或其他任何人)专门研究这样的算法std::vector<bool>,如果不是已经专门化了吗？这是C++标准允许的吗？我知道这将是不可移植的 - 但仅适用于一个选定的std C++库？假设我(或其他任何人)找到了去std::vector<bool>私人部分的方法.
根据草案N4431,std::binary_search算法库中的函数返回a bool,[binary.search]:
Run Code Online (Sandbox Code Playgroud)template<class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);要求:元素
e的[first,last)相对于该表达式被划分e < value和!(value < e)或comp(e, value)和!comp(value, e).此外,所有元素e的[first,last),e < value暗示!(value < e)或comp(e, value)implies !comp(value, e).返回:
true如果满足相应条件i的范围内存在迭代器[first,last) …
假设我有一个包含一些数据的大量字节(最多4GB).这些字节对应于这样的方式,每一个不同的对象小号字节(认为小号最多32个)将构成一个对象.一个重要的事实是,对于所有对象,此大小s是相同的,不存储在对象本身内,并且在编译时不知道.
目前,这些对象只是逻辑实体,而不是编程语言中的对象.我对这些对象进行了比较,其中包括对大多数对象数据的字典对比,以及使用剩余数据打破关系的一些不同功能.现在我想将这些对象进行排序效率(这是真的要成为应用的瓶颈).
我想到了几种可能的方法来实现这一目标,但是每一种方法似乎都有一些相当不幸的后果.您不一定非必须阅读所有这些内容.我试图用粗体打印每种方法的核心问题. 如果您打算提出其中一种方法,那么您的答案也应该回答相关问题.
当然,C快速排序算法也可用于C++应用程序.它的标志几乎完美符合我的要求.但是使用该函数将禁止内联比较函数的事实将意味着每个比较都带有函数调用开销.我曾希望有办法避免这种情况.任何关于C qsort_r在性能方面与STL相比的经验都是非常受欢迎的.
编写一堆包含指向各自数据的指针的对象会很容易.那么人们就可以对它们进 这里有两个方面需要考虑.一方面,仅仅移动指针而不是所有数据意味着更少的内存操作.另一方面,不移动对象可能会破坏内存局部性,从而破坏缓存性能.有可能实际上从一些缓存页面访问所有数据的更快的快速排序递归水平几乎完全消失.相反,每个缓存的内存页面在被替换之前只会产生非常少的可用数据项.如果有人能提供一些关于复制和记忆位置之间权衡的经验,我会很高兴.
我写了一个类作为内存范围的迭代器.取消引用此迭代器不会产生引用,而是产生一个新构造的对象来保存指向数据的指针和在构造迭代器时给出的大小s.所以可以比较这些对象,我甚至可以实现std::swap这些目标.不幸的是,它似乎std::swap还不够std::sort.在该过程的某些部分,我的gcc实现使用插入排序(__insertion_sort在文件中实现stl_alog.h),它将值移出序列,将数字项移动一步,然后将第一个值移回适当的序列中位置:
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);
您是否知道标准排序实现不需要值类型但可以单独使用交换操作？
所以我不仅需要我的类作为参考,但我还需要一个类来保存临时值.由于我的对象的大小是动态的,我必须在堆上分配它,这意味着在recusrion树的叶子上分配内存.也许一种替代方案是具有静态大小的vaue类型,该大小应足够大以容纳我当前打算支持的大小的对象.但是,这将意味着将在之间的关系更加两轮牛车reference_type和value_type迭代器类.这意味着我必须为我的应用程序更新该大小,以便有一天支持更大的对象.丑陋.
如果你能想出一个干净的方法来让上面的代码操作我的数据而不必动态分配内存,那将是一个很好的解决方案.我已经在使用C++ 11功能了,所以使用移动语义或类似功能不会有问题.
我甚至考虑重新实现所有的快速排序.也许我可以利用这样一个事实,即我的比较主要是字典比较,即我可以按第一个字节对序列进行排序,只有当所有元素的firt字节相同时才切换到下一个字节.我还没有弄清楚这方面的细节,但是如果有人可以建议一个引用,一个实现,甚至一个规范的名称作为这样一个按字节顺序排列的词典排序的关键字,我会非常高兴.我仍然不相信通过合理的努力,我可以击败STL模板实现的性能.
我知道那里有很多种排序算法.其中一些可能更适合我的问题.我首先想到了基数排序,但我还没有想到这一点.如果您可以建议更适合我的问题的排序算法,请执行此操作.优选实施,但即使没有.
所以基本上我的问题是:
"你如何有效地在堆内存中对动态大小的对象进行排序？"
任何适用于我的情况的问题的答案都是好的,无论它是否与我自己的想法有关.以粗体标记的个别问题的答案,或任何其他可能帮助我在我的选择之间做出决定的见解也是有用的,特别是如果没有对单一方法的明确答案出现.
是否有几个std::algorithm/lambda function访问nth满足给定条件的元素.因为std::find_if会访问第一个,所以有一个等价的找到nth一个吗？