Lecture 2

本节课旨在对 c++ 标准库 STL 有一个大致的了解。

 

STL


  • Containers
    • Sequential
      • array (static), vector (dynamic)
      • deque (double-ended queue)
      • forward_list (singly-linked), list (doubly-linked)
    • Associative
      • set (collection of unique keys)
      • map (collection of key-value pairs)
      • multiset, multimap
    • Unordered associative
      • hashed by keys
      • unordered_set. unordered_map
      • unordered_multiset, unordered_multimap
    • Adaptors
      • stack, queue, priority_queue
  • Algorithms
  • Iterators
 

vector


  • Constructor / Destructor
  • Element access
    • at, oprator[], front, back, data, …
  • Iterators
    • begin, end, cbegin, cend, …
  • Capacity
    • empty, size, reserve, capacity, …
  • Modifiers
    • clear, insert, erase, push_bash, …
 
一个 vector 的简单使用:
vector 支持像数组一样索引、遍历。也可以使用迭代器 Iterator,例如:
Notes: 迭代器取值需要解引用
更偷懒一点可以用 “range-based for loop”,底层也通过迭代器实现:
底层会翻译为 for (auto it = begin(evens); it < end(evens); it++)
 

list


用法基本和 vector 差不多
不同的是 list 的迭代器不是 “random access iterator”,迭代器没法做比较,所以循环结束的判定条件要写 p != s.end()
 

map


理解为键值对 key-value
但对于 map 中没有出现过的 itemprice[item] 并非简单查询而是将这个没出现的 item 插入。为了避免可以简单加一句判断 if (price.contains(item)) (in c++20)
 

stack


是一种 adapter
notion image
所谓 adapter 是一种设计模式,允许程序员在实现全部接口的前提下自己设计底层实现。例如:
很高级,没看懂😧
 

Algorithms


  • Works on a range defined as [first, last)
  • 以迭代器作为输入
 

Iterators


  • Connect containers and algorithms
后面还会讲
 

Typedefs


  • Annoying to type long names
    • map<Name, list<PhoneNum>> phonebook;
    • map<Name, list<PhoneNum>>::iterator finger;
  • Simplify with typedef
    • typdef map<Name, list<PhoneNUm>> PB;
    • PB phonebook;
    • PB::iterator finger;
  • c++11: auto , using
 

Using your own classes


  • Might need:
    • assignment operator, operator=()
    • default constructor
  • For sorted types, like set , map , …
    • less-than operator, operator<()
 
Loading...