STL list - 상세이론

1.리스트를 사용하기 위한 헤더

#include < list >

---

2.리스트 선언 및 초기화

2-1.리스트를 선언하고 초기화하는 법

list<자료형> [변수이름];

list<int> list1;
list<char> list2 = {'a','b'};
list<string> list3;

---

2-2.생성자를 이용한 디폴트 선언 초기화

list<자료형> 변수이름;

list<char> list1(5); // 디폴트 값 : ' ' => { , , , , }
list<int> list2(7); // 디폴트 값 : 0 => {0, 0, 0, 0, 0, 0, 0}
list<double> list3(3);

예제

#include <iostream>
#include <list>
using namespace std;

int main()
{
  int n = 4;
  list<double> list_double(n);
  list<char> list_char(3);
  
  for(double val : list_double)
    cout << val << ","
}

---

2-3.생성자를 이용해 특정 공간의 개수, 특정 값 지정해 초기화하기

list<자료형> 변수이름(a,b)
a : 데이터 개수 , b : 데이터 값 ( 데이터 b를 a개만큼 초기화 )

#include <iostream>
#include <list>
using namespace std;

int main()
{
  list<int> list_int(4,3); // 3 3 3 3 
  
  for(int val : list_int)
    cout << val << ",";
  
  cout << endl;
  return 0;
}

---

2-4.생성자를 이용해 특정 공간의 개수, 특정 값 지정해 초기화하기

list<타입> [변수이름]{ ..채울 값.. };

#include < iostream >
#include < list >
using namespace std;

int main()
{
  list<int> list_int{2,3,4,5};
  
  for(int val : list_int) 
    cout << val << " ";
  
  return 0;
}

---

2-5.멤버함수 assign()을 이용해서 특정 공간의 개수에 특정 값 할당하기

리스트변수 . assign(a,b)
a : 데이터 개수, b : 데이터 값 ( 데이터 b를 a개 만큼 초기화 )

#include <iostream>
#include <list>
using namespace std;

int main()
{
  list<int> list1;
  list1.assign(4,3); // 3 3 3 3 
  
  for(int val : list1)
    cout << val << " ";
  
  cout << endl;
  return 0;
}

---

3.리스트 복사하기

3-1.기본 복사생성자 사용

list<타입> list1(list2)
list2 에다 list1 을 복사

list<int> origin_list{2,3,4,5};
list<int> new_list(origin_list); // 2 3 4 5 그대로 복사

---

3-2.대입 연산자 "=" 를 사용해서 복사하기

list<타입> list1 = list2;

list<int> origin_list{2,3,4,5};
list<int> new_list = origin_list; 

3-3.iterator 반복자 사용해서 복사하기

• STL은 iterator 를 공통적으로 지원해주는데, 이를 사용해서 복사할 수 있다.
• begin() 함수는 맨 앞의 원소를 가리키는 iterator를 리턴하고,
• end() 함수는 마지막 원소 다음을 가리키는 iterator 를 리턴한다.

list<int> origin_list{2,3,4,5};
list<int> new_list( origin_list.begin(), orgin_list.end() ); // iterator를 이용해서 복사

• vector의 경우 아래처럼 iterator 를 이용해서 복사할 경우 어디부터 어디까지를 복사해 넣을건지 지정할 수 있다.

// 가능
vector<int> vector1{1,2,3,4,5,6,7,8,9,10};
vector<int> vector2( vector1.begin() + 1, vector1.begin() + 4);

// 컴파일 에러
list<int> list1{1,2,3,4,5,6,7,8,9,10};
list<int> list2( list1.begin() + 1, list1.begin() + 4); // list는 이렇게 구간을 잘라서 중간 요소들을 복사하는 것이 불가능하다.

이렇게 하면 vector1의 2~4번째 원소가 vector2에 복사된다.

• 하지만, list의 경우 처음과 끝이 아닌 중간 요소에 직접 접근이 불가능해서, 중간 구간을 잘라서 복사할 수 없다.

---

4.연산자

• list[i] 같은 인덱스 조회는 list에서 사용 불가능하다.

list == list2
list1 != list2
list1 = list2
list1 > list2
list1 >= list2
list1 < list2
list1 <= list2

list<int> list{2,3,4};
list<int> list{4,1};

cout << (list1 < list2) >> endl; // true

---

5.주요 함수

• 삽입, 삭제 연산이 O(1) 로 가능
  => push_back, pop_back, push_front, pop_front() : O(1)
• iterator 가 주소역할을 한다.

메소드

1.iterator(반복자)

• begin() : beginning iterator 를 리턴 (맨 앞 원소를 가리키는 iterator 리턴)
• end() : end iterator 를 리턴 (맨 마지막의 다음 원소를 가리키는 iterator를 리턴)

2.추가 및 삭제

• push_back(a) : 맨 뒤에 원소 추가
• push_front(a) : 맨 앞에 원소 추가
• pop_back() : 맨 뒤 원소 삭제
• pop_front() : 맨 앞 원소 삭제
• insert(iterator, a) : iterator 가 가리키는 부분 "앞"에 원소 a를 추가
• erase(iterator) : iterator가 가리키는 부분에 원소를 삭제. 삭제된 원소 iterator 의 다음 원소 iterator를 리턴해줌.
• remove(a) : a와 같은 원소를 모두 제거

3.조회

• *iterator : iterator 가 가리키는 원소에 접근
• front() : 첫번째 원소를 리턴
• back() : 마지막 원소를 리턴

4.기타

• empty() : 링크드 리스트가 비어있으면 true, 아니면 false 를 리턴
• size() : 링크드 리스트의 원소들의 수를 리턴
• assgin(3,4) : 4로 초기화된 3개의 원소를 할당
• sort() : 오름차순 정렬
• list2.swap(list1) : list2 와 list1 을 swap
• reverse() : 원소들의 순차열을 뒤집음

예제1

int main(void)
{
  list<int> L = {1,2};
  list<int>::iterator t = L.begin(); // t는 1를 가리키는 중
  // => auto t = L.begin(); 으로 써도 됌
  
  L.push_front(10) // 10 1 2
  cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
  
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // 10 6 1 2 5 => t가 가리키는 곳 앞에 6을 삽입
  
  t++;  t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 리턴
  
  cout << *t << '\n'; // 5
  for(auto i : L) // 10 6 1 5
    cout << i << ' ';
  
  cout << '\n';
  
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

예제2

int main(void)
{
  list<int> l;
  
  l.push_back(5);
  l.push_back(6);
  l.push_back(7);
  l.push_back(8);
  l.push_back(9);
  l.push_back(10);
  
  l.pop_back();
  
  l.push_front(4);
  l.push_front(3);
  l.push_Front(1);
  l_push_front(0);
  
  l.pop_front();
  
  cout << "list front value:" << l.front() << '\n';
  cout << "list end value:" << l.end() << '\n';
  
  cout << "list size:" << l.size() << '\n';
  
  cout << "Is it empty?:" << ( l.empty() ? "YES" : "NO") << '\n';
  
  list<int>::iterator begin_iter = l.begin();
  // auto begin_iter = l.begin() 도 가능(동일한 표현)
  
  list<int>::iterator end_iter = l.end();
  // auto end_ter = l.end() 도 가능(동일한 표현)
  
  begin iter++; // 2번쨰를 가리키는 iterator
  l.insert(begin_iter, 2);
  
  end_iter--; // 마지막 원소를 가리키는 iterator
  l.erase(end_iter);
  
  // iterator: 원소 접근
  cout << "list" << distance(l.begin(), begin_iter) + 1 << "element:" 
  << being_iter << '\n';
}

예제3

• 실험을 해보니, 맨 처음에 push_back 을 하면 iterator 가 계속 쫓아가는데, 중간에 iterator 가 위치해있으면 push__back 을 해도 쫓아가지 않는다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n; 
    cin >> n;
    
    list<int> L;
    auto cursor = L.begin();

    for(int i=1; i<=n; i++){
      L.push_back(i); //1 2 3 4 5 6 7 출력
      cout << "1cursor:" << *cursor << endl;
    }

    cursor--; // iterator : end -> 7
    cursor--; // iterator : 7 -> 6
    for(int i = n+1; i <= n+3; i++){
      L.push_back(i); // 6 6 6 출력
      cout << "2cursor:" << *cursor << endl;
    }
}