小编Bja*_*une的帖子

我正在寻找有关如何有效实现二进制堆的信息.我觉得应该有一篇关于有效实现堆的好文章,但我还没找到.事实上,我已经无法找到任何有关超出基础知识的有效实现的资源,例如将堆存储在数组中.我正在寻找制作快速二进制堆的技术,超出我在下面描述的那些.

我已经编写了一个比Microsoft Visual C++和GCC的std :: priority_queue或使用std :: make_heap,std :: push_heap和std :: pop_heap更快的C++实现.以下是我在实现中已经涵盖的技术.我自己只想出了最后两个,尽管我怀疑这些是新想法:

(编辑:添加了关于内存优化的部分)

&(p[i]) == static_cast<char*>(p) + sizeof(T) * i

&(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j

parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)

C++ 11标准对标准库相关的自移动赋值有何看法？更具体的是,什么(如果有的话)保证什么selfAssign呢？

template<class T>
std::vector<T> selfAssign(std::vector<T> v) {
  v = std::move(v);
  return v;
}

根据这个前缀std::atomic<T>::operator++返回一个T,所以这段代码只增加v一次:

template<class T> void addTwo(std::atomic<T>& v) {
  ++(++v);
}

此外,std::atomic<T>::operator= 显然返回a T,因此此代码取消引用用于指向临时的无效指针T:

template<class T>
void setOneThenTwo(std::atomic<T>& v) {
  auto ptr = &(v = 1);
  *ptr = 2;
}

我肯定不会建议这些代码模式是好的做法,但是对我来说std::atomic打破它们是非常令人惊讶的.我总是期望operator=和前缀operator++返回引用*this.

问题:这里的返回类型是否正确cppreference,如果是这样,std::atomic在这方面是否有充分的理由表现出与内置类型不同的行为？

我看了一下C++ 0x标准草案,据我所知,堆栈溢出没有任何内容.搜索"堆栈溢出"不会产生任何结果,并且搜索"堆栈"我只获得了堆栈展开和std :: stack的引用.这是否意味着没有符合C++标准的实现,因为当本地对象(例如巨大的本地数组)耗尽内存时,没有机制允许处理错误？

这个问题的答案表明,至少C标准没有提到堆栈溢出.

要使问题具体,请考虑此计划

// Program A
int identity(int a) {
  if (a == 0)
    return 0;
  char hugeArray[1024 * 1024 * 1024]; // 1 GB
  return identity(a - 1) + 1;
}
int main() {
  return f(1024 * 1024 * 1024);
}

和这个程序

// program B
int main() {
  return 1024 * 1024 * 1024;
}

我认为C++标准不允许任何C++实现在这两个程序上做一些明显不同的事情.实际上程序A不会在任何现代机器上运行,因为它在堆栈上分配了一个exabyte内存(想象一下该函数实际上使用了巨大的数组,因此编译器无法以静默方式将其删除而不会产生不良影响).C++标准是否允许程序A失败？

编辑:问题不在于标准是否应该定义堆栈溢出会发生什么,问题是它说什么,如果有的话.

我正在使用std :: unordered_map.我有一个哈希值和一种方法来确定给定的候选键是否是我正在寻找的键,但我没有实际的键.我想查找与哈希值对应的存储桶,并浏览该存储桶中的每个元素,看看它是否是我要查找的元素.不幸的是,函数std :: unordered_map :: bucket(x)需要x作为键.没有先构建密钥,真的没有办法从哈希值中获取存储桶吗？

您不需要回答问题的详细信息:我可以构建密钥,但在没有冲突的常见情况下,这将花费更长的时间,而不仅仅是检查我在桶中找到的单个候选是否是正确的.我的负载系数很低,因此冲突很少,即使是碰撞,完整的哈希值也不太可能匹配,因此很快就会确定不匹配.我关心这个因为我已经确定了一个分析器,关键构造花费了大量的时间 - 有很多查找,每次查找都需要构造一个密钥.

更多细节,你真的不需要回答这个问题:键是整数的向量,我的查询是两个向量的总和.检查给定向量V是两个向量A和B的总和比将两个向量加到第三个向量C = A + B然后将C与V进行比较更快.我能够确定哈希值A + B没有计算实际矢量A + B,因为我存储了这些矢量的哈希值,而我的哈希函数f具有f(A + B)= f(A)+ f(B)的特性.所以我只需添加两个存储的哈希值来获得总和的哈希值.我已经确保保留一个备用向量,以便构造一个键不需要内存分配,但添加向量的代码仍然需要花费大量的时间.

以下是可能的定义std::swap:

template<class T>
void swap(T& a, T& b) {
  T tmp(std::move(a));
  a = std::move(b);
  b = std::move(tmp);
}

我相信

1. std::swap(v,v) 保证没有效果
2. std::swap 可以如上实现.

以下引用似乎暗示这些信念是矛盾的.

17.6.4.9函数参数[res.on.arguments]

1除非另有明确说明,否则以下各项均适用于C++标准库中定义的函数的所有参数.

...

• 如果函数参数绑定到右值引用参数,则实现可以假定此参数是对此参数的唯一引用.[注意:如果参数是T &&形式的通用参数并且绑定了类型A的左值,则参数绑定到左值引用(14.8.2.1),因此不包含在前一句中. - 结束注释] [注意:如果程序在将左值传递给库函数时将左值转换为x值(例如通过使用参数move(x)调用函数),程序实际上会要求该函数处理该左值作为临时的.实现可以自由地优化别名检查,如果参数是左值,则可能需要这些检查.-endnote]

(感谢霍华德Hinnant(欣南特)用于提供报价)

让我们v从标准模板库中获取一些可移动类型的对象并考虑该调用std::swap(v, v).在该行a = std::move(b);以上,这是内部的情况T::operator=(T&& t)的是this == &b,这样的参数是不唯一的参考.这违反了上面的要求,因此该行在a = std::move(b)调用时调用未定义的行为std::swap(v, v).

这里有什么解释？

int* a = new int[5] - 1;

这一行本身根据C++标准调用未定义的行为,因为a是一个无效的指针而不是一个接一个的结尾.同时,这是制作基于1的数组(第一个元素是[1])的零开销方式,我需要用于我的项目.

我想知道这是否是我需要避免的,或者如果C++标准只是保守地支持一些奇怪的架构,我的代码永远都不会运行.所以问题是,这将是一个什么样的架构问题？这些广泛存在吗？

编辑:要查看上面的行确实调用了未定义的行为,请查看此问题.

编辑:Dennis Zickefoose指出,当调用未定义的行为时,允许编译器执行任何操作,因此编译器和CPU都必须提供超出C++标准的保证,以便像这样的代码工作.我正在将问题扩展到现代C++编译器是否存在这个问题.

这是使用移动构造函数为大多数类定义移动赋值的一种非常简单的方法:

class Foo {
public:
  Foo(Foo&& foo);                     // you still have to write this one
  Foo& operator=(Foo&& foo) {
    if (this != &foo) {               // avoid destructing the only copy
      this->~Foo();                   // call your own destructor
      new (this) Foo(std::move(foo)); // call move constructor via placement new
    }
    return *this;
  }
  // ...
};

这个调用你自己的析构函数的序列是否跟随在标准C++ 11中的this指针安全位置新增？

如果std :: unordered_map的两个键具有相同的哈希值,那么标准是否保证它们会进入同一个桶？我们假设根据模板等式谓词键不相等,它们只有相同的哈希值.

额外问题:如果相同的哈希值并不意味着相同的存储桶,那么能够单独遍历存储桶的目的是什么？

我在Cygwin上安装了Clang,我尝试编译这段代码:

#include <iostream>
int main() {
  std::cout << "hello world!" << std::endl;
  return 0;
}

如果我这样做,那很好clang++ file.cpp.如果我这样做,它就不起作用clang++ file.cpp -std=c++11.我从标准标题中得到错误,如下所示:

In file included from file.cpp:1:
In file included from /usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/iostream:39:
In file included from /usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/ostream:39:
In file included from /usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/ios:39:
In file included from /usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/exception:150:
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/exception_ptr.h:132:13: error:
      unknown type name 'type_info'
      const type_info*

Cygwin Clang是不是开启了C++ 11,或者我可以做些什么来解决这个问题？

简介:我曾预料到,只要加载的值很少改变std::atomic<int*>::load,std::memory_order_relaxed就会接近直接加载指针的性能.我看到原子负载的性能远远低于Visual Studio C++ 2012上的正常负载,因此我决定进行调查.事实证明原子负载是作为比较和交换循环实现的,我怀疑它不是最快的实现.

问题:是否有某些原因std::atomic<int*>::load需要进行比较和交换循环？

背景:我相信MSVC++ 2012正在基于此测试程序对指针的原子加载进行比较和交换循环:

#include <atomic>
#include <iostream>

template<class T>
__declspec(noinline) T loadRelaxed(const std::atomic<T>& t) {
  return t.load(std::memory_order_relaxed);
}

int main() {
  int i = 42;
  char c = 42;
  std::atomic<int*> ptr(&i);
  std::atomic<int> integer;
  std::atomic<char> character;
  std::cout
    << *loadRelaxed(ptr) << ' '
    << loadRelaxed(integer) << ' '
    << loadRelaxed(character) << std::endl;
  return 0;
}

我正在使用一个__declspec(noinline)函数来隔离与原子负载相关的汇编指令.我做了一个新的MSVC++ 2012项目,添加了一个x64平台,选择了发布配置,在调试器中运行程序并查看了反汇编.事实证明,两者std::atomic<char>和std::atomic<int>参数最终会给出相同的调用loadRelaxed<int>- 这必须是优化器所做的事情.这是被调用的两个loadRelaxed实例的反汇编:

loadRelaxed<int …