Сложность уменьшения размера вектора STL

#c #vector #stl #time-complexity #stdvector

#c #вектор #stl #сложность по времени #stdvector

Вопрос:

Какова временная сложность сокращения (уменьшения размера) an std::vector<int> ? Я понимаю, что он не перераспределяет память. В пользовательских классах может потребоваться вызвать деструкторы для всех удаляемых элементов. Но с целыми числами сокращение будет происходить за постоянное время?

1. Основные типы не имеют деструкторов, но vector , вероятно, будут использоваться placement-new внутри и могут по-прежнему вызывать для них деструкторы, что разрешено. Компилятор может быть достаточно умен, чтобы понять, что вызовы деструктора не работают, и оптимизировать их, или vector реализация может быть специализированной, чтобы реализовать это и просто пропустить их, в любом случае, в результате чего изменение размера будет фактически равно O (1), поскольку единственной операцией будет просто уменьшение size() значения. Это действительно зависит от реализации `вектора`, я не думаю, что описана временная сложность для разных типов.

Ответ №1:

Зависит от того, что вы подразумеваете под «уменьшением размера» вектора.

Обычно люди удаляют элементы из вектора с помощью вызова erase . Если вы удаляете содержимое в конце вектора, тогда все просто, и все, что происходит, это то, что элементы уничтожаются — что, как указал Реми, является недопустимым для int s .

Если вы удаляете данные не с конца, а откуда-то еще, то элементы должны быть перетасованы, а это требует времени. К счастью для вашего варианта использования, копирование an int обходится дешево, но оно не равно нулю. Таким образом, удаление элемента из начала / середины вектора не может быть постоянным временем.

Примечание: вызов resize вектора для уменьшения его размера удаляет элементы в конце.

1. Включает ли какая-либо библиотека (о которой вы знаете) специализации, чтобы избежать вызова псевдо-dtor для простых типов, таких как int ?

2. Есть ли у вас доказательства (скажем, godbolt) библиотеки, вызывающей такой псевдоним?

3. @JerryCoffin Даже в моих руководствах по векторам объясняется, как выполнить эту оптимизацию. Я бы ожидал, что это сделают профессионалы. lokiastari.com/blog/2016/03/19/vector-simple-optimizations /…

4. @MarshallClow — да, я бы использовал resize() для уменьшения размера.

5. Извините, мне пришлось некоторое время поработать там. Мой ответ Маршаллу заключается в том, что нет, я не тестировал, поэтому я не уверен. @MartinYork: подумав об этом, я подозреваю, что в этом нет необходимости. Цикл, который вызывает dtor для типа, в котором dtor является nop, вероятно, следует исключить как мертвый код (но см. Выше — я не проверял, чтобы быть уверенным).