7/18 STL

● <list>

c++에서 제공하는 양방향 연결 리스트를 구현한 컨테이너 클래스이다. 다른 STL 컨테이너와 다르게 Linked List기반의 구조를 가지고 있다. <list>를 사용하면 원소의 삽입, 삭제, 이동 등이 O(1)에 이루어질 수 있으므로 대량의 원소를 삽입, 삭제하는 상황에서 효율적이지만 원소에 접근할 경우 O(n)의 시간이 소요된다..

<list>의 주요 멤버함수

#include <list>

std::list<type> myList;

push_back(value); 	// 리스트의 끝에 원소를 추가
push_front(value);  // 리스트의 앞에 원소를 추가
pop_back();			// 리스트의 끝에 있는 원소를 삭제
pop_front();		// 리스트의 앞에 잇는 원소를 삭제
front();			// 리스트의 첫번째 원소에 접근
back();				// 리스트의 마지막 원소에 접근
begin();			// 리스트의 처음을 가리키는 반복자 반환
end();				// 리스트의 끝을 나타내는 반복자 반환
insert(pos, value); // pos위치에 원소를 삽입
erase(pos);			// pos위치의 원소를 삭제
clear();			// 리스트의 모든 원소 삭제
size();				// 리스트 원소 개수 반환

#include <iostream>
#include <list>

using namespace std;

int main(void)
{
    list<int> myList;
    
    myList.push_back(10);
    myList.push_back(20);
    myList.push_front(5); // {5, 10}

    myList.pop_back();

    cout << "첫번째 원소 : " << myList.front() << endl;
    cout << "마지막 원소 : " << myList.back() << endl;

    for (const auto& element : myList)
    {
        cout << element << ' ';
    }
    cout << endl;

    list<int>::iterator cur = myList.begin();
    myList.insert(++cur, 9999);

    printf("리스트의 원소 : ");
    for (const auto& element : myList)
    {
        cout << element << ' ';
    }
    cout << endl;

    return 0;
}

출력결과

첫번째 원소 : 5
마지막 원소 : 10
5 10
리스트의 원소 : 5 9999 10

2차원 원소(노드, 거리정보)를 연결리스트로 만드는 법

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main(void)
{
	vector<list<pair<int, int>>> graph(3);

	graph[0].push_back(make_pair(1, 7));
	graph[0].push_back(make_pair(2, 5));

	graph[1].push_back(make_pair(0, 7));
	
	graph[2].push_back(make_pair(0, 5));

	for (int i = 0; i < graph.size(); i++) {
		cout << "Node " << i << ": ";
		for (const auto& edge : graph[i]) {
			cout << "(" << edge.first << ", " << edge.second << ") ";
		}
		cout << '\n';
	}
	return 0;
}

출력결과

Node 0: (1, 7) (2, 5)
Node 1: (0, 7)
Node 2: (0, 5)