July 24, 2023 00:00

서론

러스트가 신흥 프로그래밍 언어(?)로 뜨고 있습니다. 안전하면서도 빠른 실행, 자체적으로 지원하는 rustfmt와 Clippy 등의 유용한 개발 도구, Cargo를 통한 손쉬운 라이브러리 관리 등의 장점으로 큰 인기를 끌고 있고, 구글, 페이스북 등 여러 대기업이 제품에 러스트를 사용하기 시작했습니다.

대학원 연구를 위해 러스트를 배운 적이 있는데, “러스트가 미래다”라는 막연한 생각에 올해 약 반 년 동안 러스트로 백준 온라인 저지에서 문제 풀이를 진행해 보았습니다. 그 과정에서 구현한 자료구조 및 알고리즘과 전체적인 소감을 정리합니다.

스포일러: 러스트는 좋은 언어입니다.

이 글은 러스트를 소개하는 글이 아닙니다. 러스트를 소개하려면 내용을 훨씬 많이 작성해야 되기 때문에, 여기서는 소유권, trait 등 러스트의 주요 개념을 소개하지 않습니다.

유용한 표준 기능

수

다음 자료형이 주로 사용됩니다.

• i32, i64, i128: 부호 있는 정수 자료형 (네, 128비트가 표준으로 지원됩니다!)
• u32, u64, u128, usize: 부호 없는 정수 자료형
• f64: 부동소숫점 자료형

이 자료형들의 docs를 둘러보시면 built-in method가 정말… 정말 많다는 것을 알 수 있습니다.

정수 자료형의 built-in method 중 PS에서 유용할 만한 것들은 다음과 같습니다.

• abs, signum
• abs_diff: 무작정 빼면 오버플로우가 날 위험이 있으니, 이걸 쓰면 됩니다.
• count_ones, count_zeros, leading_ones, leading_zeros, trailing_ones, trailing_zeros: 비트 관련 함수들입니다.
• div_euclid, rem_euclid: 음수로 나눌 때 C, Rust 등 언어에서 통상적으로 쓰는 것과 달리 유클리드 나눗셈을 진행하는 함수입니다.
• from_str_radix: 특정 진법의 문자열을 정수 자료형으로 변환합니다.
• ilog, ilog10, ilog2
• is_power_of_two, next_power_of_two
• pow
• saturating_add, saturating_sub, saturating_mul, saturating_pow: 덧셈, 뺄셈, 곱셈, 거듭제곱을 하되, 오버플로우가 날 경우 정수 범위 내의 최대/최솟값으로 대체합니다.

부동소숫점 자료형의 built-in method 중 PS에서 유용할 만한 것들은 다음과 같습니다.

• abs, signum
• sin, cos, tan, asin, acos, asin, atan, atan2, sin_cos
• exp, exp2, exp_m1, ln, ln_1p, log, log10, log2, powf, powi, sqrt
• floor, ceil, clamp, fract
• hypot
• max, min
• round, trunc
• to_degrees, to_radians

cmp

https://doc.rust-lang.org/std/cmp/index.html

std::cmp::max_by_key(v1, v2, f)는 v1과 v2 중 함수 f에 적용한 결과가 더 큰 값을 반환합니다. 물론 min_by_key도 있습니다.

collections

https://doc.rust-lang.org/std/collections/index.html

이 모듈에는 기초적인 자료구조가 들어있습니다.

Vec

https://doc.rust-lang.org/std/vec/struct.Vec.html

C++의 vector, 파이썬의 list입니다. PS에서 유용할 만한 것들은 다음과 같습니다.

• len, is_empty: 길이 관련 함수
• push, pop, insert, remove, clear, resize, fill: 내용물을 수정하는 기본적인 함수
• append: 해당 Vec의 끝에 다른 Vec을 옮겨 붙입니다.
• sort_..., dedup_..., reverse, rotate_..., retain_..., select_nth_unstable, swap: 전체적인 순서를 수정하는 함수
• contains, binary_search_..., partition_point: 탐색
• concat, join: 원소들을 하나로 이어붙이는 함수
• first, last, starts_with, ends_with: 시작과 마지막을 찾는 함수
• get_mut
• iter, split_..., rsplit_..., windows: iterator
• repeat

그 외의 자료구조들

VecDeque는 덱입니다. 이름에서 유추할 수 있듯이 Vec과 비슷한 API를 지원하면서 앞뒤에 원소를 효율적으로 넣거나 뺄 수 있습니다.

HashSet은 C++의 unordered_set, 파이썬의 set입니다. C++과 달리 빠르면서 해시 충돌을 매우 잘 피합니다.

BTreeSet은 C++의 set입니다. 흥미롭게도, 특정 범위를 탐색할 때 C++의 lower_bound와 upper_bound 말고 좀 더 직관적인 API를 지원합니다. range는 범위 내의 모든 원소를 순회하는 iterator를 만들며, 이를 사용해서 x 이상의 가장 작은 수를 다음과 같은 식으로 찾을 수 있습니다.

use std::ops::Bound::*;
let elm = set.range((Included(&x), Unbounded)).next();

x 이하의 가장 작은 수는 다음과 같은 식으로 찾을 수 있습니다.

let elm = set.range((Unbounded, Included(&x))).next_back();

HashMap과 BTreeMap은 위 둘의 map 버전입니다. 여기서 눈에 띄는 기능은 entry로, “특정 key를 찾고, key가 있으면 value를 새로운 값으로 수정하고 없으면 새로운 값을 삽입”을 한 번의 lookup으로 진행할 수 있습니다. entry를 호출하면 Entry를 얻는데, 여기다가 and_modify로 “있으면 새로운 값을 수정”한 다음 or_insert로 “없으면 새로운 값을 삽입”하면 됩니다. 예시는 해당 docs 페이지에서 확인할 수 있습니다.

BinaryHeap은 우선순위 큐입니다. 기본적으로는 최댓값을 뽑습니다. 최솟값을 뽑는 우선순위큐를 만들려면 type parameter에다가 Reverse라는 타입을 넣으면 됩니다. 값을 넣을 때도 Reverse를 씌우고, 뽑을 때는 패턴 매칭이나 .0으로 Reverse를 벗기면 됩니다. 예를 들어 다음과 같이 쓸 수 있습니다.

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    let mut heap = BinaryHeap::new(); // BinaryHeap<Reverse<i32>>
    heap.push(Reverse(20));
    heap.push(Reverse(10));
    let Reverse(x) = heap.pop().unwrap();
    println!("{x}"); // 10
}

Reverse도 하나의 타입이기 때문에, x랑 Reverse(y)를 같이 넣을 수는 없습니다.

마지막으로 LinkedList라는 것도 있지만, 사용할 일은 거의 없습니다.

string

String은 (당연히) 문자열입니다. PS에서 유용할 만한 것들은 다음과 같습니다.

• parse
• as_bytes, as_bytes_mut: 특정 위치의 문자를 보려면 이걸 써야 합니다. 이유는 후술합니다.
• new, len, is_empty, push, push_str, pop, clear, insert, insert_str, remove, truncate, retain, repeat, trim_..., starts_with, ends_with
• contains, find, replace, replacen, rfind: 부분문자열을 탐색할 수 있습니다.
• chars, char_indices, matches, match_indices, split_..., rsplit_... : iterator

아쉽게도 문자열의 i번째 글자를 s[i]로 가져올 수가 없습니다. 문자열은 바이트열로 구현되어 있는데, 유니코드 때문에 문자 하나가 바이트 하나라는 보장이 없어서 아예 []를 지원하지 않게 해놓았습니다. 즉 String이 Index<usize> trait을 구현하지 않습니다. i번째 글자를 가져오는 것처럼 보이는 함수들은 다 O(n)의 시간 복잡도가 걸립니다. 온라인 저지는 대부분 아스키 문자를 사용하므로, i번째 글자를 가져오려면 s.as_bytes()[i] as char를 하면 됩니다.

“그럼 파이썬에서는 왜 되냐?”라는 의문이 들 수 있는데, 거기서는 문자열이 immutable이기 때문에 가능한 게 아닐까 추측하고 있습니다.

Box, Rc

모두 포인터에게 작별인사하세요

트리처럼 참조 관계에 사이클이 없으면서 같은 노드를 여러 다른 노드가 동시에 참조하지 않는 경우, 동적 할당된 노드들을 Box로 관리할 수 있습니다.

pub struct Tree<T> {
    pub val: T,
    l: Option<Box<Tree<T>>>,
    r: Option<Box<Tree<T>>>
}

Persistent segment tree처럼 참조 관계에 사이클이 없지만 같은 노드를 여러 다른 노드가 동시에 참조할 수 있는 경우, Rc로 관리할 수 있습니다. 코드는 아래에 첨부합니다.

참조 관계에 사이클이 있으면 NonNull을 쓸 수 있다고 들었으나, 아직 사용해본 적은 없습니다.

구현한 것들

구현한 것들 가운데 정비가 완료된 것은 다음 페이지에 코드를 공개해 두었습니다. 아무나 가져다 쓰셔도 됩니다.

입출력

표준적인 입출력 방법은 stdin().read_line()과 println!이지만, 이들은 온라인 저지에 쓰기에는 느립니다. 그 대신 stdin().lines()으로 모든 줄을 읽거나 stdin.lock()으로 lock을 잡아서 한 줄씩 읽고, std::io::BufWriter 버퍼에 출력하면 됩니다.

입출력은 PS에서 거의 무조건 사용되는데 러스트의 표준 입출력은 그리 간단하지 않기 때문에, 러스트로 PS를 하시는 분들은 자신만의 입출력 템플릿을 쓰시곤 합니다. 그래서 저도 만들었습니다.

Harmonic Lemma

https://jh05013.github.io/ps-snippets/math/harmonic.html

Iterator 연습을 위해 만들었습니다.

러스트에서 iterator를 만들려면 해당 역할을 수행하는 struct를 만들고, 그 struct에 Iterator trait을 구현하면 됩니다. 파이썬의 yield와 비교했을 때 중간 결과를 다 저장해야 해서 구현이 어렵다는 단점이 있습니다.

그래프

https://jh05013.github.io/ps-snippets/graph/trait.html

그래프 trait을 만들고, 인접 리스트에 이 trait을 구현했습니다. Trait으로 만든 이유는 격자 그래프처럼 연결 정보를 직접 저장해 놓을 필요가 없는 경우도 있기 때문입니다. 그다음으로 이 그래프 trait에 대해 BFS를 구현했습니다.

러스트는 Option 타입을 많이 사용하기 때문에, 도달할 수 없는 정점은 거리를 “아주 큰 정수”가 아니라 None으로 해놓았습니다.

세그먼트 트리

아직 공개는 안 했지만 이것도 trait을 잘 활용할 수 있습니다. 다음과 같은 Monoid trait을 만들면, 원하는 타입에 Monoid trait을 구현하면서 연산을 정의하고, 그걸로 세그먼트 트리를 만들 수 있습니다.

pub trait Monoid {
    fn id() -> Self;
    fn op(l: Self, r: Self) -> Self;
}

예를 들어 이렇게 하면 최댓값 세그먼트 트리가 됩니다.

impl Monoid for i64 {
    fn id() -> Self { 0 }
    fn op(l: Self, r: Self) -> Self { cmp::max(l, r) }
}

PST

제가 예전에 이 블로그에서 Persistent Data Structures에 대해 소개한 바가 있는데, 그중 세그먼트 트리를 구현해 보았습니다.

여기서는 노드를 동적으로 할당해야 하기 때문에 Box 또는 Rc를 써야 하는데, PST에서는 여러 노드가 같은 자식을 참조할 수 있기 때문에 Rc가 더 적합하다고 판단하여 다음과 같이 작성했습니다.

#[derive(Debug, Clone)]
pub struct Pst<T: Monoid + Copy> {
    pub val: T,
    size: usize,
    l: Option<Rc<Pst<T>>>,
    r: Option<Rc<Pst<T>>>
}

그러면 위 블로그 글에서 “노드를 복사”하는 부분은 그냥 clone 하나로 끝납니다.

pub fn update(&self, i: usize, v: T) -> Self {
    let mut news = self.clone();
    ...

그 외

나머지는 다음 페이지에서 볼 수 있습니다.

언어 비교

지금까지 파이썬, C++, 러스트 총 세 가지 언어로 PS를 해보았습니다. PS 환경에서 개인적으로 느낀 이 언어들의 장단점을 비교해 보겠습니다.

아래 비교는 전부 PS 환경을 기준으로 합니다. 개발 환경과 크게 다를 수 있습니다.

코딩 시간

경쟁 프로그래밍처럼 코딩 속도가 생명인 환경에서는 짧고 짜기 쉬운 코드가 유리합니다.

필요한 문법을 다 알고 있다고 가정할 때, 코딩 시간은 파이썬이 가장 짧습니다. 간결함을 목표로 하는 언어인 만큼 코드 길이가 짧고, 특수문자도 별로 없습니다. 이는 잘 알려져 있는 사실입니다.

C++과 러스트는 각자 장단점이 있습니다. C++이 더 긴 경우도 있고, 러스트가 더 긴 경우도 있습니다.

러스트에서 더 편한 것으로는 이런 예시가 있습니다. (좌: C++, 우: 러스트)

• 정수 벡터 정렬: sort(v.begin(), v.end()) vs v.sort()
  • 정수 벡터 일부분만 정렬: sort(v.begin()+l, v.begin()+r) vs v[l..r].sort()
• 정렬된 벡터에서 연속한 같은 원소들 제거: v.erase(unique(v.begin(), v.end()), v.end()) vs v.dedup()
• 정수 벡터에서 원소가 존재하는지 판별: find(v.begin(), v.end(), x) != v.end() vs v.contains(x)

반면 C++에서 더 편한 것으로는 이런 예시가 있습니다.

• 벡터 안 각 원소의 개수를 세는 카운터 만들기: counter[x]++ vs counter.entry(&x).and_modify(|cnt| *cnt += 1).or_insert(1)
• Tree set에서 범위 탐색: *tree.lower_bound(x) vs tree.range((Included(x), Unbounded)).next().unwrap()
• 문자열 인덱싱: s[i] vs s.as_bytes()[i] as char
• 새로 정의한 struct에 연산 정의하기: MyStruct operator+(MyStruct a, MyStruct b) { ... } vs impl Add<MyStruct> for MyStruct { type Output = MyStruct; fn add(self, b: Rhs) -> Self::Output { ... } }

두 언어에서 길이가 비슷한 것으로는 이런 예시가 있습니다.

• 실수 벡터 정렬: sort(v.begin(), v.end()) vs v.sort_by(f64::total_cmp)
• 정수 벡터에서 이분탐색: lower_bound(v.begin(), v.end(), x) - v.begin() vs v.partition_point(|num| *num < x)
• 정수 벡터의 최댓값: *max_element(v.begin(), v.end()) vs v.iter().max().unwrap()
• BFS: while(!q.empty()) { v = q.front(); q.pop(); vs while let Some(v) = q.pop_front() {
• 부분문자열 복사: s.substr(l, r-l) vs s[l..r].to_string()

코드 정확성과 디버깅

코드를 빨리 짠다 한들, 코드에 오류가 있으면 힘들어집니다. 한번에 정확한 코드를 잘 짤 수 있는지, 틀린 코드가 나왔을 때 디버깅을 잘할 수 있는지를 비교해 봅시다.

파이썬이 인터프리터 언어라는 점은 장점이자 단점으로 다가옵니다. 인터프리터 언어이기 때문에 실행이 즉석으로 되고, 런타임 에러가 난 위치도 정확하게 알 수 있으며, REPL 기능이 있어서 변수의 값을 쉽게 볼 수 있습니다. 그러나 컴파일 과정이 없기 때문에 컴파일 시간에 잡을 만한 오류는 다 런타임에서 잡히고, 이는 특수 상황이나 오랜 실행 후에야 발생할 경우 더욱 잡기 어려워집니다. 그리고 파이썬은 동적 타입 언어이기 때문에, 잘못된 타입의 값이 변수에 들어가도 이것이 바로 잡히지 않습니다.

C++은 강한 타입 시스템과 컴파일러 덕분에 위의 문제가 어느 정도 해소됩니다. 그러나 C++은 그야말로 undefined behavior의 지뢰밭입니다. 배열 범위를 넘어선 접근은 UB입니다. 빈 덱에서 pop하면 UB입니다. 초기화되지 않은 변수를 쓰면 UB입니다. 벡터를 순회하는 도중에 그 벡터에서 뭔가를 지우면 UB입니다. 일부 오류는 디버그 빌드에 플래그 몇 개 넣어서 컴파일하면 런타임에 잡을 수 있지만, 이것도 시스템마다 다르고 한계가 있습니다. 예를 들어 정수 오버플로우를 탐지하는 플래그가 있지만 제 컴퓨터에서는 쓸 수 없습니다. 게다가 제 컴퓨터 기준으로는 오류가 몇 번째 줄에서 났는지도 안 알려주기 때문에 결국에는 추정하면서 버그를 찾아내야 합니다.

UB가 아닌 것이라도 안심할 수는 없습니다. cin은 입력 받기를 실패하면 그 뒤로 그냥 “고장”이 나고 더 이상 아무것도 입력받지 않습니다. 그럼 그 뒤에 나오는 입력받으려고 했던 변수들은 초기화가 안 됩니다. 결국 UB입니다.

반면, 러스트는 사람이 실수할 만한 구석을 문법 차원에서, 컴파일러에서, 그리고 런타임에서 정말 많이 잡아줍니다. 위에서 언급한 실수를 러스트에서 하면 다음과 같은 일이 일어납니다.

• 배열 범위를 넘어선 접근은 런타임 에러입니다.
• 덱의 pop 함수는 Option<T> 타입을 반환하기 때문에, 값을 얻으려면 이걸 .unwrap하거나 패턴 매칭으로 경우를 나눠줘야 합니다. 덱이 비어있었으면 None을 반환하고, 이걸 .unwrap하면 런타임 에러입니다.
• 초기화되지 않은 변수를 쓰려고 하면 아예 컴파일이 안 됩니다.
• 벡터를 순회하는 도중에 그 벡터에서 뭔가를 지우려고 하면 아예 컴파일이 안 됩니다.
• 입력은 문자열로만 받을 수 있고, 이를 다른 타입으로 바꾸려면 .parse를 해야 합니다. 이 함수는 Result<T, Err>을 반환하고, 마찬가지로 실패해서 나온 Err에 .unwrap을 하면 런타임 에러입니다.

그리고 그렇게 런타임 에러가 났으면, 어디서 에러가 났는지도 알려줍니다.

C++과 러스트의 컴파일 에러 메시지도 흥미로운 차이를 보입니다. 이건 백문불여일견입니다. 직접 보면서 비교해 봅시다. 벡터에 순서쌍을 삽입하려고 했는데 실수로 괄호를 안 친 상황입니다.

C++에서 하면 이런 메시지가 나옵니다.

#include <bits/stdc++.h>
using namespace std;
int main(){
	vector<pair<int, string>> v;
	v.push_back(123, "asdf");
}

(파일이름).cpp: In function 'int main()':
(파일이름).cpp:5:25: error: no matching function for call to 'std::__debug::vector<std::pair<int, std::__cxx11::basic_string<char> > >::push_back(int, const char [5])'
  v.push_back(123, "asdf");
                         ^
In file included from c:\mingw\lib\gcc\mingw32\8.2.0\include\c++\vector:73,
                 from c:\mingw\lib\gcc\mingw32\8.2.0\include\c++\functional:62,
                 from c:\mingw\lib\gcc\mingw32\8.2.0\include\c++\mingw32\bits\stdc++.h:73,
                 from (파일이름).cpp:1:
c:\mingw\lib\gcc\mingw32\8.2.0\include\c++\debug\vector:464:7: note: candidate: 'void std::__debug::vector<_Tp, _Allocator>::push_back(const _Tp&) [with _Tp = std::pair<int, std::__cxx11::basic_string<char> >; _Allocator = std::allocator<std::pair<int, std::__cxx11::basic_string<char> > >]'
       push_back(const _Tp& __x)
       ^~~~~~~~~
c:\mingw\lib\gcc\mingw32\8.2.0\include\c++\debug\vector:464:7: note:   candidate expects 1 argument, 2 provided
c:\mingw\lib\gcc\mingw32\8.2.0\include\c++\debug\vector:477:2: note: candidate: 'template<class _Up> typename __gnu_cxx::__enable_if<(! std::__are_same<_Up, bool>::__value), void>::__type std::__debug::vector<_Tp, _Allocator>::push_back(_Tp&&) [with _Up = _Up; _Tp = std::pair<int, std::__cxx11::basic_string<char> >; _Allocator = std::allocator<std::pair<int, std::__cxx11::basic_string<char> > >]'
  push_back(_Tp&& __x)
  ^~~~~~~~~
c:\mingw\lib\gcc\mingw32\8.2.0\include\c++\debug\vector:477:2: note:   template argument deduction/substitution failed:
(파일이름).cpp:5:25: note:   candidate expects 1 argument, 2 provided
  v.push_back(123, "asdf");
                         ^

둘째 줄을 보면 뭔지는 알겠는데, 이것도 솔직히 C++을 처음 하는 사람이라면 이해하기 힘들 것 같습니다. 그 밑의 부분은 읽어보려고 한 적이 지금까지 없습니다. template<class _Up> typename __gnu_cxx::__enable_if<(! std::__are_same<_Up, bool>::__value), void>::__type std::__debug::vector<_Tp, _Allocator>::push_back(_Tp&&) [with _Up = _Up; _Tp = std::pair<int, std::__cxx11::basic_string<char> >; _Allocator = std::allocator<std::pair<int, std::__cxx11::basic_string<char> > >]가 대체 뭔가요…

러스트는 어떨까요?

fn main() {
    let v: Vec<(i32, String)> = vec![];
    v.push(123, "asdf".to_string());
}

error[E0061]: method takes 1 argument but 2 arguments were supplied
 --> src\main.rs:3:7
  |
3 |     v.push(123, "asdf".to_string());
  |       ^^^^
  |
note: method defined here
 --> /rustc/90c541806f23a127002de5b4038be731ba1458ca\library\alloc\src\vec\mod.rs:1824:12
help: wrap these arguments in parentheses to construct a tuple
  |
3 |     v.push((123, "asdf".to_string()));
  |            +                       +

For more information about this error, try `rustc --explain E0061`.

에러 메시지가 간결할 뿐만 아니라, 어떻게 고쳐야 하는지까지 알려주고, 심지어 더 자세히 알고 싶으면 rustc --explain E0061을 해보라고 합니다. 참고로 커멘드라인에서 rustc --explain E0061을 치면 이 링크에 있는 글이 나옵니다. 별거 없는 것 같지만, 좀 더 복잡한 오류라면 얘기가 다릅니다.

더 흥미로운 점은 어떻게 고쳐야 하는지가 “인자를 하나만 넘기세요”가 아니라 “괄호를 쳐서 튜플로 만드세요”라는 것입니다. 마치 컴파일러가 사용자의 의도를 꿰뚫고 있다는 느낌이 들었습니다. 한 번은 함수에 인자를 반대로 넣었다가 help: swap these arguments라는 말을 들은 적이 있습니다.

성능

파이썬은 느리고, C++은 빠릅니다. 이는 잘 알려져 있는 사실입니다.

러스트는 어떨까요? Undefined behavior는 컴파일러 최적화를 위해 있던 건데, 이게 사라졌으니 C++보다 느릴까요? 놀랍게도 아닙니다. 소유권, 가변성 등의 러스트 고유 기능을 최대한 사용하여 C++이 할 수 없는 최적화를 진행합니다. 또한 iterator에 map, filter 등을 덕지덕지 붙이면 느려질 것 같지만, 러스트는 zero-cost abstraction을 고수하기 때문에 그렇지 않습니다. 그 결과 속도는 C++에 맞먹고 심지어 더 빠른 경우도 있습니다. BOJ에서 파이썬처럼 언어 선택 때문에 시간 초과를 걱정할 일은 없다고 보시면 됩니다.

빌트인과 표준 라이브러리

BOJ를 비롯한 여러 온라인 저지에서는 외장 라이브러리를 쓸 수 없기 때문에, 빌트인과 표준 라이브러리가 얼마나 방대한지에 따라 이점을 볼 수 있습니다.

이 부분은 어느 하나가 가장 강력하거나 약하지 않습니다. 파이썬, C++, 러스트 모두 자신에게만 들어있는 빌트인 및 표준 라이브러리 기능을 갖추고 있으면서, 자신에게만 없는 기능도 있습니다.

셋 중 하나에만 있는 기능은 다음 예시가 있습니다.

• 파이썬: 큰 정수, 임의 정밀도 실수, 분수, 카운터, 정수 제곱근, 모든 (중복)조합에 대한 iteration, 모듈로 거듭제곱, 모듈로 역원, eval
• C++: 이전/다음 순열, 비트셋, (GNU 한정) 로프, order-statistics tree
• 러스트: 정수 자료형의 여러 복잡한 비트 연산, 패턴 매칭 (match)

반대로, 셋 중 하나에만 없어 직접 구현해야 하는 기능은 다음 예시가 있습니다.

• 파이썬: 비교 연산자가 반대인 우선순위 큐¹, 트리 기반 집합²
• C++: 문자열을 특정 문자/문자열(delimiter)마다 분할³
• 러스트: 최대공약수⁴, 복소수⁵, Regex⁶, 랜덤⁷, 모든 순열에 대한 iteration⁸

러스트에 랜덤이 없는 게 의아할 수 있는데, 이것은 러스트가 “최소한만 표준에서 유지보수하고 나머지는 Cargo(외장 모듈 관리 도구)에 맡기자”라는 정책을 취하고 있기 때문입니다. 여러 장점이 있는 방향이지만, 아쉽게도 OJ에서는 단점으로 작용합니다.

의외로 셋 모두에 있는 기능으로는 대소문자 변환⁹, 시간 계산¹⁰, 선형 시간 부분문자열 탐색¹¹ 등이 있습니다.

소감

C++로 PS를 시작했을 때는 수많은 UB를 접하며 스트레스가 쌓였는데, 러스트는 반대로 긍정적인 경험이었습니다. 그 동안의 경험이 쌓인 것도 있지만, 러스트는 수십년 간의 경험을 바탕으로 안전하게 쓸 수 있도록 설계된 언어라는 느낌이 들었습니다. 앞으로도 러스트를 쓰게 될 것 같습니다.

주석