My Favorite STL Container
Hi. I was browsing hackernews today and found #100DaysToOffload, which is a blogging movement encouraging people to publish 100 pieces of content on their personal blog in a year. The website says that's one post every 3.5 days, but I started a bit late for that. There are 226 days left this year, so it'll be something every other day for me.
Before the coronavirus pandemic, I was journaling every day using emacs Org Journal. I really loved journaling because it helped me recognize things I did well and not so well during my day. I could then use those reflections to not make the same mistake twice. I stopped journaling because when I went home for spring break I put my laptop in my room, but the computer that I'm at all day is somewhere else. That could obviously be resolved, but now I'm here to do this for a while.
std::map
So, I love the C++ STL. The algorithms are awesome, iterators just make sense to me, and the containers are beautiful. When I say "favorite STL container", I don't mean the best. They all have their own use cases and places where they shine, but my favorite one to use is the Map/Multimap. A map is an associative container storing key-value pairs. Basically that means you declare a map with a key type K and a value type V, and you access the value of an entry using its key. Here's a quick example of that:
#include <map>
#include <std::string>
int
main () {
// Initializtion
std::map<std::string, int> numbers; // numbers maps strings to ints
numbers["one"] = 1; // This maps the string "one" to the int 1
numbers["two"] = 2; // You get the idea
// Iterators
auto num = numbers.begin (); // std::map stores elements in order, std::unordered_map does not
std::string key = num->first; // This gives the key of the entry
int val = num->second; // This gives the value of the entry
}
Complexities
Maps are implemented using a balanced binary tree, so all inserts, deletes, and searches are O(log n) complexity. This is because in order to get to an element you have to search to the level in the tree where it is. If the element you're operating on is at the maximum depth of the tree, log n gives you the depth of the tree where the element will be. Maps are a happy medium between lists and vectors. Vectors have linear inserts and deletes in the middle, but constant random access. Lists have linear access, but constant inserts and deletes. Maps sacrifice the constant time operations to have no linear operations.
Use Cases
Consider using a map for user access to an object with a string. You can create a map mapping strings to your object type so users can enter a string and get back the object that the string maps to. You can create a quasi relational database this way. For example: say a game you're making has in inventory system, and you want to let players search for an item in your inventory. You can use a map<string, item> to search for the item with the string the user entered.
Further Reading
std::map on cppreference
red-black trees on wikipedia
STL containers on cppreference
#100DaysToOffload