09. [C++] 벡터와 리스트에서의 erase/remove 사용법

벡터와 리스트에서의 erase 사용법에 대해 알아보기 전에 벡터와 리스트를 잠시 비교해보겠습니다.

vector와 list는 모두 sequence container로, sequence container에는 forward_list, list, deque, vector, array 등이 있습니다. 

list의 경우에는 bidirectonal iterator를 사용하는 이중 연결리스트(앞뒤 이동만 가능)이고, 

vector의 경우에는 contiguous iterator를 사용하는 연속된 배열(Random access 지원)이다. 

 

vector는 인덱스 접근이 빠르고 메모리를 효율적으로 사용할 수 있다는 장점이 있지만 연속된 배열이기 때문에 앞이나 중간에 데이터를 삽입하거나 삭제하면 해당 원소의 뒤 원소들을 모두 이동시켜야 하기 때문에 비효율적입니다. 

반면 List는 포인터로 연결된 노드들로 구성되어 컨테이너의 앞 뒤에 원소를 모두 삽입, 삭제할 수 있고 벡터보다 빠르게 동작할 수 있습니다. 

 

따라서 벡터는 push front가 의도적으로 불가능하여 push_front() 멤버함수가 존재하지 않고,

List는 push_front()와 push_back()이 멤버함수로 모두 존재합니다. 

 

이제, erase와 remove의 차이에 대해서 설명해보겠습니다. 

erase는 vector와 list 모두에 멤버함수로 존재하는데 erase는 컨테이너 내부 구조(메모리, 사이즈 등)을 실제로 수정해야하는 함수이기 때문입니다 

좀 더 구체적으로 값 찾기, 정렬와 같이 실제 내부 구조(메모리, 사이즈 등)의 변경이 필요하지 않은 경우에는 algorithm 헤더를 include 하여 공통적으로 사용할 수 있고, 실제 메모리 변경이 필요한 경우에는 컨테이너에서 효율적으로 동작할 수 있도록 설계된 멤버함수를 사용할 수 있게 stl이 구성되어 있습니다. 

 

 

 

erase의 경우 정확히 특정 위치의 요소를 제거해야하기 때문에 vector와 list모두 iterator로 접근이 필요하며 값으로는 직접 접근해서 삭제할 수 없기 때문에 iterator로 지정한 위치의 원소를 삭제합니다. iterator로 위치를 지정해서 삭제한다는 공통점이 있지만 내부동작방식은 완전히 다릅니다. vector는 연속된 배열이기 때문에 삭제를 위해서는 뒤 원소들 전부를 한칸씩 앞으로 복사해야하기 때문에 비효율적으로 동작하게 됩니다. list의 경우 연결리스트이기 때문에 포인터만 수정하면 효율적으로 동작할 수 있습니다. 

 

remove는 algorithm 헤더를 include하여 사용하며 실제 삭제를 수행하지 않고 컨테이너 내에서 삭제할 값이 아닌 원소들을 처음부터 끝까지 순회하며 삭제 대상을 만나면 삭제 대상이 아닌 원소들을 그 위치에 덮어쓰기만 수행합니다. 따라서 실제 삭제를 수행하려면 remove를 수행한 이후 쓰레기 값을 삭제해주는 remove erase idom을 사용해야합니다. 

c++20 이후로는 이를 편하게 수행하기 위해 매게변수로 컨테이너를 전달하면  remove-erase idiom을 내부적으로 처리해주게 됩니다. 

#inlcude <algorithm> 
#include <vector>

std::vector<int> v{1, 2, 3, 4, 5};

v.erase(std::remove(v.begin(), v.end(), 3), v.end());
v.erase(std::remove_if(v.begin(), v.end(), [](int x) { return x > 3; }), v.end());

erase(v, 3) //c++ 20
std::erase_if(v, [](int x) { return x > 3; }); //c++20

 

한편 list의 경우에는 remove가 멤버함수로도 존재하는데,  remove 멤버함수를 사용하면 지정한 값을 가진 원소를 실제로 삭제하여 크기도 즉시 줄어들게 됩니다. 이는 list는 연결 리스트 구조이기 때문에 단순이 이전 노드와 다음 노드를 서로 연결만 하면 되기 때문에 완전 삭제가 가능합니다. 따라서 list는 효율적으로 remove 기반 완전 삭제가 가능하기 때문에 remove()가 멤버함수로 제공됩니다. 

#include <vector>
#include <list>
#include <iostream>
#include <algorithm> //remove 사용용
 
template <typename Container>
void print_container(const Container& c)
{
    for (const auto& val : c)
        std::cout << val << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::vector<int> c{1, 2, 3, 4, 5};
    std::list<int> l{1, 2, 3, 4, 5};
    print_container(c);
    print_container(l);
 
    c.erase(c.begin() + 2); //ok
    //c.erase(3); //error erase value 접근 미지원원
    print_container(c);

    //l.erase(l.begin() + 2); //error random access 미지원원
    //l.erase(3); //error erase value 접근 미지원
    l.erase(std::next(l.begin(), 2));
    print_container(l);

    remove(c.begin(), c.end(), 2); //ok 벡터의 크기 그대로 -> 실제 삭제를 위해서는 erase-remove idiom사용 필요 
    //c.remove(2); //error
    print_container(c);

    remove(l.begin(), l.end(), 2); //ok 벡터의 크기 그대로
    l.remove(1); //ok 실제 삭제되어 erase - remove idiom 불필요 
    print_container(l);
}

 

 

끝으로 cpp conference 링크에서 vector와 list의 멤버변수 및 c++ 20 erase 문법을  확인하실 수 있습니다.

std::vector - cppreference.com

std::vector - cppreference.com

std::list - cppreference.com

std::list - cppreference.com

std::erase, std::erase_if(std::vector) - cppreference.com

std::erase, std::erase_if(std::vector) - cppreference.com