std::forward_list
- 연결 리스트에 대한 래퍼 클래스
std::forward_list에서 원소 삽입
- push_front(): 연결 리스트 맨 앞에 새로운 원소 추가
- 마지막 원소에 직접 접근할 수 없으므로 push_back() 제공 x
- insert_after(): 특정 위치에 원소 추가
- 반대 방향으로 이동이 허용되지 않으므로 특정 원소 뒤에 새로운 원소를 삽입한 후, 해당 원소의 next 포인터를 수정
- 연결 리스트에서 원소 삽입은 노드의 포인터 조작으로 구현되므로, 삽입 후 다른 원소를 이동할 필요가 없다.
- 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작. 리스트의 원소 크기에 영향을 받지 않으며 시간 복잡도는 O(1)
- 원소 삽입 예제 코드
std::forward_list<int> fwd_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}
fwd_list.insert_after(it, 6); // 맨 처음 원소 뒤에 6 추가: {0, 6, 5, 1, 2, 3}- 이외에 vector의 emplace() 함수와 유사한 emplace_front()와 emplace_after() 함수도 제공
- 삽입 함수와 같은 기능을 수행하지만 추가적인 복사 또는 이동을 하지 않으므로 더 효율적
std::forward_list에서 원소 삭제
- void pop_front(): 맨 처음 원소 삭제
- iterator erase_after( const_iterator pos ): pos 다음 원소 삭제
- iterator erase_after( const_iterator first, const_iterator last ): first 다음부터 last까지 삭제
- 원소 삭제 예제 코드
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(const T& value)
- 삭제할 원소 값 하나를 매개변수로 받아서, 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전달된 값과 일치하는 모든 원소를 찾아 삭제
- 오직 등호 연산에 근거하여 원소를 삭제하며 다른 조건에 근거하여 삭제 여부를 결정할 수 없음
- 저장된 데이터 타입에서 등호 연산이 지원되지 않으면 컴파일 에러
- remove_if(UnaryPredicate p)
- 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제
- 조건자 자리에 람다 표현식(lambda expression) 사용 가능
- remove(const T& value)
연습 문제 3: 연결 리스트에서 remove_if() 함수를 이용한 조건부 원소 삭제
- 선거 기간에 선거권이 없는 사람 가려내기
#include <string>
#include <iostream>
#include <forward_list>
// citizen 구조체 정의
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) {
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) {
return (c.age != 18);
});
std::cout << "내년에 투표권이 생기는 시민들: ";
for (const auto &c : citizens_copy)
std::cout << c << " ";
std::cout << std::endl;
}-
실행 후 출력 내용
-
참고: 깊은 복사가 가능한 이유
- forward_list의 멤버 함수 operator= 사용 시 파라미터로 주어진 other의 모든 컨텐츠의 복사본을 만들기 때문
- forward_list의 멤버 함수 operator= 사용 시 파라미터로 주어진 other의 모든 컨텐츠의 복사본을 만들기 때문
-
remove()와 remove_if() 함수는 리스트 전체를 순회하며 조건에 맞는 원소를 모두 삭제하므로 O(n)의 시간 복잡도를 갖는다.
-
void sort(): < 연산자 기반 정렬
-
void sort( Compare comp ): 이항 조건자(binary predicate) 기반 정렬
-
정렬 예제 코드
std::forward_list<int> list1 = {23, 0, 1, -3, 34, 32};
list1.sort(); // {-3, 0, 1, 23, 32, 34}
list1.sort(std::greater<int>()); // {34, 32, 23, 1, 0, -3}- reverse(): 저장된 원소의 순서를 역순으로 변경
- 걸리는 시간은 리스트 원소 개수에 비례, 시간 복잡도 O(n)
- unique(): 중복 제거
- 참고: https://www.geeksforgeeks.org/forward_listunique-in-c-stl/
- Time Complexity: O(N), where N is the number of elements compared
- Auxiliary Space: O(1) -- 보조 공간 : input size를 고려하여 알고리즘이 문제를 해결하기 위해 임시로 사용하는 공간
- 각각의 원소를 나머지 원소 전체와 비교하는 형태로 동작하는 것이 아님
- 서로 인접한 원소끼리 같은지를 판단하고, 만약 서로 같으면 앞에 있는 원소는 남기고 뒤의 원소는 제거
- 따라서 리스트 전체에서 유일한 원소들만 남게 만들려면 먼저 리스트를 정렬한 후 unique() 함수를 사용해야 함
- reverse(), sort(), unique() 함수를 사용하는 예제 코드
std::forward_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}
list1.unique([](int a, int b) { return (b - a) < 2; }); // 실행 결과: {-1, 1, 5, 10}- 참고: forward_list는 singly linked list를 구현한 것
https://www.geeksforgeeks.org/difference-between-singly-linked-list-and-doubly-linked-list/
백준 1406
- forward_list가 특정 케이스에는 메모리를 절약하는 효과가 있다고 하는데, list에서 제공하는 기능이 없는 경우가 있어서 알고리즘 풀이 시에는 대개 list를 쓰는 것 같다.
#include <iostream>
#include <string>
#include <list>
using namespace std;
int main() {
int M;
string input;
list<char> editor;
cin >> input;
editor = list<char>(input.begin(), input.end());
// 커서의 위치를 문자열의 끝으로 설정
auto cursor = editor.end();
// 명령어의 개수 입력 받기
cin >> M;
for (int i = 0; i < M; i++) {
char cmd;
cin >> cmd;
switch (cmd) {
case 'L': // 커서를 왼쪽으로 이동
if (cursor != editor.begin()) cursor--;
break;
case 'D': // 커서를 오른쪽으로 이동
if (cursor != editor.end()) cursor++;
break;
case 'B': // 커서 왼쪽 문자 삭제
if (cursor != editor.begin()) {
cursor--;
cursor = editor.erase(cursor);
}
break;
case 'P': // 문자 삽입
char c;
cin >> c;
editor.insert(cursor, c);
break;
}
}
// 수정된 내용 출력
for (char ch : editor) {
cout << ch;
}
return 0;
}