9. Rust collections

Rust의 컬렉션 소개

Rust는 다양한 컬렉션을 표준 라이브러리에 제공합니다. 이들은 모두 제네릭하게 구현되어 있습니다.

벡터 (Vector)

벡터는 한 가지 타입의 데이터를 여러 개 담을 수 있는 제네릭한 컬렉션입니다. 다른 언어에서는 리스트나 배열과 비슷한 역할을 합니다.

let mut v = Vec::new(); // 빈 벡터 생성
v.push(5); // 값 추가
v.push(6);
v.push(7);
v.push(8);

벡터는 스택처럼 동작하기 때문에 push 메서드를 이용하여 값을 추가하면 벡터의 끝에 요소가 추가됩니다. 그리고 pop 메서드를 이용하여 벡터의 끝에서 요소를 제거할 수 있습니다.

let last = v.pop(); // 마지막 요소 제거

벡터는 메모리 내에서 연속적으로 데이터를 저장하기 때문에 인덱스를 이용하여 요소에 접근할 수 있습니다. 하지만 인덱스가 범위를 벗어나면 Rust는 안전하게 패닉을 발생시키므로 인덱스를 사용하기 전에 벡터의 길이를 확인하는 것이 중요합니다.

let third: &i32 = &v[2]; // 인덱스로 접근

아래와 같이 벡터에서 안전하게 접근하는 것이 가능합니다.

let v = vec![1, 2, 3, 4, 5];

// 인덱스가 범위를 벗어나지 않도록 검사
if let Some(third) = v.get(2) {
    println!("The third element is {}", third);
} else {
    println!("There is no third element");
}

이 코드는 get 메서드를 사용하여 인덱스로 요소에 접근합니다. 이 메서드는 Option<&T>를 반환하며, 인덱스가 범위를 벗어나면 None을 반환합니다. 따라서 안전하게 요소에 접근할 수 있습니다. 만약 인덱스가 범위를 벗어나는 경우에는 패닉이 발생하지 않습니다. 대신에 None을 반환하므로 이를 처리할 수 있어야 합니다.

벡터를 생성할 때 이미 값이 알려진 경우에는 vec! 매크로를 사용하여 편리하게 생성할 수 있습니다.

let v = vec![1, 2, 3, 4, 5];

벡터는 풍부한 메서드를 제공하여 다양한 작업을 수행할 수 있습니다. 삽입, 제거, 정렬, 반복, 이진 탐색 등 다양한 작업이 표준 라이브러리에 구현되어 있습니다.

삽입 (Insertion)

let mut v = vec![1, 2, 3, 4, 5];

// 벡터 끝에 요소 추가
v.push(6); // O(1) (평균적으로 상수 시간)

// 벡터의 특정 위치에 요소 삽입
v.insert(2, 10); // O(n) (삽입 위치 뒤의 요소들을 이동해야 하므로)

println!("Vector after insertion: {:?}", v);

제거 (Removal)

let mut v = vec![1, 2, 3, 4, 5];

// 벡터의 특정 위치에 있는 요소 제거
let removed_element = v.remove(2); // O(n) (제거 위치 이후의 요소들을 이동해야 하므로)

println!("Removed element: {}", removed_element);
println!("Vector after removal: {:?}", v);

정렬 (Sorting)

let mut v = vec![5, 1, 3, 2, 4];

// 오름차순 정렬
v.sort(); // O(n log n) (퀵소트나 머지소트와 같은 비교 기반 정렬 알고리즘을 사용)

println!("Vector after sorting: {:?}", v);

반복 (Iteration)

let v = vec![1, 2, 3, 4, 5];

// 요소를 순회하며 출력
for element in &v {
    println!("{}", element);
}
// 반복은 O(n) 시간이 소요됩니다. 벡터의 크기에 선형적으로 비례하여 요소를 순회합니다.

이진 탐색 (Binary Search)

let v = vec![1, 2, 3, 4, 5];
let target = 3;

// 이진 탐색을 사용하여 요소의 존재 여부 확인
let index = match v.binary_search(&target) {
    Ok(i) => i,
    Err(_) => panic!("Element not found"),
};
// binary_search: O(log n) (이진 탐색은 정렬된 배열에서 사용되며, 반복마다 검색 영역을 절반씩 줄여나가므로)
println!("Index of {}: {}", target, index);

해시 맵 (HashMap)

해시 맵은 키와 값으로 이뤄진 제네릭한 컬렉션입니다. 다른 언어에서는 이를 사전이라고 부르기도 합니다.

use std::collections::HashMap;

let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

해시 맵은 키를 기반으로 값을 삽입, 조회, 제거할 수 있으며 이 모든 작업을 상수 시간에 수행할 수 있습니다.

let score = scores.get("Blue"); // 값 조회
scores.remove("Yellow"); // 값 제거

해시 맵은 열거형인 Option을 반환하므로 값의 존재 여부를 안전하게 확인할 수 있습니다.

// 값 조회
if let Some(score) = scores.get("Blue") {
    println!("Score: {}", score);
} else {
    println!("Score not found");
}

// 값 제거
if let Some(_) = scores.remove("Yellow") {
    println!("Yellow score removed successfully");
} else {
    println!("Yellow score not found");
}

또는 다음과 같이 unwrap_or을 사용해 default 값을 얻어오는 것도 가능합니다.

use std::collections::HashMap;

let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

// 기본값 설정
let default_score = 0;

// 값 조회 및 기본값 설정
let blue_score = *scores.get("Blue").unwrap_or(&default_score);
let green_score = *scores.get("Green").unwrap_or(&default_score);

println!("Blue score: {}", blue_score);
println!("Green score: {}", green_score);

또한 해시 맵은 값에 대한 참조를 얻거나 키, 값 또는 키-값 쌍을 반복하는 메서드를 제공합니다.

for (key, value) in &scores {
    println!("{}: {}", key, value);
}

기타 컬렉션들에 대해서는 간단히 설명하자면 다음과 같습니다.

• VecDeque: 더블 엔디드 큐를 구현하는데, 전반적으로 벡터보다는 약간 덜 효율적이지만 앞과 뒤에서 효율적으로 아이템을 추가하거나 제거할 수 있습니다.
• LinkedList: 임의의 지점에서 아이템을 빠르게 추가하거나 제거할 수 있지만 다른 작업에 대해서는 비교적 느립니다.
• HashSet: 집합의 해싱 구현으로, 집합 연산을 효율적으로 수행합니다.
• BinaryHeap: 항상 최대값을 팝하는 우선순위 큐와 유사합니다.
• BTreeMap과 BTreeSet: 수정된 이진 트리를 사용하는 대체 맵과 집합 구현체로, 키 또는 값이 항상 정렬되어야 하는 경우에 사용됩니다.