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:
vector
adding 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.list
adding and removing elements anywhere, but no random access.tuple
can contain different data type, but immutable(不可变)
- adaptors:
stack
adding or removing elements from the front.queue
adding elements from the front, removing from the back.priority_queue
adding 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
set
unique elementsmap
key-value pairs
- Unordered associative containers
unordered_set
unordered_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 许可协议。转载请注明出处!