
C++ Learning Roadmap

STL
overview of STL

why use c++ for development?
- community
- developing or evolving
- open source (unlike Java , which is owned by Oracle, so you can use c++ for business need.)
- super extensible (boost library like c++ STL plus plus)
Containers Adaptors
- stack & queue
Adapt vector and deque containers to suit this particular need.
- why not just user a vector/deque?
Express ideas and intent directly in code. And compartmentalize messy constructs.
Associative Containers
have no idea of sequence
Data is accessed using the key instead of indexes.
includes:
- std::map<T1,T2>:associate one key type of data with other value type of data
- std::set
- std::unordered_map<T1,T2>
- std::unordered_set
map & set are based on ordering property of keys(needs to be comparable)
when to use map/set , when to use unordered ones?
map/set: iterate through a range of elements
unordered: access individual elements by key
- How do we iterate over associative containers?
use Iterators
Multimaps
- Maps store unique keys
- sometimes we want the map to have the same key pointing different values
1 | multimap<int, int> myMMap; |
Iterators
why iterator is powerful?
- many scenarios require looking at elements, regardless of what type of container is storing those elements.
- go through sequence in a standardized way( use the exact same code to perform a logical action, regardless of the data structure, independent of the container)
philosophy in Iterators
- let us view a non-linear collection in a linear manner(iterate one by one without visiting twice)
Map Iterators
- the iterator of map<string, int> points to a std::pair

auto time = std::make_pair(1,45);
- find vs. count
count is just a call to the find. So find is faster
Iterator types

the one on the right is more powerful than the left one.
Templates
Why use template functions(generic functions)?
- They are such a powerful tool that could solve a bunch of similar problems.
what if there are multiple potential templates functions?


Concept Lifting
- Question the assumptions you place on the parameters whether they are really necessary?
- Can you solve a more general problems by relaxing the constraints?
An amazing example:

Implicit interfaces
- a template function defines an implicit interface that each template parameter must satisfy
Concept
- A predicate, evaluate at compile time, that is a part of the interface
predicate(谓语)
predicate is a function which takes in some numbers of arguments and returns a boolean
unary predicate: one argument
binary predicate: two arguments
more generic version of countOccurences:
1 | template<typename InputIterator, typename UniaryPredicate> |
what if we want predicate to be more flexible?
pre c++11 solution:
use classses, of course,we have to override operators.

c++11 solution:
use lambda, it’s an object but acts like a function, because it generate the class and create an instance of it.
you can use auto in parameters to templatize the lambda
1 | int main(){ |
- you can also capture by reference, only capture the variables you need
1 | set<string> teas{"black","green","oolong"}; |
Algorithms
Why use algorithms?
- Abstractions
- Generic
- Correct
- Heavily optimized
std::sort
1 | auto compareRating = [] (const Course& c1, const Course& c2){ |
std::nth_element
1 | auto m = v.begin() + v.size()/2; |
std::stable_partition

- return: Iterator to the first element of the second group
1 | auto isDep = [](auto element){ |
std::copy_if
1 |
|
上面两例copy_if的最后一个参数使用了Iterator Adaptor
- back_inserter
- ostream_iterator
std::remove_if
- remove can change the content, but does not change the size of the container(because it is not a member of std::vector)

- erase-remove idiom:
1 | v.erase(std::remove_if(v.begin(),v.end(),pred),v.end()); |
std::find
Wrapping Up The STL
Abstraction in the STL

1 | std::string str_tolower(std::string s) { |
fileToString: get the file into a string
1 | string fileToString(ifstream& file){ |
countOccurrences: find the number of the word that appears in a text
- why can’t we use std::count()?
cause, iterator in string actually points to a character, which can only count character
- use std::search() instead
Searches for the first occurrence of the sequence of elements [s_first, s_last)
in the range [first, last)
1 | int countOccurrences(){ |
1 | int dotProduct(const vector<int>& vec1,const vector<int>& vec2){ |
- Post title:CS106L笔记:STL
- Post author:sixwalter
- Create time:2023-08-05 11:14:26
- Post link:https://coelien.github.io/2023/08/05/course-learning/CS-106L/STL/
- Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.