Cpp로 다시 하는 코테준비[~0x04]
0x04
연결리스트를 공부했다. 오랜만에 하려니 어렵다.
1
2
3
4
struct NODE{
struct Node *prev, *nxt;
int data;
};
이게 연결리스트(DLL) 기본인데, list헤더에 있는 걸 쓰면 훨씬 쉬워진다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <list>
int main(){
ios::sync_with_stdio(0), cin.tie(0);
list<int> L = {1,2}; // 1 2 초기화 시키기
list<int>::iterator t = L.begin(); // t는 1을 가리키는 중
L.push_front(10); // 10 1 2 -> t에는 영향을 끼치지않는다
cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
L.push_back(5);
L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 1 2 5
t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
t = L.erase(t);
// t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
// 위치를 반환하기 때문에 t에 저장해도 된다!
// 10 6 1 5, t가 가리키는 값은 5
cout << *t << '\n'; // 5
for(auto i : L) cout << i << ' '; // 순회 꿀팁 ^cpp11+
cout << '\n';
// cpp 11 미만이면 이터레이터 걸어서 돌려줘야됨
for(list<int>::iterator it = L.begin(); it != L.end(); it++)
cout << *it << ' ';
return 0;
}
중요한 건 insert와 erase의 사용법이다. 각각 가리키는 곳 앞에 삽입하고, 가리키는 값을 제거하고난 다음 원소의 위치를 반환한다.
그렇게 에디터[BOJ1406]문제를 풀었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
void out(list<char> ll){
for(auto c: ll){
cout << c;
}
cout << "\n";
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
string input;
cin >> input;
list<char> ll;
list<char>::iterator t = ll.begin();
for(auto c: input){
ll.insert(t, c);
}
int tc = 0;
cin >> tc;
for(int i=0; i<tc; i++){
char cmd;
char in;
cin >> cmd;
if(cmd == 'P'){
cin >> in;
ll.insert(t, in);
}
if(cmd == 'L'){
if(t != ll.begin()) t--;
}
if(cmd == 'D'){
if(t != ll.end()) t++;
}
if(cmd == 'B'){
if(t != ll.begin()){ // 맨 앞이 아닐 때만
t--; // 하나 뒤로 돌린다음 삭제해야됨
t = ll.erase(t);
// t가 가리키는 위치를 지우고 그 다음위치를 반환함
}
}
}
out(ll);
return 0;
}
bound 체크를 begin, end 메서드로 처리하면, 해당 위치가 커서와 같은 지 편하게 알 수 있다.
풀고 나서 커서를 list<*>::iterator로 접근하는 게 어렵다는 생각을 하며 다른 사람 코드를 열었는데! 아래와 같이 쓰고 있었다.
1
2
3
4
for (int i = 0; i < input.size(); i++) {
ll.push_back(input[i]);
}
auto cur = ll.end();
여기서 시작된 의문. auto는 신인가?
auto
변수 선언에서 auto를 쓰면 우변 값 타입에 따라 컴파일러가 타입을 자동으로 결정한다.
1
2
3
4
5
6
7
8
// case 1
int x = 10;
auto y = x; // y는 int로 추론됨
auto d = std::vector<int>{1, 2, 3}; // std::vector<int>
// case 2
auto a; // 불가능. 초기화식이 없어서 타입을 알 수 없음
auto b = 3.14; // 가능. b는 double로 추론됨
타입 추론용 타입이기 때문에, 초기화 식과 동반돼야한다.
그래서 아래와 같은 치트가 가능한 것이다.
1
2
list<char>::iterator cur = ll.begin();
auto cur = ll.end();
중요한 건 참조를 같이 쓸 때다. auto는 초기화식이 참조거나 포인터면 실제 값을 복사(deep copy)한다. 원본을 유지하려면 auto&, const auto&, auto*를 명시해야 한다.
1
2
3
4
5
6
int x = 42;
int& ref = x;
auto a = ref; // a는 int
auto& b = ref; // b는 int&
const auto& c = x; // c는 const int&
알아보니 얼마나 특이한 지, return 값이나 템플릿에도 만능인 걸 알 수 있었다.
1
2
3
4
5
6
auto func() {
return 123; // int로 추론함
}
auto lambda = [](int a, int b){ return a+b; };
auto result = lambda(3,4); // result는 int
타입을 추론하는 데, 여러 변수에 대한 추론을 선언하면 어떻게 될까?
1
2
auto a = 1, b = 2.0; // 타입이 다름
auto a = 1, b = 2; // 같아도 추론 실패
컴파일 에러가 발생한다.
각 변수의 타입을 개별적으로 추론하는 게 아니며, 맨 앞 변수의 타입으로 모두 추론하려고 시도하는 것도 아니다.
추가로 순회할 때도 쓴다.
1
for(const auto& x : v) { ... }
컬렉션 자료형을 순회할 때 auto&으로 참조해서 돌리면 더 빨라지는 걸 알 수 있었다.
정말 auto 많이 쓸 것 같다!