What are the different types of collection in Rust

Reading Time: 4 minutes

Rust’s standard library includes a number of very useful data structures called collections. A collection is something that holds zero or more elements in some fashion that allows you to enumerate those elements, add or remove elements, find them and so forth.

Rust’s collections can be grouped into four major categories:

  • Sequences
  • Maps
  • Sets
  • Misc

Sequences Collection

Sequences are supported in many forms in Rust.

  • Vec
  • VecDeque
  • Linkedlist

1. Vec : Vector

 Vectors allow you to store more than one value in a single data structure that puts all the values next to each other in memory. A contiguous growable array type. They are useful when you have a list of items, such as the lines of text in a file or the prices of items in a shopping cart.

Initialising a new empty vector

let mut vec = Vec::new();

Inserting elements in vector

vec.push(1);
vec.push(2);

Deleting elements from vector

vec.remove(1);

Creating an array using vector

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

2. VecDeque

A double-ended queue implemented with a grow-able ring buffer. The default usage of this type as a queue is to use push_back to add to the queue, and pop_front to remove from the queue. Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory. 

Initialising a new empty VecDeque

use std::collections::VecDeque;

let mut vec = VecDeque::new();

Inserting elements in VecDeque

// pushing elements in the front of Deque
vec.push_front(1);
vec.push_front(2);
vec.push_front(3);

// pushing elements at the end of Deque
vec.push_back(4);
vec.push_back(5);
vec.push_back(6);

Deleting elements from VecDeque

// deleting element from the front of Deque
vec.pop_front();

// deleting element from the end of the Deque
vec.pop_back();

3. LinkedList

The Linked List allows pushing and popping of elements at either end in constant time. Use Linked List if you want a Vec or VecDeque of unknown size.

Initialising a new empty LinkedList

use std::collections::LinkedList;

let mut list = LinkedList::new();

Inserting elements in LinkedList

// pushing elements in the front of linkedlist
list.push_front('a');
list.push_front('b');

// pushing elements at the end of linkedlist
list.push_back('c');
list.push_back('d');

Deleting elements from LinkedList

// deleting element from the front of linkedlist
list.pop_front();

// deleting element from the end of linkedlist
list.pop_back();

Performance

Maps Collection

In map collection, each item is referenced by a unique key. Some maps can maintain the order of insertion.

1. HashMap

The type HashMap <K,V> stores a mapping of keys of type K to values of type V. It does this via a hashing function, which determines how it places these keys and values into memory. Hash maps are useful when you want to look up data not by using an index but by using a key that can be of any type.

Initialising a new empty HashMap

use std::collections::HashMap;

let mut map = HashMap::new();

Inserting elements in HashMap

map.insert(1,String::from("Rust"));
map.insert(2,String::from("Java"));

Deleting elements from HashMap

map.remove(1);
map.remove(2);

2. BTreeMap

Binary search tree (BST) is the optimal choice for a sorted map.In particular, every element is stored in its own individually heap-allocated node. Use BTreeMap if you want a map sorted by its keys.

Initialising a new empty BTreeMap

use std::collections::BTreeMap;

let mut map = BTreeMap::new();

Inserting elements in BTreeMap

map.insert(1,String::from("Rust"));
map.insert(2,String::from("Java"));

Deleting elements from BTreeMap

map.remove(1);
map.remove(2);

Performance

Sets

Rust set is a very important data structure of rust programming language. It is derived from mathematical set theory.

1. HashSet

Hashset internally uses Hashmap for its implementation.  A HashSet requires that the elements implement the Eq and Hash traits. HashSet does’t allow duplicate values. HashSet permits to have a single null value.

Initialising a new empty HashSet

use std::collections::HashSet;

let mut set = HashSet::new();

Inserting elements in HashSet

set.insert(1,String::from("Rust"));
set.insert(2,String::from("Java"));

Deleting elements from HashSet

set.remove(1);
set.remove(2);

2. BTreeSet

BTreeSet is the set based on B-Tree. It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the set.

Initialising a new empty BTreeSet

use std::collections::BTreeSet;

let mut set = BTreeSet::new();

Inserting elements in BTreeSet

set.insert(1,String::from("Rust"));
set.insert(2,String::from("Java"));

Deleting elements from BTreeSet

set.remove(1);
set.remove(2);

Misc

BinaryHeap

A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as an array. A Binary Heap is either Min Heap or Max Heap.

Initialising a new empty Min Binary Heap

Either std::cmp::Reverse or a custom Ord implementation can be used to make Binary Heap a min-heap.

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

let mut heap = BinaryHeap::new();

Initialising a new empty Max Binary Heap

std::collections::BinaryHeap alone is used to make Binary Heap a max-heap.

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();

Inserting elements in BinaryHeap

heap.push(1);
heap.push(2);
heap.push(3);

Deleting elements from BinaryHeap

// Removes the greatest item from the binary heap and returns it, or None if it is empty.
heap.pop();

Thanks for reading !!

If you want to read more content like this?  Subscribe to Rust Times Newsletter and receive insights and latest updates, bi-weekly, straight into your inbox. Subscribe to Rust Times Newsletter: https://bit.ly/2Vdlld7.


Knoldus-blog-footer-image