// An array to hold the pattern for dealing cards in Euchre
std::array<int, 8> deal_pattern = {3,2,3,2,2,3,2,3};

// Caution! A default-initialized std::array is not empty.
std::array<int, 5> nums; // Contains 5 ints with memory junk values

// Use indexing to access elements
cout << nums[0] << endl;
nums[3] = 10;

// Default constructor creates an empty vector
std::vector<int> vec;

// Push/Pop only at the back
vec.push_back(1);
vec.pop_back();
// vec.push_front(2); NOT AVAILABLE
// vec.pop_front(); NOT AVAILABLE

// Indexing
vec[i] = x;    // no bounds checking
vec.at(i) = x; // throws exception if out of bounds

// Traversal by index
for(int i = 0; i < vec.size(); ++i) {
  cout << vec[i] << endl;
}

// Traversal by iterator
for(auto it = vec.begin(); it != vec.end(); ++it) {
  cout << *it << endl;
}

// Traversal with range-based for loop
for(auto &elem : vec) {
  cout << elem << endl;
}

// std::vector provides "random-access iterators" that may use +, -, <, etc.
auto it1 = vec.begin() + 3;
auto it2 = vec.end() - 1;
cout << *it1 << endl; // prints the element at index 3
cout << it2 - it1 << endl; // prints the distance between the iterators
cout << it1 < it2 << endl; // prints true if it1 comes before it2

// Some std::vector functions use an iterator interface.
// .insert()/.erase() have linear time complexity since they must shift elements.
vec.insert(vec.begin() + 2, 5); // insert 5 at index 2
vec.erase(vec.begin() + 3); // remove element at index 3

// Many algorithms in the standard library operate via iterators.
auto it = min_element(vec.begin(), vec.end()); // find minimum element
sort(vec.begin(), vec.end()); // Sort the vector in ascending order
auto it = lower_bound(vec.begin(), vec.end(), 5); // binary search, finds the first element >= 5

// Default constructor creates an empty list
std::list<int> list;

// Push/Pop at front or back
list.push_back(1);
list.pop_back();
list.push_front(2);
list.pop_front();

// Indexing is NOT available
// list[i] = x; NOT AVAILABLE
// list.at(i) = x; NOT AVAILABLE

// Traversal by iterator
for(auto it = list.begin(); it != list.end(); ++it) {
  cout << *it << endl;
}

// Traversal with range-based for loop
for(auto &elem : list) {
  cout << elem << endl;
}

// std::list provides "bidirectional iterators" supporting the standard
// operations *, ->, ++, --, ==, and != (but not +, -, <, etc).
auto it = list.begin();
++it;
++it;
++it;
cout << *it << endl; // prints the element at index 3

// Some std::list functions use an iterator interface.
// .insert()/.erase() have constant time complexity, assuming
// you already have an iterator to the desired location.
list.insert(it, 5); // insert 5 at before the element it points to
list.erase(it); // remove element it points to

// Algorithms that only require forward iterators can be used with lists.
auto it = min_element(list.begin(), list.end()); // find minimum element

// std::sort requires random-access iterators and is not available for lists.
// sort(list.begin(), list.end()); NOT AVAILABLE

// lower_bound is available, but it has linear time complexity, since an
// implementation based on binary search would require random access.
auto it = lower_bound(list.begin(), list.end(), 5);

// A set of uniqnames of students taking a course
std::set<string> students;

auto it = students.find("spongbob");
if (it != students.end()) {
  // spongbob is in the set
}
else {
  // spongbob is not in the set
}

// Add "patrick" (does nothing if already in the set)
students.insert("patrick");

// Remove "squidward" (does nothing if not present)
students.erase("squidwrd");

// Example 1: Traversal by iterator in ascending sorted order
for(auto it = students.begin(); it != students.end(); ++it) {
  cout << "Uniqname=" << *it << endl;
}

// Example 2: Traverse with range-based for loop in ascending sorted order
for(auto &uniqname : students) {
  cout << "Uniqname=" << uniqname << endl;
}

// A map storing the number of each kind of fruit on the countertop
std::map<string, int> fruit_counts;

auto it = fruit_counts.find("apple");

// Print key and value if the entry exists
if (it != fruit_counts.end()) {
  cout << "Key=" << it->first << endl;
  cout << "Value=" << it->second << endl;
}

// Attempt to insert an entry with key="pineapple", value=2
// Use a structured binding to unpack the returned pair.
// it is an iterator, success is a boolean.
auto [it, success] = fruit_counts.insert({"pineapple", 2});

if (success) {
  // In this case, it is an iterator to the newly inserted entry
}
else {
  // In this case, it is an iterator to the previous entry with
  // the given key (i.e. the one that blocked the attempted insert)
}

fruit_counts["apple"] = 5; // store the value 5 for the key "apple"

cout << fruit_counts["apple"]; // prints 5, the stored value for the key "apple"
cout << fruit_counts["banana"]; // prints 0 (the placeholder value created)

string fruit_name;
cin >> fruit_name; // ask the user for an arbitrary fruit name
fruit_counts[fruit_name] += 2; // Add 2 more
// ^^ If the user had entered "apple", makes 5 + 2 = 7 apples
// ^^ If the user had entered "orange", makes 0 + 2 = 2 oranges

fruit_counts.erase(it);
fruit_counts.erase("banana");

// Example 1: Traversal by iterator in ascending sorted order by key
for(auto it = fruit_counts.begin(); it != fruit_counts.end(); ++it) {
  cout << "Key=" << it->first << endl;
  cout << "Value=" << it->second << endl;
}

// Example 2: Traverse with range-based for loop in ascending sorted
// order by key. Use a structured binding to unpack the key-value pair.
// The & avoids unnecessary copying.
for(auto & [fruit_name, count] : fruit_counts) {
  cout << "Key=" << fruit_name << endl;
  cout << "Value=" << count << endl;
}