Reference:
- "전문가를 위한 C++" / 마크 그레고리 / 한빛 미디어
- "Optimized C++" / 커트 건서로스 / 한빛 미디어
std::array나 std::vector와 같은 연속형 자료구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적이다(시간 복잡도: O(n)). 그래서 연결 리스트와 같은 형태의 자료 구조가 등장한다.
기본적인 연결 리스트로 구성하려면 포인터를 하나 가지고 있어야 하고, new와 delete 연산자를 이용하여 메모리를 할당하고 해제할 수 있어야 한다. c++ STL 표준 라이브러리에서 기본적인 연결 리스트에 대한 래퍼 클래스인 std::forward_list 클래스를 제공한다. 리스트에서 가장 기본적인 것만 남긴 순차 컨테이너이다.
1. std::forward_list
source: https://hackingcpp.com/cpp/std/sequence_containers.html
std::forward_list는 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공한다. 성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다. 원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 제공한다. 이러한 기능은 기본적인 연결 리스트의 메모리 사용량이나 성능에 영향을 주지 않는다.
std::list와의 차이점
- std::forward_list에는 std::list와 다르게 순방향 반복자만 제공된다.
- 삽입할 때 다른 접근 방법이 필요하다. std::forward_list에는 insert() 메서드 대신 insert_after() 메서드가 있다. 또한 before_begin()이라는 함수로 리스트의 첫번째 요소 앞을 가리키는 반복자를 얻을 수 있다.
- forward_list의 요소에는 다음 요소를 가리키는 포인터만 있기에 첫번째 요소 앞에 삽입할 수 있는 다른 방법은 없다.
2. std::forward_list 멤버 함수
원소의 삽입: push_front, insert_after
std::forward_list에서 원소를 삽입할 때에는 push_front()와 insert_after() 함수를 사용한다. 연결 리스트에서 원소 삽입은 노드의 포인터 조직으로 구현되므로, 삽입 후 다른 원소를 이동할 필요가 없다. 그러므로 std::forward_list의 삽입 함수는 모두 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작한다(시간 복잡도: O(1)).
std::forward_list<int> fwa_list = {1, 2, 3};
fwd_list.push_front(0); // 맨 앞에 0 추가: {0, 1, 2, 3,}
auto it = fwd_list.begin(); // 첫 번쨰 원소를 가리키는 반복자
fwd_list.insert_after(it, 5); // 맨 처음 원소(반복자가 가리키는 원소) 뒤에 5 추가: {0, 5, 1, 2, 3}
// it 반복자는 여전히 같은 위치를 가리킨다.
fwd_list.insert_after(it, 6); // 같은 위치에 6 추가: {0, 6, 5, 1, 2, 3}원소의 삭제: pop_front, erase_after
std::forward_list에서 원소를 삭제할 때에는 pop_front()와 erase_after() 함수를 사용한다. pop_front() 함수는 리스트의 맨 처음 원소를 제거한다. 원소 이동이 필요하지 않으므로 시간 복잡도는 O(1)이다.
erase_after는 두 가지 형태로 함수가 오버로딩되었다.
1) 특정 원소를 가리키는 반복자를 인자로 받아 바로 다음 위치의 원소를 삭제.
2) 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 인자로 받아 삭제.
마찬가지로 erase_after() 함수를 사용하여 일련의 원소를 삭제하는 시간 복잡도는 삭제할 원소 개수의 선형 함수 형태로 나타난다. 이는 연결 리스트에서 각각의 노드는 전체 메모리의 임의 위치에 산재되어 있으며, 각각의 노드에 사용된 메모리를 개별적으로 해제해야 하기 때문이다.
std::forward_list<int> fwd_list = {1, 2, 3, 4, 5};
fwd_list.pop_front(); // 맨 앞 원소를 삭제: {2, 3, 4, 5}
auto it = fwd_list.begin();
fwd_list.erase_after(it); // 맨 앞 다음 원소를 삭제: {2, 4, 5}
// 반복자가 가리키는 원소의 다음 원소를 삭제
fwd_list.erase_after(it, fwd_list.end()); // 맨 앞 원소 다음부터 맨 마지막 원소까지 삭제: {2}
std::forward_list의 기타 멤버 함수: remove, remove_if, sort
반복자로 원소 위치를 지정하여 삭제하는 erase() 함수 외에도 원소 값을 검사하여 삭제하는 remove()와 remove_if() 함수도 제공한다.
remove() 함수는 삭제할 원소 값 하나를 매개변수로 받는다. 이 함수는 저장된 데이터 타입에 정의된 등호(==) 연산자를 사용하여 전달된 값과 일치하는 모든 원소를 찾아 삭제한다. 저장된 데이터 타입에서 등호 연산이 지원되지 않으면 remove() 함수를 사용할 수 없으며, 컴파일 에러가 발생한다. remove() 함수는 오직 등호 연산에 근거하여 원소를 삭제하며, 다른 조건에 근거하여 삭제 여부를 결정할 수 없다.
좀 더 유연한 조건부 삭제를 수행하려면 remove_if() 함수를 사용할 수 있다. remove_if()는 데이터 원소 값 하나를 인자로 받아 bool 값을 반환하는 조건자 함수를 인자로 받는다. 그리고 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제한다. (최신 c++버전을 사용한다면 조건자 자리에 람다 표현식을 사용할 수 있다.)
연결 리스트에서 remove_if() 함수를 이용한 조건부 원소 삭제
시민들의 정보를 이용하여 선거권이 없는 사람을 가려내기
#include <string>
#include <iostream>
#include <forward_list> // STL이 제공하는 '연결 리스트' 자료구조
using namespace std;
// citizen 구조체
struct citizen
{
string name;
int age;
};
int main(){
// 리스트 초기화
forward_list<citizen> citizens = {
{"Kim", 22}, {"Lee", 25}, {"Park", 18}, {"Jin", 16}
};
cout << "전체 시민들: " << endl;
for(const auto &c : citizens)
cout << c.name << " : " << c.age << endl;
// 나이 정보를 이용하여 투표권이 없는 시민을 리스트에서 제거
// 람다 표현식 사용
citizens.remove_if([](const citizen &c) {
// 나이가 19세보다 작으면 리스트에서 삭제
return (c.age < 19);
});
cout << "투표권이 있는 시민들: " << endl;
for(const auto &c : citizens)
cout << c.name << " : " << c.age << endl;
return 0;
}remove, remove_if, 두 함수는 리스트 전체를 순회하면서 조건에 맞는 원소를 모두 삭제하므로 O(n)의 시간 복잡도를 갖는다.
forward_list는 원소 데이터를 정렬하는 sort() 멤버 함수를 제공한다. array나 vector 등에 저장된 데이터는 범용적인 std::sort(first_iterator, last_iterator) 함수를 이용하여 원소를 정렬할 수 있지만, 연결 리스트와 같은 자료구조는 특정 원소에 임의 접근이 불가능하고, 사용되는 반복자가 std::array/vector와 다르기에 std::sort() 함수를 사용할 수 없다. 따라서 자체적으로 sort 기능을 멤버 함수로 제공한다.
forward_list 자료구조의 sort 멤버 함수는 선형 로그 시간 복잡도 O(nlogn)을 갖는다.
#include <iostream>
#include <forward_list>
using namespace std;
int main(){
std::forward_list<int> list = {23, 0 , 1, -3, 34, 17};
// 오름차순 정렬
list.sort();
cout << "오름차순 정렬" << endl;
for(auto &c : list){
cout << c << " ";
}
cout << endl;
// 내림차순 정렬
list.sort(greater<int>());
// std::greater<int>는 표준으로 제공되는 비교 함수 객체이다.
// 또는 compare 함수를 구현하고, 함수 이름을 인자로 전달하여도 된다.
/*
bool compare(int a, int b){
return a > b;
}
...
list.sort(compare);
*/
cout << "내림차순 정렬" << endl;
for(auto &c : list){
cout << c << " ";
}
cout << endl;
}