Быстрый способ удаления элемента из массива типа std::vector (C/C++) или ArrayList (Java)

Давно известный прием, но вдруг кто-то не знает: если вам не важен порядок элементов в массиве, то удалить объект из середины массива элементарно — извлекаете последний элемент массива и вставляете его на место удаляемого.

Вот простой код для демонстрации:

#include <vector>
#include <stdio.h>
 
template <class T>
void remove_item( std::vector<T> &v, int i )
{
    // Сохраняем последний элемент
    const T item = v.back();
    // Удаляем последний элемент из массива
    v.pop_back();
    // Вставляем сохраненный элемента вместо элемента с индексом i
    v[i] = item;
}
 
 
int main()
{
    std::vector<int> v;
    v.push_back(10);
    v.push_back(11);
    v.push_back(12);
    v.push_back(13);
    v.push_back(14);
 
    printf("before:\n");
    for (int i = 0, count = v.size(); i < count; ++i)
    {
        printf("v[%d] = %d\n", i, v[i]);
    }
 
    remove_item(v, 1);
 
    printf("after:\n");
    for (int i = 0, count = v.size(); i < count; ++i)
    {
        printf("v[%d] = %d\n", i, v[i]);
    }
}

Вывод:

before:
v[0] = 10
v[1] = 11
v[2] = 12
v[3] = 13
v[4] = 14
after:
v[0] = 10
v[1] = 14
v[2] = 12
v[3] = 13

Обратите внимание, что в remove_item() происходит копирование последнего элемента. Так что если у вас что-то сложнее простых int, long, char или float, то этот код вам надо переписать.

Код для ArrayList (Java). Не проверял, но идея понятна:

public class ArrayListUtil {
    public static <T> void removeItem(ArrayList<T> v, int index) {
        T item = v.get(v.size() - 1);
        v.remove(v.size() - 1);
        v.set(index, item);
    }
 
    private ArrayListUtil {
    }
}
Отвратительно!Ужасно.НормальноХорошо.Отлично! (2 оценок, среднее: 5.00 из 5)
Загрузка...

Ваши комментарии к статье:

  1. vec.erase(vec.begin() + Номер_элемента); //На стандартах ниже 11 никогда не писал, так что хз будет ли там оно работать

    • В стандартном std::vector::erase() происходит перемещение всех элементов справа от удаляемого на один элемент влево. Этот способ физически не может быть быстрее предложенного мной.

  2. Зачем лишнее (возможно, глубокое) копирование?

    v[i] = std::move(v.back());
    v.pop_back();

Оставить комментарий: