C++ STL - linked list

자료구조를 C로 공부하니까 기본 원리는 알겠는데 C++에서 만들어져 있는 건 어떻게 되어있는지 몰라서 헤맸다. 계속 찾아 보려고 정리. 근데 공식 문서 예제 보는게 빠르고 편함

http://www.cplusplus.com/reference/list/list/insert/

list의 사용

• 헤더파일 사용
• 선언 기본 list<[Data Type] > [변수 이름];

list 의 멤버 함수

list li으로 선언했을 경우

li.front()

맨 앞의 원소를 반환 ,참조

li.back()

맨 뒤의 원소를 반환, 참조

li.back()

맨 뒤의 원소를 반환, 참조

li.begin()

맨 앞의 원소를 가리키는 iterator를 반환

li.end()

맨 마지막의 다음 원소를 가리키는 iterator 반환

li.rbegin()

뒤에서부터 순차적으로 접근할때 사용

뒤집었을때 첫번째

li.rend()

뒤에서부터 순차적으로 접근할때 사용

뒤집었을때 마지막

li.push_back(k)

꼬리로 원소 삽입

li.push_front(k)

머리로 원소 삽입

li.pop_back()

맨 마지막 원소 제거

li.pop_front()

맨 앞 원소 제거

li.insert(iter,k)

iter가 가리키는 위치에 원소 삽입

삽입한 원소를 가리키는 iterator 반환

삽입하면 나머지들은 뒤로 밀림 (왼쪽에 삽입된다는 뜻)

li.erase(iter)

iter가 가리키는 원소를 삭제

삭제한 원소의 다음 원소를 가리키는 iterator 반환

li.size()

원소의 개수 반환

li.remove(k)

k와 같은 원소를 모두 제거

li.remove_if(predicate)

단항 조건자 predicate에 해당하는 원소를 모두 제거

li.reverse()

원소들의 순차열을 뒤집음

li.sort()

모든 원소를 오름차순(default)으로 정렬

파라미터로 정렬 기준 받아서 그 기준으로 정렬

(linked list setSortRule이랑 똑같음)

li2.swap(li1)

li1과 li2를 바꿈

li2.splice(iter2,li1)

li2에서 iter2가 가리키는 곳에 li1의 모든 원소를 잘라 붙임

li2.splice(iter2,li1,iter1)도 가능

li.unique()

인접한 원소가 같으면 유일하게 만듬 (중복 다 삭제)

li2.merge(li1)

li1를 li2 내부로 합병 정렬 기준은 오름차순

두번째 파라미터로 정렬 기준 받을 수 있음

예제

iterator (반복 연산자)

그냥 cur라고 생각하면 됨. 정수 연산 불가하고 ++ , -- 형태만 가능.

포인터임 그냥

• 반복 출력

  //old style
  list<int> iList;
  list<int>::iterator it;
  for (it = iList.begin(); it != iList.end(); ++it)
  cout << *it << endl;
  
  //modern (c++ 11 이상) style 이런 식으로도 가능
  for(auto i:iList)
      cout<< i<<endl;

• 백준 : 에디터 (1406)

  #include<iostream>
  #include<list>
  using namespace std;
  int main() {
  	list<char> clist;
  	list<char>::iterator cursor;
  	string init,cmd;
  	char c;
  	int n;
  
  	cin >> init;
  	cin >> n;
  
  	for (int i = 0; i < init.size(); i++) 
  		clist.push_back(init[i]);
  	 
  	cursor = clist.end();
  
  	for (int i = 0; i < n; i++) {
  		cin >> cmd;   
  		 
  		if (cmd == "L") {
  			if(cursor != clist.begin())
  				cursor--; 
  		}
  		if (cmd == "D") {
  			if (cursor != clist.end())
  				cursor++;
  		}
  		if (cmd == "B") {
  			if (cursor != clist.begin()) {
  				cursor--;
  				cursor = clist.erase(cursor); 
  			} 
  
  		}
  		if (cmd == "P") {
  			cin >> c; 
  			clist.insert(cursor,c);
  		}
  	}
  
  	for (char c : clist)
  		cout << c;
  
  	return 0;
  }

• 백준 : 카드 2(2164)

  #include <iostream>
  #include <list>
  using namespace std;
  int main() {
  	int n;
  	list<int> nlist;
  	cin >> n;
  
  	for (int i = 0; i < n; i++)
  		nlist.push_back(i + 1);
  
  	while (nlist.size() != 1) {
  		nlist.pop_front();
  		nlist.push_back(nlist.front());
  		nlist.pop_front();
  	}
  
  	cout<< nlist.back();
  	return 0;
  }

추가할 거 있으면 나중에 더 추가