Vec, HashMap, String

// 1) Vec<T> — growable array
let mut v: Vec<i32> = Vec::new();
v.push(1); v.push(2); v.push(3);
v.len();                                   // 3
v.is_empty();                              // false
v.get(0);                                   // Some(&1)
v[0];                                       // 1 (panics if out of bounds)
v.iter().sum::<i32>();                      // 6
v.iter().rev();                             // reverse iterator
v.sort();
v.dedup();
v.contains(&2);

// Macro
let v = vec![1, 2, 3, 4, 5];
let zeros = vec![0; 100];                  // 100 zeros

// 2) String — owned UTF-8
let mut s = String::new();
s.push_str("hello");
s.push(' ');
s.push_str("world");
s.len();                                    // BYTE length, not char count
s.chars().count();                          // char count

let s2 = String::from("hi");
let s3: String = "hi".to_string();
let s4 = format!("{} {}", s2, s3);          // formatted

// &str is a borrowed string slice; String owns. Most functions take &str.
fn greet(name: &str) { println!("hi {name}"); }
greet(&s);                                  // String -> &str via deref coercion

// 3) HashMap<K, V> — hash table
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert("Mara", 95);
scores.insert("Sam",   87);
scores.get("Mara");                         // Option<&i32>
scores.contains_key("Sam");                  // true
scores.remove("Sam");
scores.len();

for (k, v) in &scores { println!("{k}: {v}"); }

// Entry API — insert if missing
let counter = scores.entry("Alex").or_insert(0);
*counter += 1;

// Group / count
let words = vec!["foo", "bar", "foo", "baz", "bar", "foo"];
let mut counts: HashMap<&str, u32> = HashMap::new();
for w in words { *counts.entry(w).or_insert(0) += 1; }
// { 'foo': 3, 'bar': 2, 'baz': 1 }

// 4) BTreeMap<K, V> — sorted by key (red-black tree)
use std::collections::BTreeMap;
let mut scores: BTreeMap<String, i32> = BTreeMap::new();
scores.insert("alex".into(), 88);
scores.insert("mara".into(), 95);
scores.insert("sam".into(),  87);
for (k, v) in &scores { println!("{k}: {v}"); }   // alphabetical order

scores.range("a".."m");                     // range iterator
scores.first_key_value();                    // Option<(&K, &V)>

// HashMap is faster for random access; BTreeMap is sorted + supports range queries.

// 5) HashSet<T> + BTreeSet<T>
use std::collections::{HashSet, BTreeSet};
let mut s: HashSet<i32> = [1, 2, 3].into_iter().collect();
s.insert(4);
s.contains(&2);                              // true
s.remove(&1);

// Set operations
let a: HashSet<_> = [1, 2, 3].iter().copied().collect();
let b: HashSet<_> = [2, 3, 4].iter().copied().collect();
let union:  HashSet<_> = a.union(&b).copied().collect();
let inter:  HashSet<_> = a.intersection(&b).copied().collect();
let diff:   HashSet<_> = a.difference(&b).copied().collect();

// 6) VecDeque<T> — double-ended queue
use std::collections::VecDeque;
let mut q: VecDeque<i32> = VecDeque::new();
q.push_back(1);
q.push_back(2);
q.push_front(0);
q.pop_front();                              // Some(0)
q.pop_back();                                // Some(2)

// Use for queues + sliding windows; faster than Vec for both ends.

// 7) BinaryHeap<T> — max-heap by default
use std::collections::BinaryHeap;
let mut h: BinaryHeap<i32> = BinaryHeap::new();
h.push(3); h.push(1); h.push(4); h.push(1);
h.peek();                                    // Some(&4) — largest
h.pop();                                     // Some(4)

// Min-heap via Reverse wrapper
use std::cmp::Reverse;
let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(3));
min_heap.push(Reverse(1));
min_heap.pop();                              // Reverse(1) — smallest

// 8) LinkedList<T> — almost never the right choice
// Worse cache locality than Vec; use Vec or VecDeque unless you need O(1) splice in the middle.

// 9) Choosing a collection
//
//   Need                                 Best choice
//   Indexed access, iteration            Vec
//   FIFO queue                            VecDeque
//   Stack                                 Vec
//   Priority queue                        BinaryHeap
//   Hash lookup                            HashMap
//   Sorted lookup / range queries          BTreeMap
//   Set membership, fast                  HashSet
//   Sorted set with range                 BTreeSet
//   Linked list                            VecDeque (LinkedList only for splice)

// 10) Iteration consumption modes
// iter()         → &T (borrow)
// iter_mut()     → &mut T (mutable borrow)
// into_iter()    → T (consume the collection)

let v = vec![1, 2, 3];
for x in &v       { /* &i32 */ }
for x in &mut v   { /* &mut i32 */ }
for x in v        { /* i32, v is moved */ }

// 11) Collect into different types
let v: Vec<i32>      = (0..5).collect();
let h: HashSet<i32>  = (0..5).collect();
let m: HashMap<i32, String> = (0..3).map(|i| (i, format!("item-{i}"))).collect();

// 12) Sorting
let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6];
v.sort();                                    // stable sort
v.sort_unstable();                            // faster, not stable
v.sort_by(|a, b| b.cmp(a));                  // descending
v.sort_by_key(|x| (-x, *x));                  // by computed key

// 13) Capacity + perf
let mut v: Vec<i32> = Vec::with_capacity(1000);
v.shrink_to_fit();                            // release unused memory
let mut m: HashMap<String, i32> = HashMap::with_capacity(100);

// Pre-allocate when size known to avoid repeated allocations.

// 14) FxHashMap — faster hash for non-adversarial input
// Use the `rustc-hash` or `ahash` crate; default HashMap uses HashDoS-resistant SipHash (slower).
// hashbrown::HashMap is also fast and is what HashMap uses internally since 1.36.

// 15) Common bugs
// • Indexing String / &str by byte position cutting a UTF-8 char — panic; use .chars() / char_indices()
// • for loop borrowing a collection while mutating — borrow checker fight; clone keys first
// • HashMap iteration order — UNDEFINED (randomised); use BTreeMap for sorted output
// • Forgot entry().or_insert_with() — recomputes for no reason; use lazy variant
// • LinkedList expecting cache locality — slower than Vec in nearly every benchmark
// • Borrowing the value from a HashMap while inserting — second insert invalidates the &V borrow
// • Iterating .keys()/.values() expecting same order across runs — random per insert
// • Using sort() in a hot path — sort_unstable() is faster when stability not needed

use std::collections::HashMap;
let mut h = HashMap::new();
h.insert("ada", 36);
for (k, v) in &h { println!("{k} -> {v}"); }