std::forward_list
- std::array, std::vector와 같은 연속된 자료구조는 데이터 중간에 자료를 추가, 삭제하는 작업이 매우 비효율적임
- 따라서 연결 리스트 기반 컨테이너가 등장함
- 연결 리스트를 구성하는 중에 포인터와 관련된 버그 양산을 막기 위해 연결 리스트 wrapper class인 std::forward_list 클래스를 제공함
std::forward_list의 기본적인 기능
- 연결 리스트의 성능을 유지하면서 기본적인 기능을 제공함
- 성능 유지를 위해 전체 리스트 크기를 반환하거나, 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않음
- front() 함수는 제공하지만, 거꾸로 움직이는 back() 함수는 제공하지 않음
- 원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 제공함
- 두 번째 템플릿 매개변수에 사용자 지정 할당자를 지정할 수 있음
std::foward_list에서 원소 삽입
- 원소 삽입할 때 push_front()와 insert_after() 함수를 사용
- push_front()
- 마지막 원소에 직접 접근할 수 없으므로 push_back() 함수는 제공하지 않음
- insert_after()
- 특정 위치에 원소를 삽입하려면 insert()가 아닌 insert_after() 를 사용해야 한다
- 해당 위치 앞에 있는 원소의 next 포인터를 수정해야 하기 때문
- 리스트의 원소 크기에 영향을 받지 않으며, 시간 복잡도는 O(1) 이다.
// 연결 리스트 생성
std::forward_list<int> fwd_lst = { 1, 2, 3 };
// 맨 앞에 0 추가: { 0, 1, 2, 3 }
fwd_list.push_front(0);
auto it = fwd_list.begin();
// 맨 처음 원소 뒤에 5 추가: { 0, 5, 1, 2, 3 }
fwd_list.insert_after(it, 5);
// 같은 위치에 6 추가 { 0, 6, 5, 1, 2, 3 }
fwd_list.insert_after(it, 6);
- emplace_front()와 emplace_after() 함수도 제공함
- 추가적인 복사, 이동을 하지 않기 때문에 효율적이다
std::foward_list에서 원소 삭제
- pop_front()
- 리스트의 맨 앞 원소를 제거
- 원소의 이동이 필요하지 않으므로, 시간복잡도는 O(1)
- erase_after()
- 두 가지 형태로 제공
- (1) 특정 원소를 가리키는 반복자를 인자로 받아서 다음 위치의 원소를 제거
- (2) 일련의 원소를 제거하기 위해 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 인자로 받는다
- 시간 복잡도는 삭제할 원소의 개수의 선형 함수 형태로 나타난다
// 연결 리스트 생성
std::forward_list<int> fwd_list = { 1, 2, 3, 4, 5};
// 맨 앞 원소 삭제: { 2, 3, 4, 5 }
fwd_list.pop_front();
auto it = fwd_list.begin();
// 맨 앞의 다음 원소를 삭제: { 2, 4, 5 }
fwd_list.erase_after(it);
// 맨 앞 원소 다음부터 맨 마지막 원소까지 삭제: { 2 }
fwd_List.erase_after(it, fwd_list.end());
std::forward_list의 기타 함수
- 원소 값을 검사하여 삭제하는 remove()와 remove_if() 함수 제공
- remove()
- 삭제할 원소 값 하나를 매개변수로 받는다
- 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전달된 값과 일치하는 모든 원소를 찾아 삭제함
- 등호 연산이 지원되지 않으면 remove()를 사용할 수 없고, 이 경우 컴파일러 에러가 발생
- 등호 연산 외 다른 조건에 근거하여 삭제 여부를 결정할 수 없음
- remove_if()
- remove()보다 유연한 조건부 삭제를 수행한다
- 데이터 원소 값 하나를 인자로 받아 bool 값을 반환하는 조건자 함수를 인자로 받는다
- 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제함
- remove(), remove_if() 함수 모두 리스트 전체를 순회하며 조건에 맞는 원소를 모두 삭제함 --> O(n)
- remove_if() 함수를 이용한 예제
#include <iostream>
#include <string>
#include <forward_list>
struct citizen
{
std::string name;
int age;
};
std::ostream &operator<<(std::ostream &os, const citizen &c)
{
return (os << "[" << c.name << ", " << c.age << "]");
}
int main()
{
std::forward_list<citizen> citizens = {
{"Kim", 22}, {"Lee", 25}, {"Park", 18}, {"Jin", 16}
};
// 깊은 복사
auto citizens_copy = citizens;
std::cout << "전체 시민들: ";
for(const auto &c : citizens)
std::cout << c << " ";
std::cout << std::endl;
citizens.remove_if([](const citizen &c) {
// 나이가 19세 보다 작으면 리스트에서 제거
return (c.age < 19);
});
std::cout << "투표권이 있는 시민들: ";
for(const auto &c : citizens)
std::cout << c << " ";
std::cout << std::endl;
citizens_copy.remove_if([](const citizen &c) {
// 나이가 18세가 아니라면 리스트에서 제거
return (c.age != 18);
});
std::cout << "내년에 투표권이 생기는 시민들: ";
for(const auto &c : citizens_copy)
std::cout << c << " ";
std::cout << std::endl;
return 0;
}
std::forward_list의 정렬
- std::foward_list는 원소 데이터를 정렬하는 sort() 멤버 함수를 제공함
- std::array, std::vector에 저장된 데이터는 범용적인 std::sort 이용이 가능함
- 연결 리스트 같은 자료 구조는 특정 원소에 임의 접근이 불가능하므로 std::sort() 사용 불가능
- std::foward_list의 반복자는 std::array, std::vector의 반복자와는 다르다
- std::forward_list에서 제공하는 sort() 함수는 두 가지 형태를 지원
- (1) < 연산자를 기반으로 정렬
- std::less을 비교자로 사용
- 이 비교자는 첫 번째 인자가 두 번째보다 작으면 true를 반환하며, 사용자 정의 타입 원소를 사용할 경우에는 < 연산자가 재정의되어 있어야 한다
- (2) 매개변수로 전달된 비교자(comparator)를 사용
- 다른 기준을 이용하여 원소를 비교하고 정렬하려면 이항 조건자를 지정할 수 있다.
- 둘 다 선형 로그 시간 복잡도 O(nlogn)을 갖는다
std::forward_list<int> list1 = {23, 0, 1, -3, 34, 32};
list1.sort(); // {-3, 0, 1, 23, 32, 34} 순서로 바뀜
list1.sort(std:greater<int>()); // {32, 32, 23, 1, 0, -3} 순서로 바뀜
- std::greater는 표준으로 제공되는 비교 함수 객체이고, 원소를 내림차순으로 정렬하기 위한 > 연산자에 대한 래퍼임
std::forward_list에서 제공하는 기타 멤버 함수
- reverse()
- unique()
- 홀로 나타나는 원소는 놔두고 인접하여 중복되는 원소에 대해서는 첫 번째만 남겨두고 나머지는 제거한다
- 두 가지 타입
- (1) 인자가 없는 형태, 원소 타입의 등호 연산자를 사용하여 같은지 판단
- (2) bool 값을 반환하는 이항 조건자를 인자로 받으며, 리스트 원소 타입의 인자를 두 개 받는다
- 시간 복잡도 : 선형 함수로 표현됨
- 각각의 원소를 나머지 원소 전체와 비교하는 형태로 동작하는 것이 아님
- 서로 인접한 원소끼리 같은지를 판단하고, 서로 같으면 앞에 있는 원소는 남기고, 뒤의 원소를 제거
- 따라서 유일한 원소들만 남게 하려면 먼저 리스트를 정렬한 후 unique()를 사용해야 한다
std::foward_list<int> list1 = {2, 53, 1, 0, 4, 10};
list1.reverse(); // {10, 4, 0, 1, 53, 2}
list1 = {0, 1, 0, 1, -1, 10, 5, 5, 10, 0};
list1.unique(); // {0, 1, 0, 1, -1, 10, 5, 10, 0};
list1 = {0, 1, 0, 1, -1, 10, 5, 5, 10, 0};
list1.sort(); // {-1, 0, 0, 0, 1, 1, 5, 5, 10, 10}
list1.unique(); // {-1, 0, 1, 5, 10}
- 다음 예제 코드는 리스트에서 특정 원소가 바로 앞 원소보다 2 이상 크지 않으면 삭제함
list1.unique([](int a, int b) {return (b - a) < 2;>});
// 실행 결과 : {-1, 1, 5, 10};