[1. 리스트, 스택, 큐] C++ std::forward_list
std::forward_list
배열, 벡터 같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적이다.
std::forward_list는 C++에서 제공하는 기본적인 연결 리스트에 대한 래퍼 클래스이다.
원소의 삽입, 삭제, 순서 뒤집기, 분할 등의 기능은 제공하지만 성능 유지를 위해 전체 리스트의 크기를 반환하거나 첫 번째 원소를 제외한 나머지 원소에 접근하는 기능은 제공하지 않는다.
vector와 마찬가지로 사용자 지정 할당자를 지정하여 메모리 관리를 더욱 효율적으로 수행할 수 있다.
원소 삽입
원소 삽입은 노드 포인터 조작으로 구현되므로 삽입 후 다른 원소를 이동할 필요가 없다.
그렇기 때문에 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작한다.
리스트의 원소 크기에 영향을 받지 않아 O(1)의 시간복잡도를 갖는다.
push_front()
linked list 맨 앞에 새로운 원소를 삽입한다.
forward_list는 마지막 원소에 직접 접근할 수 없으므로 push_back이 아닌 push_front 함수를 제공한다.
#include <iostream>
#include <forward_list>
#include <algorithm>
using namespace std;
int main(){
forward_list<int> fwd_list = {1, 2, 3};
fwd_list.push_front(5);
for(auto elem : fwd_list)
cout << elem << " "; // 출력: 5 1 2 3
return 0;
}
insert_after()
특정 위치에 원소를 삽입할 때 사용하는 함수이다.
연결 리스트에서 원소를 삽입할 때 앞 원소의 next 포인터를 수정해야 하기 때문에 특정 원소 뒤에 새로운 원소를 삽입한다.
#include <iostream>
#include <forward_list>
#include <algorithm>
using namespace std;
int main(){
forward_list<int> fwd_list = {1, 2, 3};
auto it = fwd_list.begin();
it ++;
fwd_list.insert_after(it, 5);
for(auto elem : fwd_list)
cout << elem << " "; // 출력: 1 2 5 3
return 0;
}
emplace_front(), emplace_after()
vector의 emplace()와 유사한 emplace_front(), emplace_after()도 사용할 수 있다.
삽입함수와 같은 기능을 수행하지만 추가적인 복사 또는 이동을 하지 않기 때문에 더 효율적이다.
원소 삭제
pop_front()
리스트의 맨 처음 원소를 제거한다.
O(1)의 시간 복잡도를 갖는다.
erase_after()
vector와 마찬가지로 특정 원소를 가리키는 반복자를 받아 다음 위치의 원소를 삭제하는 형태와 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 통해 일련의 원소를 제거할 수 있다.
삭제할 원소 개수의 선형 함수 형태의 시간 복잡도를 갖는다. (각각의 노드에 사용된 메모리를 개별적으로 해제해야 하기 때문)
pop_front()와 erase_after()를 사용한 예제 코드는 다음과 같다.
#include <iostream>
#include <forward_list>
#include <algorithm>
using namespace std;
int main(){
forward_list<int> fwd_list = {1, 2, 3, 4, 5};
fwd_list.pop_front(); // fwd_list = {2, 3, 4, 5}
auto it = fwd_list.begin();
fwd_list.erase_after(it, fwd_list.end()); // fwd_list = {2}
for(auto elem : fwd_list)
cout << elem << " ";
return 0;
}
추가적인 멤버 함수
remove(), remove_if()
remove 함수는 삭제할 원소 값 하나를 매개변수로 받아 모든 같은 원소를 찾아 삭제한다.
이 때 데이터 타입에 등호 연산자가 존재해야 하고, 존재하지 않는다면 컴파일러 에러가 발생한다.
remove_if 함수는 조금더 유연하게 삭제할 수 있다. 데이터 원소 값 하나를 인자로 받아 bool 값을 반환하는 조건자(predicate)함수를 인자로 받는다. 조건자가 true가 되는 모든 데이터 원소를 삭제한다.
조건자 자리에 람다 표현식을 사용할 수도 있다.
remove와 remove_if 함수는 리스트 전체를 순회하면서 조건에 맞는 원소를 모두 삭제하므로 O(n)의 시간 복잡도를 갖는다.
이를 활용한 코드는 다음과 같이 작성할 수 있다.
#include <iostream>
#include <forward_list>
#include <algorithm>
using namespace std;
bool checkGreater(int val){return val > 4;}
int main(){
forward_list<int> fwd_list = {1, 2, 3, 4, 5};
fwd_list.remove(2); // fwd_list = {1, 3, 4, 5}
fwd_list.remove_if(checkGreater); // fwd_list = {1, 3, 4}
fwd_list.remove_if([](int a){return a <= 3;}); // fwd_list = {4}
for(auto elem : fwd_list)
cout << elem << " ";
return 0;
}
sort()
std::array, std::vector 등에 저장된 데이터는 범용적인 std::sort(first_iterator, last_iterator) 함수를 이용하여 원소를 정렬할 수 있다. 그러나 연결 리스트는 특정 원소에 임의 접근이 불가능하므로 std::sort 를 사용할 수 없다.
forward_list에서 제공하는 sort() 함수는 < 연산자를 기반으로 정렬하거나 비교자를 이용할 수 있다.
sort() 함수는 선형 로그 시간 복잡도 O(nlogn)을 갖는다.
#include <iostream>
#include <forward_list>
using namespace std;
int main(){
forward_list<int> list1 = {23, 0, 1, -3, 34, 32};
list1.sort(); // 오름차순 정렬
for(const auto &c : list1)
cout << c << " "; // 출력: -3 0 1 23 32 34
cout << endl;
list1.sort(greater<int>()); // 내림차순 정렬
for(const auto &c : list1)
cout << c << " "; // 출력: 34 32 23 1 0 -3
cout << endl;
}
reverse()
저장된 원소의 순서를 역순으로 변경한다.
O(n)의 시간 복잡도를 갖는다.
#include <iostream>
#include <forward_list>
using namespace std;
int main(){
forward_list<int> list1 = {23, 0, 1, -3, 34, 32};
list1.reverse();
for(const auto &c : list1)
cout << c << " "; // 출력: 32 34 -3 1 0 23
cout << endl;
}
unique()
리스트에서 홀로 나타나는 원소는 놔두고, 인접하여 중복되는 원소는 첫 번째를 제외하고 제거한다.
이 때 두 원소가 같다는 판단은 등호 연산자와 이항 조건자를 통해 이루어진다.
선형 시간복잡도를 갖는다. 이 말은, 각 원소를 나머지 전체 원소들과 비교하는 것이 아닌, 서로 인접한 원소끼리만 같은지를 판단하게 된다.
따라서 전체적으로 unique한 리스트를 만들기 위해서는 sort를 통해 list를 정렬한 후 unique를 사용해야 한다.
#include <iostream>
#include <forward_list>
using namespace std;
int main(){
forward_list<int> list1 = {0, 1, 0, 1, -1, 10, 5, 5, 10, 0};
auto list2 = list1;
list1.unique();
for(const auto &c : list1)
cout << c << " "; // 출력 : 0 1 0 1 -1 10 5 10 0
cout << endl;
list2.sort();
list2.unique();
for(const auto &c : list2)
cout << c << " "; // 출력 : -1 0 1 5 10
cout << endl;
}