Rust勉強中 - その22 -> コレクション

自己紹介

出田 守と申します。
しがないPythonプログラマです。
情報セキュリティに興味があり現在勉強中です。CTFやバグバウンティなどで腕を磨いています。主に低レイヤの技術が好きで、そっちばかり目が行きがちです。

Rustを勉強していくうえで、読んで学び、手を動かし、記録し、楽しく学んでいけたらと思います。

環境

新しい言語を学ぶということで、普段使わないWindowsとVimという新しい開発環境で行っています。
OS: Windows10 Home 64bit 1903
CPU: Intel Core i5-3470 @ 3.20GHz
Rust: 1.38.0
RAM: 8.00GB
Editor: Vim 8.1.1
Terminal: PowerShell

前回

前回はイテレータについて学びました。
Rust勉強中 - その21

コレクション

コレクション	説明
Vec<T>	可変な配列
VecDeque<T>	両端キュー
LinkedList<T>	リンクリスト
BinaryHeap<T> where T: Ord	優先度付きキュー
HashMap<K, V> where K: Eq+Hash	キーバリューハッシュテーブル
BTreeMap<K, V> where K: Ord	順序付きキーバリューハッシュテーブル
HashSet<T> where T: Eq+Hash	ハッシュテーブル
BTreeSet<T> where T: Ord	ソートされたハッシュテーブル

Vec<T>

Vecは、ヒープメモリ上に確保される型Tの可変な配列です。ベクタはバッファのポインタ、容量、長さという3wordのファットポインタを持っています。バッファはヒープメモリ上に確保されます。

pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

ベクタの作成方法はいろいろあります。

fn main() {
    let v: Vec<i32> = Vec::new();
    let v: Vec<i32> = Vec::with_capacity(3);
    let v           = vec![0, 1, 2];
    let v: Vec<i32> = (0..3).collect();
}

最後の方法はcollectメソッドを用いて、Rangeイテレータのアイテムを集めて、Vecのベクタを作成しています。

要素へのアクセスはインデックスや範囲を使えます。

fn main() {
    ...
    println!("{:?}", v[0]);     // 0
    println!("{:?}", &v[0..2]); // [0, 1]
    println!("{:?}", &v[0..]);  // [0, 1, 2]
    println!("{:?}", &v[..]);   // [0, 1, 2]
    println!("{:?}", &v[..2]);  // [0, 1]
    // println!("{:?}", &v[0..4]); // Panic: Out of range
}

ただし、範囲外の場合はコンパイルエラーではなく、panicが発生します。
範囲指定は、ベクタからスライスの参照にしてからアクセスしています。
また、usizeのみを許容します。Pythonのように末尾を表す-1は使えません。末尾の要素が欲しい場合はlastメソッドが使えます。

ベクタはイテレート可能で、iterメソッドやiter_mutメソッドも用意されています。

fn main() {
    ...
    let iter = v.iter().map(|item| item+1);
    for item in iter {
        println!("{:?}", item); // 1, 2, 3
    }
}

ベクタのメソッドは省略します。必要に応じてベクタのドキュメントを参照することにします。
と、思ったのですが、前回イテレータをサボったので、戒めるためにベクタのメソッドを書いていきます。(誰と戦っとんねんって感じですが・・・)
ただし、unsafe系のメソッドは、まだよくわかっていないのでスキップしています。それと、非推奨のメソッドもスキップします。

以下、nightlyのRustでしか動かないメソッドもあるので一時的にnightlyに切り替えて実行します。

rustup default nightly

ベクタのメソッド

new

pub const fn new() -> Vec<T> {
    Vec {
        buf: RawVec::new(),
        len: 0,
    }
}

T型の要素を持つ空のベクタを返します。

fn main() {
    ...
    // new
    let v: Vec<i32> = Vec::new();
}

with_capacity

pub fn with_capacity(capacity: usize) -> Vec<T> {
    Vec {
        buf: RawVec::with_capacity(capacity),
        len: 0,
    }
}

確保する容量が分かっている場合その分をあらかじめ確保して、再確保のコストを減らすことができます。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
}

capacity

pub fn capacity(&self) -> usize {
    self.buf.capacity()
}

容量の確認

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
}

reserve

pub fn reserve(&mut self, additional: usize) {
    self.buf.reserve(self.len, additional);
}

バッファの容量を長さ+additional(+α)分再確保します。なので、実行後容量が長さ+additional以上になります。指定されたadditionalより容量が既にある場合は何もしません。オーバーフローするとpanicが発生します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // reserve
    println!("<reserve>");
    let mut tmp_v = v.clone();
    tmp_v.reserve(3);
    println!("{}", tmp_v.capacity()); // 6
}

reserve_exact

pub fn reserve_exact(&mut self, additional: usize) {
    self.buf.reserve_exact(self.len, additional);
}

reserveメソッドとは違い、余分な容量を取らずきっちり再確保します。オーバーフローするとpanicが発生します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // reserve_exact
    println!("<reserve_exact>");
    let mut tmp_v = v.clone();
    tmp_v.reserve_exact(5);
    println!("{}", tmp_v.capacity()); // 8
}

try_reserve(nightly)

pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
    self.buf.try_reserve(self.len, additional)
}

動作はreserveメソッドと同じです。違いは戻り値としてResult型を返します。この時、オーバーフローまたは何らかの再確保失敗時にCollectionAllockErrを返します。

#![feature(try_reserve)]
fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // try_reserve
    println!("<try_reserve>");
    let mut tmp_v = v.clone();
    tmp_v.try_reserve(5);
    println!("{}", tmp_v.capacity()); // 8
}

try_reserve_exact(nightly)

pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), CollectionAllocErr>  {
    self.buf.try_reserve_exact(self.len, additional)
}

これも、reverse_exactと動作は同じです。違いはオーバーフローまたは何らかの再確保失敗時にCollectionAllockErrを返します。

#![feature(try_reserve)]
fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // try_reserve_exact
    println!("<try_reserve_exact>");
    let mut tmp_v = v.clone();
    tmp_v.try_reserve_exact(5);
    println!("{}", tmp_v.capacity()); // 8
}

shrink_to_fit

pub fn shrink_to_fit(&mut self) {
    if self.capacity() != self.len {
        self.buf.shrink_to_fit(self.len);
    }
}

余分な容量をできるだけ縮めます。もしかしたら余分な容量が残る可能性もあります。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // shrink_to_fit
    println!("<shrink_to_fit>");
    let mut tmp_v = v.clone();
    tmp_v.push(3);
    println!("{}", tmp_v.capacity()); // 6
    tmp_v.shrink_to_fit();
    println!("{}", tmp_v.capacity()); // 4
}

shrink_to(nightly)

pub fn shrink_to(&mut self, min_capacity: usize) {
    self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
}

min_capacityで指定された容量まで縮めます。少なくとも容量は長さとmin_capacityと同じ大きさになります。現在の容量がmin_capacityより小さければpanicになるそうです(下のように試してみたのですがpanicにはならなかったです。こういうことではない？)。

#![feature(shrink_to)]
fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // shrink_to
    println!("<shrink_to>");
    let mut tmp_v = v.clone();
    tmp_v.push(3);
    println!("{}", tmp_v.capacity()); // 6
    tmp_v.shrink_to(3);
    println!("{}", tmp_v.capacity()); // 4
}

into_boxed_slice

pub fn into_boxed_slice(mut self) -> Box<[T]> {
    unsafe {
        self.shrink_to_fit();
        let buf = ptr::read(&self.buf);
        mem::forget(self);
        buf.into_box()
    }
}

VecをBox<[T]>に変換します。余分な容量はドロップされます。

fn get_type<T>(_: T) -> &'static str {
    std::any::type_name::<T>()
}

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // into_boxed_slice
    println!("{}", get_type(v.clone().into_boxed_slice())); // alloc::boxed::Box<[i32]>
}

truncate

pub fn truncate(&mut self, len: usize) {
    let current_len = self.len;
    unsafe {
        let mut ptr = self.as_mut_ptr().add(self.len);
        // Set the final length at the end, keeping in mind that
        // dropping an element might panic. Works around a missed
        // optimization, as seen in the following issue:
        // https://github.com/rust-lang/rust/issues/51802
        let mut local_len = SetLenOnDrop::new(&mut self.len);

        // drop any extra elements
        for _ in len..current_len {
            local_len.decrement_len(1);
            ptr = ptr.offset(-1);
            ptr::drop_in_place(ptr);
        }
    }
}

ベクタをlenで指定された長さに縮めます。余分な要素はドロップされます。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // truncate
    println!("<truncate>");
    let mut tmp_v = v.clone();
    tmp_v.truncate(2);
    println!("{:?}", tmp_v); // [0, 1]
}

as_slice

pub fn as_slice(&self) -> &[T] {
    self
}

スライス&[T]に変換します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // as_slice
    println!("<as_slice>");
    let tmp_v = v.clone();
    println!("{}", get_type(tmp_v.as_slice())); // &[i32]
}

as_mut_slice

pub fn as_mut_slice(&mut self) -> &mut [T] {
    self
}

可変スライス&mut [T]に変換します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // as_mut_slice
    println!("<as_mut_slice>");
    let mut tmp_v = v.clone();
    println!("{}", get_type(tmp_v.as_mut_slice())); // &mut [i32]
}

as_ptr

pub fn as_ptr(&self) -> *const T {
    // We shadow the slice method of the same name to avoid going through
    // `deref`, which creates an intermediate reference.
    let ptr = self.buf.ptr();
    unsafe { assume(!ptr.is_null()); }
    ptr
}

ベクタのバッファへのraw pointerに変換します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // as_ptr
    println!("<as_ptr>");
    let tmp_v = v.clone();
    println!("{}", get_type(tmp_v.as_ptr())); // *const i32
}

as_mut_ptr

pub fn as_mut_ptr(&mut self) -> *mut T {
    // We shadow the slice method of the same name to avoid going through
    // `deref_mut`, which creates an intermediate reference.
    let ptr = self.buf.ptr();
    unsafe { assume(!ptr.is_null()); }
    ptr
}

ベクタのバッファへの可変なraw pointerに変換します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // as_mut_ptr
    println!("<as_mut_ptr>");
    let mut tmp_v = v.clone();
    println!("{}", get_type(tmp_v.as_mut_ptr())); // *mut i32
}

swap_remove

pub fn swap_remove(&mut self, index: usize) -> T {
        unsafe {
        // We replace self[index] with the last element. Note that if the
        // bounds check on hole succeeds there must be a last element (which
        // can be self[index] itself).
        let hole: *mut T = &mut self[index];
        let last = ptr::read(self.get_unchecked(self.len - 1));
        self.len -= 1;
        ptr::replace(hole, last)
    }
}

indexが指す要素を削除し、その要素を返します。削除された領域には、最後の要素が入るため、ずらす必要はなくremoveメソッドより順序を気にしないなら、こちらのメソッドの方が速いです。範囲外のindexを指定するとpanicが発生します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // swap_remove
    println!("<swap_remove>");
    let mut tmp_v = v.clone();
    let removed_element = tmp_v.swap_remove(0);
    println!("{}, {:?}", removed_element, tmp_v); // 0, [2, 1]
}

insert

pub fn insert(&mut self, index: usize, element: T) {
    let len = self.len();
    assert!(index <= len);

    // space for the new element
    if len == self.buf.capacity() {
        self.reserve(1);
    }

    unsafe {
        // infallible
        // The spot to put the new value
        {
            let p = self.as_mut_ptr().add(index);
            // Shift everything over to make space. (Duplicating the
            // `index`th element into two consecutive places.)
            ptr::copy(p, p.offset(1), len - index);
            // Write it in, overwriting the first copy of the `index`th
            // element.
            ptr::write(p, element);
        }
        self.set_len(len + 1);
    }
}

indexで指定された位置にelementを追加します。indexより右側の要素は右にずらされます。indexが範囲外の場合panicが発生します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // insert
    let mut tmp_v = v.clone();
    tmp_v.insert(1, 999);
    println!("{:?}",tmp_v); // [0, 999, 1, 2]
}

remove

pub fn remove(&mut self, index: usize) -> T {
    let len = self.len();
    assert!(index < len);
    unsafe {
        // infallible
        let ret;
        {
            // the place we are taking from.
            let ptr = self.as_mut_ptr().add(index);
            // copy it out, unsafely having a copy of the value on
            // the stack and in the vector at the same time.
            ret = ptr::read(ptr);

            // Shift everything down to fill in that spot.
            ptr::copy(ptr.offset(1), ptr, len - index - 1);
        }
        self.set_len(len - 1);
        ret
    }
}

indexで指定された要素を削除します。indexより右側の要素を左にずらします。indexが範囲外ならpanicが発生します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // remove
    let mut tmp_v = v.clone();
    tmp_v.remove(1);
    println!("{:?}",tmp_v); // [0, 2]
}

retain

pub fn retain<F>(&mut self, mut f: F)
    where F: FnMut(&T) -> bool
{
    self.drain_filter(|x| !f(x));
}

指定された関数またはクロージャfに要素を渡し、結果がtrueならばその要素は残し、falseなら削除します。

fn main() {
    ...
    // with_capacity
    println!("<with_capacity>");
    let mut v: Vec<i32> = Vec::with_capacity(3);
    v.push(0);
    v.push(1);
    v.push(2);
    // capacity
    println!("<capacity>");
    println!("{}", v.capacity()); // 3
    // retain
    println!("<retain>");
    let mut tmp_v = v.clone();
    tmp_v.retain(|e| e%2==0);
    println!("{:?}",tmp_v); // [0, 2]
}

dedup_by_key

pub fn dedup_by_key<F, K>(&mut self, mut key: F) where F: FnMut(&mut T) -> K, K: PartialEq {
    self.dedup_by(|a, b| key(a) == key(b))
}

keyに指定された関数またはクロージャに各要素を入れて、結果が連続した同じ結果になった場合最初の要素を除く要素を削除します。ソートされている場合、すべての重複が削除されます。

fn main() {
    ...
    // dedup_by_key
    println!("<dedup_by_key>");
    let mut tmp_v = vec![0, 10, 20, 20, 999, 20, 20];
    tmp_v.dedup_by_key(|e| *e%2==0);
    println!("{:?}",tmp_v); // [0, 999, 20]
}

まず、0, 10, 20, 20は指定したkeyでtrueになるので、要素0を除く要素が削除されます。つぎに、最後2つの要素20, 20がkeyでtrueになるので、最初の20以外の要素20を削除します。

dedup_by

pub fn dedup_by<F>(&mut self, same_bucket: F) where F: FnMut(&mut T, &mut T) -> bool {
    let len = {
        let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
        dedup.len()
    };
    self.truncate(len);
}

same_bucketに指定された関数またはクロージャに要素二つを順番に入れてます。same_bucket(a, b)がtrueであれば要素aを削除します。

fn main() {
    ...
    // dedup_by
    println!("<dedup_by>");
    let mut tmp_v = vec!["100", "100000", "111", "100", "200", "200"];
    tmp_v.dedup_by(|a, b| {println!("a={}, b={}", *a, *b); (*a).contains(*b)});
    println!("{:?}",tmp_v); // ["100", "111", "100", "200"]
}

<dedup_by>
a=100000, b=100
a=111, b=100
a=100, b=111
a=200, b=100
a=200, b=200
["100", "111", "100", "200"]

削除した要素とは、次の要素を比較していないのが分かります。つまり、連続した同じ結果の場合それらの要素が削除されます。

push

pub fn push(&mut self, value: T) {
    // This will panic or abort if we would allocate > isize::MAX bytes
    // or if the length increment would overflow for zero-sized types.
    if self.len == self.buf.capacity() {
        self.reserve(1);
    }
    unsafe {
        let end = self.as_mut_ptr().add(self.len);
        ptr::write(end, value);
        self.len += 1;
    }
}

要素を末尾に追加します。オーバーフローの場合、panicが発生します。

fn main() {
    ...
    // push
    println!("<push>");
    let mut tmp_v = vec![2, 1]; 
    tmp_v.push(0);
    println!("{:?}",tmp_v); // [2, 1, 0]
}

pop

pub fn pop(&mut self) -> Option<T> {
    if self.len == 0 {
        None
    } else {
        unsafe {
            self.len -= 1;
            Some(ptr::read(self.get_unchecked(self.len())))
        }
    }
}

末尾から要素をOption型で取り出します。すでに空の場合Noneを返します。

fn main() {
    ...
    // pop
    println!("<pop>");
    let mut tmp_v = vec![2, 1]; 
    println!("{:?}", tmp_v.pop()); // Some(2)
    println!("{:?}", tmp_v.pop()); // Some(1)
    println!("{:?}", tmp_v.pop()); // None
}

append

pub fn append(&mut self, other: &mut Self) {
    unsafe {
        self.append_elements(other.as_slice() as _);
        other.set_len(0);
    }
}

ベクタに別のベクタを結合します。渡したベクタ側は空になります。オーバーフローした場合、panicが発生します。

fn main() {
    ...
    // append
    println!("<append>");
    let mut v1 = vec![0, 1, 2];
    let mut v2 = vec![3, 4, 5];
    v1.append(&mut v2);
    println!("{:?}",v1); // [0, 1, 2, 3, 4, 5]
    println!("{:?}",v2); // []
}

drain

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
    where R: RangeBounds<usize>
{
    // Memory safety
    //
    // When the Drain is first created, it shortens the length of
    // the source vector to make sure no uninitialized or moved-from elements
    // are accessible at all if the Drain's destructor never gets to run.
    //
    // Drain will ptr::read out the values to remove.
    // When finished, remaining tail of the vec is copied back to cover
    // the hole, and the vector length is restored to the new length.
    //
    let len = self.len();
    let start = match range.start_bound() {
        Included(&n) => n,
        Excluded(&n) => n + 1,
        Unbounded    => 0,
    };
    let end = match range.end_bound() {
        Included(&n) => n + 1,
        Excluded(&n) => n,
        Unbounded    => len,
    };
    assert!(start <= end);
    assert!(end <= len);

    unsafe {
        // set self.vec length's to start, to be safe in case Drain is leaked
        self.set_len(start);
        // Use the borrow in the IterMut to indicate borrowing behavior of the
        // whole Drain iterator (like &mut T).
        let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().add(start),
                                                    end - start);
        Drain {
            tail_start: end,
            tail_len: len - end,
            iter: range_slice.iter(),
            vec: NonNull::from(self),
        }
    }
}

rangeで指定された範囲の要素を削除し、削除した要素のイテレータを返します。無効な範囲を指定した場合、panicが発生します。

fn main() {
    ...
    // drain
    println!("<drain>");
    let mut tmp_v = vec![0, 1, 2, 3, 4, 5];
    println!("{:?}",tmp_v.drain(2..4)); // Drain([2, 3])
}

clear

pub fn clear(&mut self) {
    self.truncate(0)
}

ベクタのすべての要素を削除し、空にします。定義をみると、truncate(0)を呼び出しています(なるほど)。

fn main() {
    ...
    // clear
    println!("<clear>");
    let mut tmp_v = vec![0, 1, 2, 3, 4, 5];
    println!("{:?}",tmp_v.clear()); // ()
}

len

pub fn len(&self) -> usize {
    self.len
}

ベクタの長さを返します。

fn main() {
    ...
    // len
    println!("<len>");
    let mut tmp_v = vec![0, 1, 2, 3, 4, 5];
    println!("{}",tmp_v.len()); // 6
}

is_empty

pub fn is_empty(&self) -> bool {
    self.len() == 0
}

ベクタが空かどうかチェックします。空ならtrue、それ以外ならfalse。

fn main() {
    ...
    // is_empty
    println!("<is_empty>");
    let tmp_v: Vec<i32> = vec![];
    println!("{}",tmp_v.is_empty()); // true
}

(今、メソッドハイに入りました。)

split_off

pub fn split_off(&mut self, at: usize) -> Self {
    assert!(at <= self.len(), "`at` out of bounds");

    let other_len = self.len - at;
    let mut other = Vec::with_capacity(other_len);

    // Unsafely `set_len` and copy items to `other`.
    unsafe {
        self.set_len(at);
        other.set_len(other_len);

        ptr::copy_nonoverlapping(self.as_ptr().add(at),
                                 other.as_mut_ptr(),
                                 other.len());
    }
    other
}

指定されたatから、ベクタの末尾までの要素を削除し、削除した要素のベクタを返します。範囲外のatを指定した場合、panicが発生します。

fn main() {
    ...
    // split_off
    println!("<split_off>");
    let mut tmp_v = vec![0, 1, 2, 3, 4, 5];
    println!("{:?}",tmp_v.split_off(3)); // [3, 4, 5]
    println!("{:?}",tmp_v);              // [0, 1, 2]
}

resize_with

pub fn resize_with<F>(&mut self, new_len: usize, f: F)
    where F: FnMut() -> T
{
    let len = self.len();
    if new_len > len {
        self.extend_with(new_len - len, ExtendFunc(f));
    } else {
        self.truncate(new_len);
    }
}

ベクタの長さを指定されたnew_lenにし、新たな要素にはfに指定された結果を追加します。要素の型にDefaultトレイトが実装されている場合は、Default::default()を指定できます。

fn main() {
    ...
    // resize_with
    println!("<resize_with>");
    let mut tmp_v = vec![0, 1, 2];
    tmp_v.resize_with(6, Default::default);
    println!("{:?}",tmp_v); // [0, 1, 2, 0, 0, 0]

    let mut tmp_v = vec![0, 1, 2];
    let mut n = 2;
    tmp_v.resize_with(6, || {n=n+1;n});
    println!("{:?}",tmp_v); // [0, 1, 2, 3, 4, 5]
}

leak(nightly)

pub fn leak<'a>(vec: Vec<T>) -> &'a mut [T]
    where
    T: 'a // Technically not needed, but kept to be explicit.
{
    Box::leak(vec.into_boxed_slice())
}

&mut [T]に変換します。この時、Tのライフタイムに注意が必要です。先にドロップしてしまった場合ダングリングポインタを指すことになります。

#![feature(vec_leak)]

fn main() {
    ...
    // leak
    println!("<leak>");
    let mut tmp_v = vec![0, 1, 2];
    println!("{}", get_type(Vec::leak(tmp_v))); // &mut [i32]
}

ここからは、要素TがCloneトレイトを実装している必要があります。

resize

pub fn resize(&mut self, new_len: usize, value: T) {
    let len = self.len();

    if new_len > len {
        self.extend_with(new_len - len, ExtendElement(value))
    } else {
        self.truncate(new_len);
    }
}

ベクタの長さを指定されたnew_lenにします。新たな要素にはT型のvalueを追加します。

fn main() {
    ...
    // resize
    println!("<resize>");
    let mut tmp_v = vec![0, 1, 2];
    tmp_v.resize(6, 999);
    println!("{:?}", tmp_v); // [0, 1, 2, 999, 999, 999]

}

extend_from_slice

pub fn extend_from_slice(&mut self, other: &[T]) {
    self.spec_extend(other.iter())
}

otherで指定したスライスをベクタに追加します。イテレータを引数にとるextendメソッドとほとんど同じなので、もしかしたらこのメソッドは廃止になる可能性があるそうです。

fn main() {
    ...
    // extend_from_slice
    println!("<extend_from_slice>");
    let mut tmp_v = vec![0, 1, 2];
    tmp_v.extend_from_slice(&[3, 4, 5]);
    println!("{:?}", tmp_v); // [0, 1, 2, 3, 4, 5]
}

ここからは、要素TはPartialEqトレイトを実装している必要があります。

dedup

pub fn dedup(&mut self) {
    self.dedup_by(|a, b| a == b)
}

重複した要素を削除します。ソートしている場合すべての重複した要素が削除されます。

fn main() {
    ...
    // dedup
    println!("<dedup>");
    let mut tmp_v = vec![1, 1, 1, 2, 1, 3, 3];
    tmp_v.dedup();
    println!("{:?}", tmp_v); // [1, 2, 1, 3]
}

remove_item(nightly)

pub fn remove_item(&mut self, item: &T) -> Option<T> {
    let pos = self.iter().position(|x| *x == *item)?;
    Some(self.remove(pos))
}

ベクタからitemで指定された要素を削除します。削除した要素が存在すればSome(T)を返し、なければNoneを返します。

#![feature(vec_remove_item)]

fn main() {
    ...
    // remove_item
    println!("<remove_item>");
    let mut tmp_v = vec![0, 1, 2];
    tmp_v.remove_item(&1);
    println!("{:?}", tmp_v); // [0, 2]
}

splice

pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
    where R: RangeBounds<usize>, I: IntoIterator<Item=T>
{
    Splice {
        drain: self.drain(range),
        replace_with: replace_with.into_iter(),
    }
}

ベクタからrangeで指定された範囲の要素を、replace_withで指定されたイテレータと入れ替えます。入れ替えられた要素はSplice型として返されます。範囲外のrangeを指定するとpanicが発生します。

fn main() {
    ...
    // splice
    println!("<splice>");
    let mut tmp_v = vec![0, 1, 2];
    let replace_with = vec![3, 4, 5];
    let ret: Vec<i32> = tmp_v.splice(1.., replace_with).collect();
    println!("{:?}", ret);   // [1, 2]
    println!("{:?}", tmp_v); // [0, 3, 4, 5]
}

drain_filter(nightly)

pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
    where F: FnMut(&mut T) -> bool,
{
    let old_len = self.len();

    // Guard against us getting leaked (leak amplification)
    unsafe { self.set_len(0); }

    DrainFilter {
        vec: self,
        idx: 0,
        del: 0,
        old_len,
        pred: filter,
        panic_flag: false,
    }
}

ベクタからfilterに要素を入れていき、trueを返した要素はDrainFilter型で返し、falseの場合はそのまま残します。

#![feature(drain_filter)]

fn main() [
    ...
    // drain_filter
    println!("<drain_filter>");
    let mut tmp_v = vec!["10", "11", "101", "110", "201"];
    let v10: Vec<&str> = tmp_v.drain_filter(|e| e.contains("10")).collect();
    println!("{:?}", v10);   // ["10", "101", "110"]
    println!("{:?}", tmp_v); // ["11", "201"]
}

まだ、この後もDerefのメソッドが続きますが、全部はもう・・・

sort

pub fn sort(&mut self)
    where T: Ord
{
    merge_sort(self, |a, b| a.lt(b));
}

スライスを対象に要素を昇順でソートします。同じ値は並べ替えません。

fn main() {
    ...
    // sort
    let mut tmp_v = vec![2, 0, 0, 1];
    tmp_v.sort();
    println!("{:?}", tmp_v); // [0, 0, 1, 2]
}

sort_by

pub fn sort_by<F>(&mut self, mut compare: F)
    where F: FnMut(&T, &T) -> Ordering
{
    merge_sort(self, |a, b| compare(a, b) == Less);
}

スライスを対象に要素を指定された関数またはクロージャcompareによって昇順でソートします。
第一キーが同じで第二キーでソートしたい場合タプルを使用します。

fn main() {
    ...
    // sort_by
    println!("<sort_by>");
    let mut tmp_v = vec![(2, 1), (0, 5), (0, 2), (1, 2)];
    tmp_v.sort_by(|a, b| {
        a.cmp(b)
    });
    println!("{:?}", tmp_v); // [(0, 2), (0, 5), (1, 2), (2, 1)]
}

sort_by_key

pub fn sort_by_key<K, F>(&mut self, mut f: F)
    where F: FnMut(&T) -> K, K: Ord
{
    merge_sort(self, |a, b| f(a).lt(&f(b)));
}

スライスを対象に要素を関数またはクロージャkeyから得られたキーをもとにソートします。keyの処理が高価な場合、sort_by_chched_keyメソッドを使うことで高速になる可能性があります。

fn main() {
    ...
    // sort_by_key
    println!("<sort_by_key>");
    let mut tmp_v = vec![(2, 1), (0, 5), (0, 2), (1, 2)];
    tmp_v.sort_by_key(|e| {
        e.0+e.1
    });
    println!("{:?}", tmp_v); // [(0, 2), (2, 1), (1, 2), (0, 5)]
}

binary_search, binary_search_by, binary_search_by_key

binary_search

pub fn binary_search(&self, x: &T) -> Result<usize, usize>
    where T: Ord
{
    self.binary_search_by(|p| p.cmp(x))
}

binary_search_by

pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
    where F: FnMut(&'a T) -> Ordering
{
    let s = self;
    let mut size = s.len();
    if size == 0 {
        return Err(0);
    }
    let mut base = 0usize;
    while size > 1 {
        let half = size / 2;
        let mid = base + half;
        // mid is always in [0, size), that means mid is >= 0 and < size.
        // mid >= 0: by definition
        // mid < size: mid = size / 2 + size / 4 + size / 8 ...
        let cmp = f(unsafe { s.get_unchecked(mid) });
        base = if cmp == Greater { base } else { mid };
        size -= half;
    }
    // base is always in [0, size) because base <= mid.
    let cmp = f(unsafe { s.get_unchecked(base) });
    if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) }

}

binary_search_by_key

pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
    where F: FnMut(&'a T) -> B,
          B: Ord
{
    self.binary_search_by(|k| f(k).cmp(b))
}

ソートされたスライスを対象に要素を検索したい場合に、これらのメソッドを利用します。見つかればOk(index)を返し、見つからなければその値が挿入できるインデックスをErrで返します。

fn main() {
    ...
    // binary_search
    println!("<binary_search>");
    let mut tmp_v = vec![1, 2, 5, 9, 10];
    println!("{:?}", tmp_v.binary_search(&2));  // Ok(1)
    println!("{:?}", tmp_v.binary_search(&3));  // Err(2)
    println!("{:?}", tmp_v.binary_search(&11)); // Err(5)
}

VecDeque<T>

先頭末尾の操作をVecよりも効率的に行えるリングバッファを持つ両端キューです。デックと呼ばれるそうです。

pub struct VecDeque<T> {
    tail: usize,
    head: usize,
    buf: RawVec<T>,
}

VecDequeには様々な生成方法があります。

use std::collections::VecDeque;

fn main() {
    let vdeq: VecDeque<i32> = VecDeque::new();
    let vdeq: VecDeque<i32> = VecDeque::with_capacity(5);
    let vdeq                = VecDeque::from(vec![0, 1, 2]);
    let vdeq                = VecDeque::from(vec![0, 1, 2]);
    use std::iter::FromIterator;
    let vdeq                = VecDeque::from_iter((0..5));
}

まずは、useでインポートする必要があります。
VecDequeとVecは相互にfromメソッドで変換できます。

一部メソッドを以下に紹介します。

fn main() {
    ...
    // push_front
    println!("<push_front>");
    let mut vdeq = VecDeque::from(vec![1]);
    vdeq.push_front(0);
    println!("{:?}", vdeq); // [0, 1]
    // push_back
    println!("<push_back>");
    let mut vdeq = VecDeque::from(vec![1]);
    vdeq.push_back(2);
    println!("{:?}", vdeq); // [1, 2]
    // pop_front
    println!("<pop_front>");
    let mut vdeq = VecDeque::from(vec![0, 1, 2]);
    vdeq.pop_front();
    println!("{:?}", vdeq); // [1, 2]
    // pop_back
    println!("<pop_back>");
    let mut vdeq = VecDeque::from(vec![0, 1, 2]);
    vdeq.pop_back();
    println!("{:?}", vdeq); // [0, 1]
}

それ以外のメソッドについてはVecDequeドキュメントを参照することにします。Vecと似たメソッドもあります。

LinkedList<T>

双方向リンクリストです。個々の要素はヒープメモリ上に確保され、それぞれポインタで相互につながっています。

pub struct LinkedList<T> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<Box<Node<T>>>,
}

LinkedListはnewを使って生成します。

use std::collections::LinkedList;

fn main() {
    let ll: LinkedList<i32> = LinkedList::new();
}

メソッドはVecDequeと似ている部分もあるので割愛します。

参照:
LinkedListドキュメント

BinaryHeap<T>

キーの最大値が常に先頭に来るようにしたコレクション型。要素TはOrdトレイトを実装している必要があります。

pub struct BinaryHeap<T> {
    data: Vec<T>,
}

生成方法はいろいろあるようです。

use std::collections::BinaryHeap;

fn main() {
    let _binh: BinaryHeap<i32> = BinaryHeap::new();
    let _binh: BinaryHeap<i32> = BinaryHeap::with_capacity(3);
    let _binh                  = BinaryHeap::from(vec![0, 1, 2]);
    use std::iter::FromIterator;
    let binh                   = BinaryHeap::from_iter((0..3));
    while let Some(e) = binh.pop() {
        println!("{}", e); // 2, 1, 0
    }
}

昇順にしたい場合は、std::cmp::Reverseを使うそうです。

fn main() {
    ...
    // Reverse
    use std::cmp::Reverse;
    let mut binh = BinaryHeap::new();
    binh.push(Reverse(2));
    binh.push(Reverse(1));
    binh.push(Reverse(0));
    while let Some(e) = binh.pop() {
        println!("{:?}", e); // Reverse(0), Reverse(1), Reverse(2)
    }
}

popメソッドのほかにpeekメソッドでも値を取得できます。popは最大値を削除するのに対して、peekは最大値を取得します。

fn main() {
    ...
    // peek
    let mut binh = BinaryHeap::new();
    binh.push(2);
    binh.push(1);
    binh.push(0);
    println!("{:?}", binh.peek()); // Some(2)
    println!("{:?}", binh); // [2, 1, 0]
}

HashMap

HashMapはキーと値をペアに持つコレクション型です。このペアのことをエントリと呼びます。一つのヒープメモリ上にテーブルを確保し、ハッシュ値、キー、値を確保します。同じキーをもつエントリは一つのみです。
Kは、HashトレイトとEqトレイトを実装している必要があります。
キーは変更不可能ですが、値は変更可能です。

pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}

生成方法には以下のようなものがあります。

use std::collections::HashMap;

fn main() {
    let _hm: HashMap<i32, char> = HashMap::new();
    let hm: HashMap<i32, char>  = vec![(0, 'a'), (1, 'b')].into_iter().collect();
}

メソッドの一部を紹介します。

insert

pub fn insert(&mut self, k: K, v: V) -> Option<V> {
    self.base.insert(k, v)
}

エントリを追加します。キーが存在しない場合はNoneを返し、存在する場合はSome(value)を返します。

fn main() {
    ...
    // insert
    let mut hm = HashMap::new();
    println!("{:?}", hm.insert(0, 'a')); // None
    println!("{:?}", hm.insert(1, 'b')); // None
    println!("{:?}", hm.insert(0, 'c')); // Some('b')
    println!("{}",   hm[&0]); // c
    println!("{}",   hm[&2]); // panic
}

存在しないキーに直接アクセスしようとするとpanicが発生します。

get

pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
    where
    K: Borrow<Q>,
    Q: Hash + Eq,
{
    self.base.get(k)
}

指定されたkから、キーを検索しその値を取得します。存在すればSome(value)を返し、なければNoneを返します。

fn main() {
    ...
    // insert
    let mut hm = HashMap::new();
    println!("{:?}", hm.insert(0, 'a')); // None
    println!("{:?}", hm.insert(1, 'b')); // None
    println!("{:?}", hm.insert(0, 'c')); // Some('b')
    ...
    // get
    println!("{:?}", hm.get(&0)); // Some('a')
    println!("{:?}", hm.get(&2)); // None
}

keys

pub fn keys(&self) -> Keys<'_, K, V> {
    Keys { inner: self.iter() }
}

キーのイテレータを返します。

fn main() {
    ...
    // insert
    let mut hm = HashMap::new();
    println!("{:?}", hm.insert(0, 'a')); // None
    println!("{:?}", hm.insert(1, 'b')); // None
    println!("{:?}", hm.insert(0, 'c')); // Some('b')
    ...
    // keys
    println!("{:?}", hm.keys()); // [0, 1]
}

values

pub fn values(&self) -> Values<'_, K, V> {
    Values { inner: self.iter() }
}

値のイテレータを返します。

fn main() {
    ...
    // insert
    let mut hm = HashMap::new();
    println!("{:?}", hm.insert(0, 'a')); // None
    println!("{:?}", hm.insert(1, 'b')); // None
    println!("{:?}", hm.insert(0, 'c')); // Some('b')
    ...
    // values
    println!("{:?}", hm.values()); // ['b', 'c']
}

contains_key

pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
    where
    K: Borrow<Q>,
    Q: Hash + Eq,
{
    self.base.contains_key(k)
}

キーが存在するかチェックします。

fn main() {
    ...
    // insert
    let mut hm = HashMap::new();
    println!("{:?}", hm.insert(0, 'a')); // None
    println!("{:?}", hm.insert(1, 'b')); // None
    println!("{:?}", hm.insert(0, 'c')); // Some('b')
    ...
    // contains_key
    println!("{}", hm.contains_key(&0)); // true
    println!("{}", hm.contains_key(&2)); // false
}

そのほかのメソッドは、HashMapドキュメントを参照します。

Entry型

Entry型とそのメソッドを使えば、エントリが存在するかしないか、しない場合に新しいエントリを追加することができます。

pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}

HashMapのEntry値の取得はentryメソッドで得られます。

fn main() {
    ...
        // entry
    let mut hm: HashMap<String, i32>  = HashMap::new();
    hm.insert(String::from("jan"), 1);
    {
        let jan = hm.entry(String::from("jan"));
        println!("{:?}", jan); // Entry(OccupiedEntry { key: "jan", value: 1 })
    }
    {
        let feb = hm.entry(String::from("feb"));
        println!("{:?}", feb); // Entry(VacantEntry("feb"))
    }
}

Entry値は可変参照で受け取るので、そのEntry値をドロップするまで複数作成できません。
変数janは存在するキーに対してEntry値を取得しています。一方、変数febは存在しないキーに対してEntry値を取得しています。
Entry型には下記のようなメソッドが用意されています。

• or_insert, or_insert_with
  エントリが存在しなければ、指定した値で新しいエントリを追加します。or_insert_withは引数に関数またはクロージャを指定できます。可変参照の値を返します。
• key
  entryで指定したキーを返します。
• and_modify
  エントリが存在する場合、その値の可変参照を指定された関数またはクロージャに渡します。
• or_default
  エントリが存在しない場合、デフォルト値のエントリを追加します。

fn main() {
    ...
    // entry
    let mut hm: HashMap<String, i32>  = HashMap::new();
    hm.insert(String::from("jan"), 1);
    {
        let jan = hm.entry(String::from("jan"));
        println!("{:?}", jan); // Entry(OccupiedEntry { key: "jan", value: 1 })
    }
    {
    {
        let feb = hm.entry(String::from("feb"));
        println!("{:?}", feb); // Entry(VacantEntry("feb"))
        println!("{}", feb.or_insert(2)); // 2
    }
    {
        let mar = hm.entry(String::from("mar"));
        println!("{}", mar.or_insert_with(|| 3)); // 3
    }
    {
        let apr = hm.entry(String::from("apr"));
        println!("{}", apr.key()); // apr
        apr.or_insert(4);
    }
    {
        let may = hm.entry(String::from("may"));
        println!("{}", may.and_modify(|v| {*v+=1}).or_insert(4)); // 4
        let may = hm.entry(String::from("may"));
        println!("{}", may.and_modify(|v| {*v+=1}).or_insert(4)); // 5
    }
    {
        let jun = hm.entry(String::from("jun"));
        println!("{}", jun.or_default()); // 0
    }
}

BTreeMap<K, V>

BTreeMapはB木のデータ構造を持つコレクション型です。
Kはキーの順番を保つためにOrdを実装している必要があります。

pub struct BTreeMap<K, V> {
    root: node::Root<K, V>,
    length: usize,
}

生成方法やメソッド、Entry型もほとんど同じなので割愛させていただきます。

参照:
BTreeMapドキュメント

HashSet<T>とBTreeSet<T>

HashSetとBTreeSetは、同じ値を含めることができないコレクションです。同じ値が含まれているかどうかを判定するのが高速です。

pub struct HashSet<T, S = RandomState> {
    map: HashMap<T, (), S>,
}

pub struct BTreeSet<T> {
    map: BTreeMap<T, ()>,
}

それぞれ、HashMapとBTreeMapをラップした形になっています。

セット同士の論理演算

セット同士の論理演算が用意されています。

use std::collections::HashSet;

fn main() {
    let mut s1 = HashSet::new();
    s1.insert(String::from("jan"));
    s1.insert(String::from("feb"));
    let mut s2 = HashSet::new();
    s2.insert(String::from("jan"));
    s2.insert(String::from("mar"));
    println!("{:?} & {:?} = {:?}", &s1, &s2, &s1 & &s2); // {"jan", "feb"} & {"mar", "jan"} = {"jan"}
    println!("{:?} | {:?} = {:?}", &s1, &s2, &s1 | &s2); // {"jan", "feb"} | {"mar", "jan"} = {"jan", "feb", "mar"}
    println!("{:?} - {:?} = {:?}", &s1, &s2, &s1 - &s2); // {"jan", "feb"} - {"mar", "jan"} = {"feb"}
}

参照:
HashSetドキュメント
BTreeSetドキュメント

今回はここまでー！
もう無理やーーーー