代码之家 › 专栏 › 技术社区 › Frank

如何使用未知(类似int)类型作为std::vector的索引?

typedef vector stl data-structures c++

Frank · 技术社区 · 14 年前

我在用打字机 Id

typedef int Id;

现在我得到了许多物品,每一件都带有这样一个标记 身份证件 身份证件 作为索引到 std::vector 存储这些对象的。它可能看起来像这样:

std::vector<SomeObj*> vec(size);
std::pair<Id, SomeObj*> p = GetNext();
vec[p.first] = p.second;

标准::向量 使用其自己的类型索引其元素: std::vector::size_type

严格来说,最好是 std::map<Id, SomObj*> ,但这样效率会降低,而数组才是我真正需要的(我知道所有对象的索引都是连续的,并且从 0 typedef int Id 可能会变为 typedef long int Id typedef 在某些情况下;这就是typedef的用途)。

unordered_map<Id, SomeObj*> 身份证件 作为哈希键?这会不会降低内存效率?(我不完全明白 unordered_map 如果哈希函数的范围事先未知,则分配其空间?)

4 回复 | 直到 14 年前

Anthony Williams 14 年前

您可以传递任何整数类型作为 std::vector . 如果不匹配 std::vector<T>::size_type (这通常是 unsigned long )然后该值将被隐式转换。

Steve Jessop 14 年前

size_type unsigned int 在您的实现中,这是有原因的,无论是什么原因阻止了实现者使用更大的类型,如果您要求其他的[*],那么仍然存在。另外,对于您的特定示例,大小类型必须是无符号的,并且您希望使用有符号的类型,因此这是支持您希望执行的操作所需的另一个更改。

大小\u类型 size_t 大小\u t 字节。

Id 作为一个向量索引,您可以依赖于隐式转换,也可以显式转换(也许还有显式边界检查),以便绝对清楚地知道您在做什么。您还可以使用资产来确保 身份证件 不大于 大小\u类型 . 类似这样的情况,尽管静态断言可能更好:

assert(std::numeric_limits<Id>::max() <= std::numeric_limits<std::vector<SomeObj*>::size_type>::max());

A map<Id, SomeObj*> 如果使用的Id值是稀疏的,这将是一个很好的选择。如果唯一有效的id是1和400000000,那么向量将相当浪费内存。

如果这让你觉得更舒服,记住 0 int vector<SomeObj*>::size_type . 大多数人对写作毫不犹豫 vec[0] :标准中确实使用了。

[*]即使这个理由是公正的,“实施者认为40亿元素对任何人都足够”。

Konrad Rudolph 14 年前

编写自己的容器包装器 Id 作为索引类型。使用 map 或 unordered_map 在内部实现容器。针对此包装器的程序。如果发现这个实现太慢,请切换到 vector 内在地改变你 身份证件 索引到 vector::size_type (当然,内部也是如此)。

向量::大小\类型 身份证件 到 向量::大小\类型

Arun 14 年前

问题是, Id int (更准确地说, signed int 身份证件 是无符号类型,例如。 typedef unsigned int Id;

如果到目前为止我的理解是正确的,那么我不明白为什么会有人想用负数作为 vector array