我记得,从一开始,最流行的实现方法std::list<>::sort()是以自下而上的方式实现的经典Merge Sort算法(另请参阅是什么让gcc std :: list排序实现如此之快？).
我记得有人恰如其分地将这种策略称为"洋葱链"方法.
至少这是GCC实现C++标准库的方式(例如,参见这里).这就是旧版Dimkumware在标准库的MSVC版本中的STL,以及所有版本的MSVC到VS2013的情况.
但是,随VS2015提供的标准库突然不再遵循此排序策略.VS2015附带的库使用自上而下的 Merge Sort 的相当简单的递归实现.这让我感到很奇怪,因为自上而下的方法需要访问列表的中点才能将其分成两半.由于std::list<>不支持随机访问,找到该中间点的唯一方法是逐字遍历列表的一半.此外,在最开始时,有必要知道列表中的元素总数(在C++ 11之前不一定是O(1)操作).
尽管如此,std::list<>::sort()在VS2015确实如此.以下是该实现的摘录,它定位中点并执行递归调用
...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...
正如您所看到的,他们只是无意中使用std::next了遍历列表的前半部分并到达_Mid迭代器.
我想知道这种转变背后的原因是什么？我所看到的是std::next在每个递归级别上重复调用看似明显的低效率.天真的逻辑说这是慢的.如果他们愿意支付这种价格,他们可能希望获得回报.那他们得到了什么？我没有立即将此算法视为具有更好的缓存行为(与原始自下而上方法相比).我没有立即看到它在预先排序的序列上表现得更好.
当然,由于C++ 11 std::list<>基本上需要存储其元素数,这使得上面的效率略高,因为我们总是提前知道元素数.但这仍然不足以证明每个递归级别的顺序扫描是正确的.
(不可否认,我没有试图相互竞争实施.也许有一些惊喜.)
我正在查看条目在O(lg(N))操作中查找N位整数的日志基数2,并使用Bit Twiddling hacks 进行乘法和查找.
我可以很容易地看到该条目中的第二个算法是如何工作的
static const int MultiplyDeBruijnBitPosition2[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];
计算n = log2 v在哪里v知道2的幂.在这种情况下0x077CB531是一个普通的De Bruijn序列,其余的是显而易见的.
但是,该条目中的第一个算法
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, …我有一个在文件中定义的数组,在另一个我必须使用它,例如 -
/* a.c - defines an array */
int a[] = {1,2,3,4,5,6,7,8,9};
/* b.c - declare and use it. */
#define COUNT ((sizeof a)/(sizeof int))
extern int a[]; //size of array
.
.
.
int i;
for(i=0; i<COUNT; i++)
printf("%d", a[i]);
.
.
.
现在,当我尝试编译它时,它给了我一个错误,说sizeof不能用于不完整类型.
谁能告诉我如何在C/C++中处理这种情况？我不想在ac中使用数组下标
提前致谢
我看到VS2013增加了对C99的大量主要核心语言功能的支持.现在它支持复合文字,指定初始化器,可变参数宏,交错声明和语句,仅举几例.
这表明VS开发人员在Visual Studio中为C99支持迈出了重要的一步.然而,其中一些功能并不是C++语言的一部分,这似乎与之前宣布的开发策略有明显的偏差(例如"VS C编译器只支持那些也是C++一部分的C99功能").
那么,有什么官方或半官方的话说明发生了什么？我似乎无法在网上找到任何确定的内容.这些C99功能是否正式公布？是否有任何承诺继续在VS中支持C99？或者这只是某种"流氓"的非官方发展？
这是我之前的问题的后续问题,其中明显的共识是,prvalues的cv资格处理的变化只是一个相当小的和无关紧要的变化,旨在解决一些不一致性(例如返回prvalues并通过cv-qualified返回声明的函数)类型).
但是,我看到标准中的另一个地方似乎依赖于具有cv限定类型的constprvalues:通过临时实现转换初始化带有prvalues 的引用.有关措辞可在9.3.3/5中的多个地点找到
[...]如果转换的初始化程序是prvalue,则将其类型T4调整为键入"cv1 T4"([conv.qual])并应用临时实现转换([conv.rval])[...]
[...]否则,初始化表达式被隐式转换为"cv1 T1"类型的prvalue.应用临时实现转换,并将引用绑定到结果.
目的很明显是当我们进行实际的临时物化转换时
7.3.4临时实现转换
1类型T的prvalue可以转换为类型T的xvalue.此转换通过使用临时对象评估prvalue,从prvalue初始化类型为T的临时对象([class.temporary])它的结果对象,并生成一个表示临时对象的xvalue.[...]
T它作为输入接收的类型包括所需的cv资格.
但是在非类非数组prvalue的情况下,该cv资格如何在7.2.2/2中存活？
7.2.2类型
2如果prvalue最初具有类型"cv T",其中T是cv非限定的非类非数组类型,则在进行任何进一步分析之前将表达式的类型调整为T.
或者是吗？
例如,我们在这个例子中得到了什么样的临时性
const int &r = 42;
暂时const与否？我们能做到吗
const_cast<int &>(r) = 101; // Undefined or not?
没有触发未定义的行为？如果我没有弄错的话,最初的意图是const int在这种情况下获得临时性.它仍然是真的吗？(对于班级类型,答案很清楚 - 我们得到一个const临时的.)
我已经在Windows XP Pro 64位下使用Visual Studio 2005进行C和C++项目一段时间了.我在调试器中不时使用的一个流行技巧是记住程序的先前调试运行中的数字指针值(比如说0x00000000FFAB8938),将其添加到具有正确类型转换(例如((MyObject *) 0x00000000FFAB8938)->data_field)的监视窗口,然后在下一次调试运行期间观察对象占用的内存.在许多情况下,这是一个非常方便和有用的事情,因为只要代码保持不变,就可以预期分配的内存布局也将保持不变.简而言之,它有效.
但是,最近我开始在64位Windows Vista(家庭高级版)的笔记本电脑上使用相同版本的Visual Studio.奇怪的是,在该设置中使用这个技巧要困难得多.实际的内存地址似乎经常在运行之间发生变化,没有明显的原因,即使程序的代码根本没有改变.看起来实际地址并没有完全随机变化,它只是从固定的或多或少稳定的值集中选择一个值,但无论如何它使得这种类型的内存观察变得更加困难.
有谁知道Windows Vista中此行为的原因？是什么导致内存布局的变化？是否有一些外部入侵进程的地址空间来自其他[系统]进程？或者是Vista下的Heap API实现的一些怪异/特征？有没有办法防止这种情况发生？
如您所知,在标准的现代C语言中,指针上下文中使用的常量0值充当空指针常量,它将转换为特定于平台(甚至可能是特定于类型)的空指针值.
同时,C语言的早期版本,如C参考手册中描述的那样,并没有对指针和整数上下文做出太多区分,允许人们自由地比较并将整数分配给指针.如果没有弄错,在那个版本的C中,常量0没有特殊状态,这意味着将常量0的值赋给指针只会使它指向物理地址0(就像将42的值赋值给指针一样使它指向物理地址42).
在ANSI C中,事情发生了重大变化.现在将常量0赋给指针会将一些特定于平台的空指针值放入该指针.空指针值不需要由物理0值表示.
那么,在C语言历史的哪个阶段它从一个变为另一个？考虑到其特殊状态,K&R C是否已经将空指针的更高级概念与常数0相结合？或者K&R C是否仍然保证整数指针的物理分配,即使是常数0？
刚刚查看了C99和C11,试图弄清楚它们是否保证单个声明中的多个声明符按顺序从左到右执行.他们确实说每个完整的声明符都以序列点结束
6.7.5 C99声明者
6.7.6 C11声明者
3完整声明者是不属于另一个声明者的声明者.完整声明符的结尾是一个序列点.[...]
但似乎没有什么可以说个别初始化是按从左到右的顺序进行的.它真的没有说明,还是我错过了一些简单的东西？
int main() {
int i = 0;
int a = i++, b = i++;
// Are values of `a` and `b` specified here?
}
如果未指定订单,则它将取消以下实施模式
int array[N];
for (int *element = array, *element_end = element + N;
element != element_end;
++element)
*element = 0;
这让我感到非常惊讶.(我确实意识到我可以element_end用它进行初始化array + N.)
PS C++规范在这方面也不完全明确.它有一个脚注,表示T d1, d2;相当于T d1; T d2;,但这些都是非规范性的.因此显然是DR#1342
根据n4640中的5.2.2/4"函数调用"(n4659中的8.2.2/4),在调用者的上下文中创建和销毁函数参数.并且允许实现将函数参数的破坏延迟到封闭的完整表达式的末尾(作为实现定义的特征).请注意,选择不是未指定的,而是实现定义的.
(目前还不完全清楚这与3.3.3"块范围"(n4659中的6.3.3)是否一致,这似乎意味着函数参数具有块范围,然后是3.7.3"自动存储持续时间"(6.7.3)在n4659)中,它表示块作用域变量的存储一直存在,直到它们被创建的块出现.但是我们假设我在措辞中缺少/误解了一些内容.显然现在函数参数将有自己的范围)
据我所知,ABI要求GCC和Clang将函数参数的销毁延迟到完全表达式的末尾,即这是这些编译器的实现定义行为.我猜想在类似的实现中,只要在调用表达式中使用这些引用/指针,就可以返回对函数参数的引用/指针.
但是,以下示例在GCC中的段错误并且在Clang中正常工作
#include <iostream>
#include <string>
std::string &foo(std::string s)
{
return s;
}
int main()
{
std::cout << foo("Hello World!") << std::endl;
}
两个编译器都发出关于返回对局部变量的引用的警告,这在这里是完全合适的.快速检查生成的代码表明,两个编译器确实将参数的破坏延迟到表达式的末尾.但是,GCC仍故意返回"null引用" foo,导致崩溃.与此同时,Clang表现为"按预期",返回对其参数的引用,该参数的s存活时间足以产生预期的输出.
(简单来说,GCC在这种情况下很容易愚弄
std::string &foo(std::string s)
{
std::string *p = &s;
return *p;
}
它修复了GCC下的段错误.)
在这种情况下GCC的行为是否合理,假设它保证参数的"晚期"破坏？我是否遗漏了标准中的其他段落,即返回对函数参数的引用始终未定义,即使它们的生命周期是由实现扩展的？
似乎C++ 11和C++ 14对prvalues的cv资格进行了不同的处理.
C++ 11坚持自C++ 98以来一直存在的"经典"方法:根据3.10/4 "非类prvalues总是有cv-unqualified类型".
C++ 14在3.10/4中包含类似的措辞,但是它作为注释呈现:"[注意:类和数组prvalues可以具有cv限定类型;其他prvalues总是具有cv非限定类型.请参阅第5章.结束说明]"
在第5条中,它说:
6如果prvalue最初具有类型"cv T",其中T是cv非限定的非类非数组类型,则在进行任何进一步分析之前将表达式的类型调整为T. 1
这个5/6条目是C++ 14中的新增内容.现在,它使用与参考类型结果一直使用的相同方法来处理prvalues的cv资格(参见5/5).
这种变化的原因是什么？C++ 11和之前拒绝非class prvalues拥有任何cv资格的权利.C++ 14表示非类非数组prvalues 可以具有cv资格,但在进一步分析之前,这些cv资格被丢弃.
我的猜测是,有一些新的(对于C++ 14)语言功能可以在某种情况下(在上述调整发生之前)以某种方式"看到"prvalues的cv资格.它们存在吗？如果是这样,这些功能是什么？2
问题源于以下上下文:想象一个编译器,它在内部实现this类的隐藏参数X作为类型的变量X *const.由于编译器需要this作为prvalue 公开,这const不应该导致C++ 11(或之前)中的任何问题,其中标量prvalues永远不会被cv限定.但是C++ 14呢？如果完全相同的编译器将其暴露this为类型的prvalue X *const,是否可能导致问题？
1在C++ 14中,5/6与3.10/4中的音符之间似乎存在矛盾,但音符无论如何都不是规范性的.我正在使用该文本的草稿版本.
2我最初的猜测是decltype.我甚至认为我尝试时找到了答案
std::cout << std::is_same<decltype((const int) 0), const int>::value << std::endl;
在海湾合作委员会,其产出1.但是,看到Clang和VC++输出0(并且该规范decltype似乎不支持这种行为)我倾向于认为这只是GCC中的一个错误(从6.1开始)