C++ std：：具有始终有效迭代器/指针/索引/键的向量
动机:使std::vector<std::unique_ptr<T>>可访问性达到std::vector<T>的速度。
std::vector有一个不便--如果向量增长/改变，您就不能存储指向元素的指针或索引。
为了克服这个问题，我们通常使用指针/ deque (如果只是增长)/ list /等等的向量。在创建、遍历和每个元素访问时，让我们的元素处于堆中有很大的开销。
要将指向元素的“指针”(或键)存储在向量中，我有返回的索引数组。
浓缩版：
struct Key{
int index; // index of key_indices
};
struct Element {
int key_index; // never changes
Value value;
};
std::vector<Element> data; // usual continious vector, no magic here
std::vector<int> key_indices; // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;
void emplace_back(){
// if have no free_indices
data.emplace_back();
key_indices.emplace_back(data.size() - 1);
data.back().key_index = key_indices.size() - 1;
}
Key get_key(std::vector<Element>::iterator iter){
return {iter->key_index};
}
Value& operator[](Key key){
return data[key_indices[key.index]].value;
}
Value& operator[](int index){
return data[index].value;
}
void erase(std::vector<Element>::iterator iter){
free_indices.push_back(iter->key_index);
update_indices(iter + 1, data.end(), -1);
data.erase(iter);
}
// same with insert, emplace_front, etc.
template<class iter>
void update_indices(iter from, iter to, int shift) {
for (auto it = from; it != to; ++it)
{
key_indices[it->key_index] += shift;
}
}并用于：
KeyContainer<Data> list;
list.emplace_back().back().x = 100;
list.emplace_back().back().x = 200;
auto key = list.get_key(list.end()-1);
list.erase(list.begin()); // all indices invalidated
std::cout << list[key].x << std::endl; // key still valid换句话说，键- is数组索引总是指向同一个元素，就像指向std::vector<std::unique_ptr<T>>元素的指针一样。
它在创建时大约比std::vector<std::unique_ptr<T>>/list快6-10倍，比deque快3-4倍(至少is 2015/clang是这样)。当遍历/索引访问时，速度与向量相同。和约10%的速度，与关键访问。我试着用指针代替索引，但没有看到任何区别。
对于这样的容器是否有现成的库解决方案(带有索引的向量-数组(或ptr反向数组))？
完整的代码(只是一个概念证明)
回答 1
Code Review用户
发布于 2016-10-21 15:32:16
快速检查(预期会有更多代码)。
代码的主要问题是没有封装在类中。
std::vector<Element> data; // usual continious vector, no magic here
std::vector<int> key_indices; // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;这些基本上是全局变量，任何人都可以访问变异变量(不仅是恶意的，而且是偶然的)。C++能够封装类的所有部分，并仅允许某些函数(方法)访问原始底层数据，从而防止类被意外滥用。
class MultiIndexToElement
{
private:
std::vector<Element> data; // usual continious vector, no magic here
std::vector<int> key_indices; // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;
public:
void emplace_back();
Key get_key(std::vector<Element>::iterator iter);
Value& operator[](Key key);
Value& operator[](int index);
void erase(std::vector<Element>::iterator iter);
private:
template<class iter>
void update_indices(iter from, iter to, int shift);
};现在我们可以清楚地看到界面了，有几件事您应该注意。
Const正确性.
不更改对象状态的方法应标记为const。这告诉编译器，调用此方法不会更改对象。
Key get_key(std::vector<Element>::iterator iter) const;
// ^^^^^这一点很重要，因为const reference在C++中经常将对象传递给函数，以避免复制对象的成本。
元素访问
通常容器允许两种形式的元素访问。变异访问和const访问。
Value& operator[](int index); // This allows mutating access.
Value const& operator[](int index) const; // This allows const accesses.Emplace Back.
通常放回(一种新的推退形式)。使用一个Element构造函数在适当的位置创建Elements。您的版本只允许元素具有零参数构造函数。
通常是这样写的：
template<Args... args>
void emplace_back(Args&& args...) {
data.emplace_back(std::forward<Args>(args)...); // pass arguments to constructor
.... /* Other stuff you need */
}Args...部件是C++14的一个新部分，因此您需要告诉编译器使用新版本的标准(这还不是默认的)。但通常这意味着将-std=c++14添加到命令行。
Templatization
您的代码不允许简单的模板化。实际上，您没有在上面的代码示例中定义Value。使用类周围的模板可以更容易地解决这个问题。
template<typename Value>
class MultiIndexToElement
{
/* STUFF */
};https://codereview.stackexchange.com/questions/144808
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号