1. The Standard Templete Library(STL)
STL is the core of modern C++. There are “Containers”, “Iterators”, “Functions” and “Algorithms” in it.
2. Containers(Standford v.s. STL)
All containers can hold almost all elements. There two types of containers, one is
sequence containers, the other isassociative containers.
Sequence containers can be divide into simple sequence containers and adaptors.
- simple sequence containers:
vectoradding and removing elements at end.deque(double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end.listadding and removing elements anywhere, but no random access.tuplecan contain different data type, but immutable(不可变)
- adaptors:
stackadding or removing elements from the front.queueadding elements from the front, removing from the back.priority_queueadding elements with a priority, always removing the highest priority-element.
Accociative Containers can be divide into ordered associative containers and unordered associative containers.
- ordered associative containers
setunique elementsmapkey-value pairs
- Unordered associative containers
unordered_setunordered_map
Vector
| What you want to do. | std::vector |
|---|---|
| Create a new, empty vector. | std::vector |
| Create a vector with n copies of 0 | std::vector |
| Create a vector with n copies of a value k | std::vector |
| Add a value k to the end of a vector | vec.push_back(k) |
| Remove all elements of a vector | vec.clear() |
| Get thr element at index i | int k = vec[i] |
| Check size of vector | vec.size() |
| Loop through vector by index i | for(std::size_t i = 0; i < vec.size();++i) |
| Replace the element at index i | vec[i] = k |
| Insert k at some index i | vec.insert(vec.begin()+i, k) |
| Remove the element at index i | vec.erase(vec.begin()+i) |
| Get the sublist in range[i,j) | std::vector |
| Add k to the fromt of a vector | vec.insert(vec.begin(), k) |
Internally, a std::vector consists of a fixed-sized array. It automatically resizes for you!
size: number of elements in a vector.capacity: amount of space saved for a vector.
Wrapper(封装): a wrapper on an object changes how external users can interact with that object. Containter adaptors provide a different interface for sequence containers.
deque
As opposed to std::vector, the elements of a deque are not stored contiguously(连续的). The storage of a deque is automatically expanded and constracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector, because it does not involve copying of the existing elements to a new memory location.
set
| What do you want to do | std::set |
|---|---|
| Create an empty set | std::set |
| Add value k to the set | s.insert(k) |
| Remove value k from the set | s.erase(k) |
| Check if value is in the set | if(s.count(k)) |
| Check if set is empty | if(s.empty()) |
map
| What do you want to do | std::map<int,char> |
|---|---|
| Create an empty map | std::map<int,char>m |
| Add key k with value v into the map | m.insert({k,v}); m[k]=v; |
| Remove key k from the map | m.erase(k) |
| Check if key k is in the map | if(m.count(k)) |
| Check if the map is empty | if(m.empty()) |
| Retrieve or overwrite value associated with key k(error if key isn’t in map) | char c = m.at(k);m.at(k)=v; |
| Retrive or overwrite value associated with key k(auto-insert if key isn’t in map) | char c = m[k]; m[k]=v; |
STL maps actyally store pairs. Every std::map<k,v> is actually backed by std::pair<const k, v>. By default, the type(for sets) or key’s type(for maps) must have a comparison operator(<) defined.
unordered_map and unordered_set
Each STL set/map comes with an unordered sibling. They’re almost the same, except:
- Instend of a comparison operator, the set/map type must have a hash function defined for it.
- Simple types, like int, char, bool, double, and even std::string are already supported.
- Any containers/collections need you to provide a hash function to use them.
- unordered_map/unordered_set are generally faster than map/set.
- 本文作者： 夏花
- 本文链接： http://xiahua19.github.io/2022/07/24/cs106l-5-Containers/
- 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！