stl c++ 数据结构

vector<T> v
  • v.push_back(a), v.pop_back(), v.back(), v.size(), v.empty(), v.clear()

queue<T> q
  • q.push(a), q.pop(), q.front(), q.empty()

stack<T> s
  • s.push(a), s.pop(), s.top(), s.empty()

unordered_map<TKey, TValue> uMap   (using as hashtable access O(1))
  • uMap[key] = value, uMap.at(key)
  • uMap.emplace(key, value), uMap.insert(make_pair<TKey, TValue>(key, value))
  • uMap.find(key), return iterator 
  • uMap.size(), uMap.emtpy()
  • uMap.count(key) == 1 or == 0
  • NOTE: access a map by a key which does not exist, can cause a new key insert with a default value.

unordered_set<T> uSet, hashset, no duplication, access O(1)
  • uSet.insert(v),
  • uSet.count(v) == 0 or == 1
  • uSet.erase(v)
  • uSet.empty()

map<TKey, TValue> m, BST based. access O(log(n))   
  • m[key] = value, m.at(key)
  • m.emplace(key, value), m.insert(make_pair<TKey, TValue>(key, value))
  • m.find(key), return iterator 
  • m.size(), m.empty()

set<T> s, BST based. access O(log(n))
  • s.insert(v),
  • s.count(v) == 0 or == 1
  • s.erase(v)
  • s.empty()

deque<T> dq, double-ended queue
  • dq.size(), dq.resize(), dq.empty()
  • dq[index], dq.at(index), dq.front(), dq.back()
  • assign(int num, T value), assign(it.begin(), it.end()), 
  • push_back(v), push_front(v), pop_back()

priority_queue<T> pq
  • pq.push(v), pq.pop(), pq.top(), pq.emtpy(), pq.size()
  • NOTE:  A sorted queue which always has the max value on the top. You can push any value to the right position, and you can peek or pop the max value from queue. Push to or pop from the queue is O(logn), while peek the top value is O(1). A priority_queue is not de-depulicated, so it allows multiple items with same value in the queue. A priority_queue can have its customized comparator, so it can defined its own "highest priority value". if want have min heap, negative the value or have a default comparator such as great().
  • Priority queues are a type of container adaptors. vector and deque are satisfied container.
  • default priority_queue is a max heap. to have a min heap 
  • std::priority_queue<int> second (myints,myints+4); max heap
  • std::priority_queue<int, std::vector<int>, std::greater<int>> third (myints,myints+4); min heap
     
     
     

Comments

Popular posts from this blog

Unique Binary Search Trees

Coin in Line