Как использовать неизвестный (int-like) тип в качестве индекса в std :: vector?

Question

Я использую тип Id, который определен в другой части кода, который я использую:

typedef int Id;

Теперь мне предоставлено много объектов, каждый из которых имеет такой Id, и я хотел бы использовать Id в качестве индекса в std::vector, в котором хранятся эти объекты. Это может выглядеть примерно так:

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

Проблема в том, что std::vector использует свой собственный тип для индексации своих элементов: std::vector::size_type (почему это не шаблонно?).

Строго говоря, было бы лучше использовать std::map<Id, SomObj*>, но это было бы менее эффективно, и мне здесь действительно нужен массив (я знаю, что индексы всех объектов смежны и начинаются с 0 ). Другая проблема заключается в том, что typedef int Id может измениться на typedef long int Id или аналогичный в будущем ... (хотя это часть моего собственного кода, поэтому я управляю им, но в идеале мне следует разрешить изменить typedef в некоторые моменты, вот для чего используется typedef).

Как бы вы справились с этим? Может быть, использовать unordered_map<Id, SomeObj*>, где хеш-функция напрямую использует Id в качестве хэш-ключа? Будет ли это менее эффективным для памяти? (Я не совсем понимаю, как unordered_map выделяет свое пространство, учитывая, что диапазон хеш-функции заранее неизвестен?)

Answer 1

Вы можете передать любой целочисленный тип в качестве индекса для std::vector. Если оно не соответствует std::vector<T>::size_type (что обычно unsigned long), тогда значение будет неявно преобразовано.

Answer 2

почему это не шаблонно?

Поскольку стандартные контейнеры реализованы так, чтобы использовать самый большой тип без знака, который они могут разумно использовать.Если size_type равно unsigned int в вашей реализации, то по какой-то причине, и какова бы ни была причина, препятствующая реализации, использующей больший тип, все равно будет существовать, если вы попросите что-то еще [*].Кроме того, в вашем конкретном примере типы размеров должны быть без знака, и вы хотите использовать тип со знаком, так что это еще одно изменение, которое потребуется для поддержки того, что вы хотите сделать.

На практике size_type для стандартного контейнера (почти?) всегда size_t.Поэтому, если вы запросили больший вектор, у вас его не было бы, потому что вектор поддерживается непрерывным хранилищем.Вектор не сможет выделить массив размером более size_t байтов.

Чтобы использовать Id в качестве векторного индекса, вы можете либо полагаться на неявные преобразования, либо вы можете явно преобразовать (и, возможно,явно проверьте границы), чтобы было абсолютно ясно, что вы делаете.Вы также можете использовать утверждения, чтобы убедиться, что Id не больше size_type.Примерно так, хотя статическое утверждение, вероятно, было бы лучше:

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

A map<Id, SomeObj*> было бы хорошим вариантом, если используемые значения Id бывают разреженными.Если единственными допустимыми идентификаторами являются 1 и 400 000 000, то вектор будет довольно бесполезно использовать память.

Если вам от этого легче, помните, что литерал 0 имеет тип int, а не vector<SomeObj*>::size_type.Большинство людей не сомневаются в написании vec[0]: на самом деле это используется в стандарте.

[*] Даже если эта причина проста, «разработчики считают, что 4 миллиарда элементов достаточно для любого».

Answer 3

Напишите свою собственную оболочку контейнера, которая принимает Id в качестве типа индекса.Используйте map или unordered_map внутри для реализации контейнера.Программа против этой обертки.Если окажется, что эта реализация слишком медленная, переключитесь на vector внутри и конвертируйте Id индекс в vector::size_type (также, конечно, внутри).

Это самый чистый подход.Но на самом деле, vector::size_type будет очень большим целым типом без знака, поэтому преобразование из Id в vector::size_type всегда будет безопасным (но не наоборот!).

Answer 4

Проблема в том, что Id - это int (точнее, signed int), может быть отрицательным.Если Id был неподписанным типом, например typedef unsigned int Id;, проблем нет.

Если мое понимание пока верно, то я не понимаю, зачем кому-то использовать отрицательное число в качестве индекса для vector (или array).Чего мне не хватает?