Быстрый способ удаления элемента из массива типа 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 {
    }
}

Советую вам использовать стандартные функции std::remove() и std::remove_if(), которые делают практически тоже самое и std::vector::erase(), подробнее можно ознакомиться по ссылке.