c++ - 在没有未定义行为的情况下实现类似 std::vector 的容器
问题描述
std::vector
它可能会让一些编码人员感到惊讶,并且尽管可能令人惊讶,但如果没有编译器的非标准支持,就不可能实现。问题本质上在于对原始存储区域执行指针运算的能力。论文p0593:隐式创建对象用于低级对象操作,出现在@ShafikYaghmour 答案中,清楚地揭示了问题并提出修改标准,以便更容易实现容器等向量和其他法律级别的编程技术。
尽管如此,我想知道是否没有解决方法来实现一种等效于std::vector
仅使用语言提供的类型而不使用标准库的类型。
目标是在原始存储区域中一个一个地构造向量元素,并能够使用迭代器访问这些元素。这等效于 std::vector 上的 push_back 序列。
要了解这个问题,请简化std::vector
在 libc++ 或 libstdc++ 中执行的操作:
void access_value(std::string x);
std::string s1, s2, s3;
//allocation
auto p=static_cast<std::string*>(::operator new(10*sizeof(std::string)));
//push_back s1
new(p) std::string(s1);
access_value(*p);//undefined behavior, p is not a pointer to object
//push_back s2
new(p+1) std::string(s2);//undefined behavior
//, pointer arithmetic but no array (neither implicit array of size 1)
access_value(*(p+1));//undefined behavior, p+1 is not a pointer to object
//push_back s2
new(p+2) std::string(s3);//undefined behavior
//, pointer arithmetic but no array
access_value(*(p+2));//undefined behavior, p+2 is not a pointer to object
我的想法是使用一个从不初始化其成员的联合。
//almost trivialy default constructible
template<class T>
union atdc{
char _c;
T value;
atdc ()noexcept{ }
~atdc(){}
};
原始存储将使用此联合类型的数组进行初始化,并且始终在此数组上执行指针运算。然后在每个 push_back 的联合的非活动成员上构造元素。
std::string s1, s2, s3;
auto p=::operator new(10*sizeof(std::string));
auto arr = new(p) atdc<std::string>[10];
//pointer arithmetic on arr is allowed
//push_back s1
new(&arr[0].value) std::string(s1); //union member activation
access_value(arr[0].value);
//push_back s2
new(&arr[1].value) std::string(s2);
access_value(arr[1].value);
//push_back s2
new(&arr[2].value) std::string(s2);
access_value(arr[2].value);
上面这段代码中是否有任何未定义的行为?
解决方案
这是正在积极讨论的话题,我们可以在提案p0593 中看到这一点:为低级对象操作隐式创建对象。这是对这些问题的非常扎实的讨论,以及为什么如果不进行更改就无法修复它们。如果您对正在考虑的方法有不同的方法或强烈的看法,您可能需要联系提案作者。
它包括以下讨论:
2.3. 动态构建数组
考虑这个试图实现像 std::vector 这样的类型的程序(为简洁起见省略了许多细节):
……
实际上,此代码适用于一系列现有实现,但根据 C++ 对象模型,未定义的行为发生在点 #a、#b、#c、#d 和 #e,因为它们试图在不包含数组对象的已分配存储区域。
在#b、#c 和#d 位置,对char* 执行算术运算,在#a、#e 和#f 位置,对T* 执行算术运算。理想情况下,该问题的解决方案将使两种计算都具有定义的行为。
- 方法
上面的片段有一个共同的主题:他们试图使用他们从未创建过的对象。实际上,程序员认为他们不需要显式创建对象的一系列类型。我们建议识别这些类型,并仔细制定规则,消除显式创建此类对象的需要,而是隐式创建它们。
使用adc union 的方法有一个问题,即我们希望能够通过指针访问包含的数据,T*
即通过std::vector::data。作为 a 访问联合T*
将违反严格的别名规则,因此是未定义的行为。
推荐阅读
- python - TensorFlow Dense Layers:一维权重?
- mysql - 如何总结没有公共假期的假期?
- linux - debian 9 - 在关机时挂机,而不是在重启时挂机?
- mysql - 如何在单列中加入codeigniter中的两个表
- java - 如何迭代以下列表并打印其元素?
- android - 为什么我应用于 EditText 的 PhoneNumberFormattingTextWatcher 不是由并发 1 组成的格式
- java - 将所有先前活动的数据显示到一项活动
- python - 类型错误:generate_user_key() 缺少 1 个必需的位置参数:“密码”
- c# - Gsuite API 面临授权问题
- python - WebSocket Handler on_close 方法 async 实现tornado