Ожидаемое содержание динамического вектора

Question

Я должен хранить целочисленные значения, которые отображаются на другие целые числа.Один из способов сделать это - использовать std :: map m.Но тогда для получения значения, используя m [int] или m.find (int), будет порядок logN (N - количество элементов) времени.В моем случае N довольно большое (до 2 ^ 30).Я думал, что использование std :: vector будет быстрее для доступа, поскольку каждый ключ теперь отображается на индекс элемента вектора, к которому можно получить доступ за O (1).Ключ встречается в случайном порядке, и они не могут быть смежными.Например, если вектор имеет размер 10, то не все 10 элементов являются допустимыми, и может быть только 6 допустимых элементов, а остальные мне нужно заполнить -1.Я написал небольшую программу и с удивлением обнаружил вывод ниже:

int main () {
   std::vector<int> v;
   v.assign(6, -1); 
   v[3] = 10; 
   v[10] = 100;
   cout << v.size() << v.capacity() << endl ;
   cout << v[3] << v[10] << endl; 
}

Вывод: size = 6, емкость = 6, V [3] = 10, v [10] = 100.Я не понимаю, как размер и емкость равны 6, но v [10] имеет допустимое значение, или я не встретил сегмента.неисправность.Может кто-нибудь объяснить это?Насколько я понимаю, функция push_back динамически изменяет размер вектора, когда vector.size> vector.capacity, оператор [] также делает это?Чтобы быть в безопасности, я переписал приведенный выше код следующим образом:

int main () {
   std::vector<int> v;
   v.assign(6, -1);
   int key = getKey(); 
   if (key < v.size()) 
      v[key] = <correct value>;
   else {
      v.resize(key, -1); // I want to assign -1 to invalid elements
      v[key-1] =  <correct value>;
   }
}

Кажется, он работает нормально, но будет ли лучше сравнить ключ с v.capacity (), а затем изменить размер вектора.

Answer 1

Насколько я понимаю, функция push_back динамически изменяет размер вектора, когда vector.size> vector.capacity, оператор [] также делает это?

Нет, это не так.Если вы обращаетесь к концу вектора, используя operator[], поведение вашего кода не определено.Вы должны явно изменить размер вектора, чтобы убедиться, что он достаточно велик для любого доступа через operator[].

std::vector::at() аналогичен operator[], но выполняет проверку ошибок и, следовательно, может быть полезен для определения-пределенного доступа (но при выполнении этих дополнительных проверок будет снижена производительность).

Если вы ожидаете, что ваша структура данных будет относительно разреженной, возможно, стоит подумать о std::unordered_map для этой работы.

В любом случае, я надеюсь, вы понимаете, что 2^30 int займет достаточно ОЗУ (4 ГБ, если int имеет ширину 32 бита).Даже если ваше аппаратное обеспечение / операционная система позволит вам иметь такой большой массив, вам, возможно, придется предварительно выделить его, а не увеличивать его за счет повторного перераспределения.

Answer 2

std::vector<int> v;
v.assign(6, -1); 
v[3] = 10; 
v[10] = 100;  // Unlucky with this statement

Размер вектора просто 6 .И индекс доступа от 0 до 5 .Ваш первый фрагмент имеет неопределенное поведение, и вам не повезло, что он не сломался при доступе к индексу 10 .Если существует понятие связи ключа со значением, тогда ассоциативные контейнеры, такие как std::map или std::multimap, будут лучше, чем контейнер последовательности, такой как std::vector.