Быстрый способ удаления элемента из массива типа 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(), подробнее можно ознакомиться по ссылке.

4 комментария

написал(а) SR_team (6 сентября 2016, 09:49)

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

ответить

написал(а) eJ (6 сентября 2016, 10:01)

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

ответить

написал(а) Аноним (21 сентября 2017, 16:33)

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

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

ответить
написал(а) Вова (2 декабря 2019, 19:16)

можно не удалять а просто поменять местами и уменьшить размер масива) просто отсекаем последний обєкт

auto it=v.end();
std::swap(v[i],*(it-1));
v.resize(v.size -1); //или v.pop_back();

ответить

Добавить комментарий