C++ Standard Library 의 list
std::list
list란?
std::forward_list는 아주 기본적인 형태로 구현된 연결리스트이다.
std::forward_list는 다른 유용한 기능 중에서도
리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능은 제공하지 않는다.
이는 메모리를 적게 쓰고 성능을 유지하기 위함이다.
이외에도 std::forward_list의 반복자는 매우 적은 기능만 지원한다.
컨테이너의 크기를 얻어오거나
자료 구조 맨 뒤에 새로운 데이터를 추가하는 등의 기능은 매우 유용하고 빈번하게 사용되지만,
std::forward_list에서는 지원되지 않는다.
그러므로 std::forward_list의 단점을 보완하기 위해 std::list를 C++에서 제공한다.
이중 연결 리스트에서 사용하는 노드의 기본 형태는 다음과 같다.
struct doubly_linked_list_node
{
int data;
doubly_linked_list_node* next;
doubly_linked_list_node* prev;
};
코드에서 볼 수 있듯이 이중 연결 리스트 노드는 이전 노드를 가리키는 포인터가 추가로 있다.
이 포인터를 이용하여 역방향으로 이동할 수 있으며,
맨 마지막 원소와 리스트 크기를 따로 저장하여 빠른 push_back() 또는 size() 함수를 지원할 수 있다.
또한 std::forward_list와 마찬가지로 템플릿 매개변수로 사용자 정의 할당자를 지정할 수 있다.
std::list 멤버 함수
std::list에서 제공되는 대부분의 함수는 약간의 차이가 있긴 하나,
std::forward_list와 대부분 유사하거나 같다.
이는 마이크로 소프트에서 제공하는 list클래스의 설명에 상세하게 나와있는데,
https://learn.microsoft.com/ko-kr/cpp/standard-library/list-class?view=msvc-170
list 클래스
자세한 정보: list 클래스
learn.microsoft.com
해당 사이트를 참고하여 응용할 수 있다.
std::list 함수 응용하기
1. 필요한 헤더 파일을 포함한다.
2. 초깃값을 갖는 리스트를 생성하고, 새로운 원소를 몇 개 추가한다.
3. 함수를 응용한다.
// list_class_insert.cpp
// compile with: /EHsc
// Microsoft Learn list 클래스 예제 발췌
#include <list>
#include <iostream>
#include <string>
int main()
{
using namespace std;
list <int> c1, c2;
list <int>::iterator Iter;
c1.push_back(10);
c1.push_back(20);
c1.push_back(30);
c2.push_back(40);
c2.push_back(50);
c2.push_back(60);
cout << "c1 =";
for (auto c : c1)
cout << " " << c;
cout << endl;
Iter = c1.begin();
Iter++;
c1.insert(Iter, 100);
cout << "c1 =";
for (auto c : c1)
cout << " " << c;
cout << endl;
Iter = c1.begin();
Iter++;
Iter++;
c1.insert(Iter, 2, 200);
cout << "c1 =";
for(auto c : c1)
cout << " " << c;
cout << endl;
c1.insert(++c1.begin(), c2.begin(), --c2.end());
cout << "c1 =";
for (auto c : c1)
cout << " " << c;
cout << endl;
// initialize a list of strings by moving
list < string > c3;
string str("a");
c3.insert(c3.begin(), move(str));
cout << "Moved first element: " << c3.front() << endl;
// Assign with an initializer_list
list <int> c4{ {1, 2, 3, 4} };
c4.insert(c4.begin(), { 5, 6, 7, 8 });
cout << "c4 =";
for (auto c : c4)
cout << " " << c;
cout << endl;
}
해당 예제를 디버깅하면 이러한 결과값이 나온다.
std::list와 std::forward_list의 차이
1. 연산량의 차이
2. 반복자
3. 사용 예
1. 연산량의 차이
std::forward_list와 std::list의
push_front(), insert(), pop_front(), erase() 의 함수 시간 복잡도는 서로 같지만,
실제로는 std::list에서 좀 더 많은 연산이 필요하다.
왜냐하면 std::list는 각각의 노드의 두 개의 포인터를 가지고 있고,
삽입 또는 삭제 연산 시 두 개의 포인터를 관리해야 하기 때문이다.
그로므로 이중 연결 리스트에서 포인터를 관리하기 위해서는
단일 연결 리스트보다 대략 두 배의 연산을 수행해야 한다.
<이중 연결 리스트에서 원소 삽입 시>
2. 반복자
list는 양방향 반복자이다.
list의 반복자는 역방향으로 이동할 수 있으므로, forward_list보다 제약이 적다.
list의 반복자를 이용하여 특정 위치로 이동하는 작업은 선형 시간 복잡도를 가진다.
++Plus ++
선형 시간 복잡도란?
만약 시간복잡도가 O(n)이면,
이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다.
리스트의 모든 요소를 더하는 프로시저는 리스트의 길이에 비례하는 시간을 요구한다.
이러한 설명은 수행시간이 특히 작은 n의 값에 대해,
정확한 선형적인 비례형태로부터 상당히 편차를 가질 수 있기 때문에 다소 부정확하다.
종종 선형 시간은 알고리즘의 이상적인 특성으로 여겨진다.
많은 연구자들이 선형 시간이나 그보다 더 좋은 알고리즘을 만드는 것을 연구해왔다.
이러한 연구는 소프트웨어와 하드웨어어적인 방법 모두를 포함한다.
수학적으로, 표준 계산 모델을 사용해 선형 시간을 절대 얻을 수 없는 알고리즘들은
하드웨어적인 관점에서 선형 시간 동안 실행될 수 있다.
이것을 제공하는 병렬식 방법을 이용하는 하드웨어 기술이 존재하며,
예로는 content-addressable 메모리와 같은 것이 있다.
이러한 선형시간 개념은 BoyerMoore 알고리즘과 Ukkonen 알고리즘과 같은
문자열 매칭 알고리즘에서 사용된다.
++
3. 사용 예
std::list는 size(), push_back(), pop_back() 등의 더 많은 함수를 제공하며,
이들 연산은 O(1) 시간 복잡도로 동작한다.
그러므로 std::list가 std::forward_list보다 더 자주 사용된다.
std::forward_list는 데이터를 역방향으로 이동하며 접근하지 않아도 되는 경우에
메모리 또는 성능을 최적화하고 싶을 때에만 제한적으로 사용된다.
즉, 대부분의 경우에는 std::list를 사용하는 것이 더 나은 선택이다.
std::list의 특징
반복자 무효화
어떤 컨테이너든 원소 접근, 순회, 삽입, 삭제 등의 작업을 반복자를 사용하여
모두 같은 방식으로 처리한다는 점을 확인했다.
반복자는 메모리 주소를 가리키는 포인터를 이용하여 구현되었기 때문에
경우에 따라 컨테이너가 변경될 경우 제대로 동작하지 않을 수 있다.
그러므로 컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌면
사용하던 반복자가 무효화 될 수 있고, 이 경우 예측할 수 없는 동작이 발생할 수 있다.
vector의 경우,
메모리 재할당 없이 원소를 삽입하는 경우라면,
원소 삽입 위치 이후에 있는 원소를 모두 이동해야 하므로
이 위치를 가리키는 반복자는 모두 무효화된다.
vector와 달리 연결 리스트에서 삽입 또는 삭제 동작에서
원소를 이동할 필요가 없으므로 반복자가 무효화되지 않는다.
즉, std::list 또는 std::forward_list 에서 삽입 동작은 반복자의 유효성에 영향을 미치지 않는다.
다만 특정 우너소를 삭제하는 경우,
삭제되는 원소를 가리키던 반복자는 당연히 무효화되지만
나머지 원소를 가리키는 반복자는 그대로 사용할 수 있다.
예제 코드 - vector
std::vector<int> vec = {1, 2, 3, 4, 5};
auto v_it4 = vec.begin() + 4; // v_it4 는 vec[4] 원소를 가르킨다.
vec.insert(vec.begine() + 2, 0) // v_it4 반복자는 무효화된다.
/*
해당 코드에서 마지막 문장이 수행되면 v_it4 반복자는 무효화되며,
v_it4를 이용하여 원소에 접근하려고 하면
예상치못한 애러가 발생할 수 있다.
*/
예제 코드 - list
std::list<int> lst = {1, 2, 3, 4, 5};
auto l_it4 = next(lis.begin(), 4);
list.insert(next(lst.begin(), 2), 0); // l_it4는 여전히 유효하다.
카드 게임을 시뮬레이션하려고 한다.
한 게임에 네 명의 플레이어가 있고, 각각의 임의의 카드 13장을 가지고 게임을 시작한다.
그리고 각 플레이어의 카드에서 임의의 카드 한 장을 선택한다.
그렇게 하면 비교할 카드가 네 장이 생기게 되고, 이 중 서로 중복되는 카드 쌍은 모두 제거한다.
세 장의 카드가 같을 경우에는 이 중 임의로 두 장만 제거한다.
네 장의 카드가 모두 같으면 네 장을 모두 제거한다.
남겨진 카드는 카드를 낸 플레이어가 다시 가져간다.
일치하는 카드 쌍이 없으면 플레이어의 카드 세트를 섞을 수 있다.
이제 이 과정을 어느 한 사람의 카드가 다 없어질 때까지 반복한다.
제일 먼저 자신의 카드를 모두 없앤 사람이 게임의 승자이다.
최종적으로 승자를 화면에 출력하고 게임이 끝난다. 이 문제를 해결하기 위해 다음 단계를 수행한다.
1. 먼저 각 플레이어가 가지고 있는 카드를 저장하기에 적합한 컨테이너를 결정해야 한다.
네 명의 플레이어가 각기 여러 장의 카드를 있으므로 네 개의 컨테이너 객체를 생성해야 한다.
2. 카드를 초기화하고 섞는 함수를 작성한다.
3. 네 명의 플레이어에서 각각 무작위로 카드를 선택하는 함수를 작성한다.
4. 서로 일치하는 카드가 있는지 검사하는 매칭 함수를 작성한다.
이 함수는 각 플레이어로부터 카드를 한 장씩 선택하고, 선택된 네 장의 카드를 서로 비교한다.
그리고 일치하는 카드를 제거한다.
카드를 제거하는 작업이 빠르게 동작할 수 있도록 카드를 선택해야 한다.
처음에 카드를 저장할 컨테이너를 선정할 때 이러한 점도 고려해야한다.
5. 승자가 있는지를 검사하는 함수를 작성한다.
6. 이제 게임의 핵심 로직을 구현한다.
이 단계에서는 이전에 작성한 함수들을 이용하여 승자가 나타날 때까지 매칭 작업을 반복적으로 수행한다.
#include <iostream>
#include <vector>
#include <array>
#include <sstream>
#include <algorithm>
#include <random>
#include <chrono>
struct card
{
int number;
enum suit
{
HEART,
SPADE,
CLUB,
DIAMOND
} suit;
std::string to_string() const
{
std::ostringstream os;
if (number > 0 && number <= 10)
os << number;
else
{
switch (number)
{
case1 :
os << "Ace";
break;
case11:
os << "Jack";
break;
case12:
os << "Queen";
break;
case13:
os << "King";
break;
default:
return "Invalid card";
}
}
os << " of ";
switch (suit)
{
case card::HEART:
os << "hearts";
break;
case card::SPADE:
os << "spades";
break;
case card::CLUB:
os << "clubs";
break;
case card::DIAMOND:
os << "diamonds";
break;
}
return os.str(); // 해당 분류 뱉기
}
};
struct game
{
std::array<card, 52> deck;
std::vector<card> player1, player2, player3, player4;
void buildDeck()
{
for (int i = 0; i < 13; i++)
deck[i] = card{ i + 1,card::HEART };
for (int i = 0; i < 13; i++)
deck[i + 13] = card{ i + 1,card::SPADE };
for (int i = 0; i < 13; i++)
deck[i + 26] = card{ i + 1,card::CLUB };
for (int i = 0; i < 13; i++)
deck[i + 39] = card{ i + 1,card::DIAMOND };
}
void dealCards()
{
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(deck.begin(), deck.end(), std::default_random_engine(seed));
player1 = { deck.begin(), deck.begin() + 13 };
player2 = { deck.begin() + 13, deck.begin() + 26 };
player3 = { deck.begin() + 26, deck.begin() + 39 };
player4 = { deck.begin() + 39, deck.end() };
}
bool compareAndRemove(std::vector<card>& p1, std::vector<card>& p2)
{
if (p1.back().number == p2.back().number)
{
p1.pop_back();
p2.pop_back();
return true;
}
return false;
}
void playOneRound() // 비교해서 같으면 지워주기
{
if (compareAndRemove(player1, player2))
{
compareAndRemove(player3, player4);
return;
}
else if (compareAndRemove(player1, player3))
{
compareAndRemove(player2, player4);
return;
}
else if (compareAndRemove(player1, player4))
{
compareAndRemove(player2, player3);
return;
}
else if (compareAndRemove(player2, player3))
{
return;
}
else if (compareAndRemove(player2, player4))
{
return;
}
else if (compareAndRemove(player3, player4))
{
return;
}
}
bool isGameComplete() const
{
return player1.empty() || player2.empty() || player3.empty() || player4.empty();
}
void playGame()
{
while (not isGameComplete())
{
playOneRound();
}
}
int getWinner() const // 승자 판별
{
if (player1.empty())
return 1;
if (player2.empty())
return 2;
if (player3.empty())
return 3;
if (player4.empty())
return 4;
}
};
int main()
{
game newGame;
newGame.buildDeck();
newGame.dealCards();
newGame.playGame();
auto winner = newGame.getWinner();
std::cout << winner << "번 플레이가 승리하였습니다!" << std::endl;
}
해당 게시글은 코딩 테스트를 위한 자료 구조와 알고리즘 with c++를 주교재로,
Microsoft Learn 에서 예제 발췌 및 참고,
이외 각종 사이트를 참조하여 작성되었습니다.
'컴퓨터 프로그래밍 공부 > 자료구조와 알고리즘' 카테고리의 다른 글
| 그리디 알고리즘 - 최단 작업 우선 스케줄링 (0) | 2023.12.01 |
|---|---|
| std::deque (0) | 2023.10.27 |
| 우선순위 큐와 힙 (Priority Queue & Heap) (0) | 2023.06.07 |
| 시간 복잡도 & 자료구조와 알고리즘이란? (0) | 2023.02.20 |
| #include <sstream> (0) | 2023.02.14 |