c++ stl

05 February 2021

C++ STL

Terms

Container: 基本上是一種class template, 定義好各個method來access這個class object(包括get,at,或者直接overwrite operation []), 只要宣告class的data type就可以用

Vector

基本上就是allocate一個空間的array, 可以random access, 而且可以任意增加array長度. 當array長度超過allocate空間時就會reallocate到新的更大的記憶體位置,原本假設是n個元素會超過allcoate的空間,則下次的空間會足夠2n個元素(倍數成長,減少需要allocate的次數)

一般來說Vector每次allocate都會是一個大空間(Capacity),而vector真正用到的空間(Size)都會小於capacity

insert, remove相對花時間( O(n))

Vector Initialize

// Create a vector of size n with
// all values as 10.
vector<int> vect(n, 10);

// Initializing like arrays 
vector<int> vect{ 10, 20, 30 };

// Initializing with array
int arr[] = { 10, 20, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> vect(arr, arr + n);

// Initializing with other vector
vector<int> vect1{ 10, 20, 30 };
vector<int> vect2(vect1.begin(), vect1.end());

API:

empty: test if vector is empty
reserve: increase capacity
resize: change size
front/back: return front/back
at: Mostly same as [] operator, only additionally check if n is out of bound
clear: remove all element(size = 0)
insert(i,v): position i加入element v, 搬移的時候是O(n), 就是array的作法, 超過大小還會另外需要allocate
erase(it): 移除element, parameter是iterator(myvec.begin()+n)這種形式, 也可以一次傳進兩個iterator, 那就範圍內的值都會刪掉

Reference: GeekforGeeks

deque

double-ended queue

  • efficient insert/remove operation (O(1))
  • dynamic array implementation
  • random access through iterators (O(1))

  • element can be scattered through storage(element are linked through probably linked list), no need to have a consecutive storage space and occasionally reallocate like vectors.

  • 統整:
    • 利用iterator可以random access而且比較快insert,remove
    • 不用allocate一大塊空間來存資料,而是各個資料可以存在不同storage chunk
    • 他是利用一個二微陣列第一微陣列指向每個不同的chunk(bucket)第一個chunk,最後一個chunk有空位可以push_front,back, 滿了再allocate一塊新的chunk,一微陣列再多一個元素指向新的chunk
    • insert時就去那個chunk 加一個元素並把其他元素往後面擠,因為分chunk所以amortized的insert是O(1)
size: deque size
front/back: 第一個/最後的元素
at,[]: random access
push_back/push_front/pop_back/pop_front
insert(position,value)/erase(iterator,[iterator end]): 插入或刪除
begin/end: return iterator to the begin/end
empty, size, resize, clear

iterator:
deque<int>::iterator it = mydeque.begin();

可能的Use-After Free

常常我們使用queue來做bfs, 如以下的code, 在很特殊少見的狀況下會發生Use After Free, 原因有二, 第一個是 const auto & 如果element的例子那會變成 int &* ptr，也就是跟queue內的element是同個指標，不是copy指標。

第二個原因是storage chunk, 以此題為例storage chunk內每個element都是int指標，正常狀況下front, pop只是queue的第二層指標移向下一個element,該指標還是valid(指向int物件, 只是不應使用了)，一但剛好pop時是這個chunk的最後一個element, 這會導致這個chunk被清掉，此時chunk內的element(int指標)都會變成invalid,被清掉，這時候const auto &ptr這個指標就會失效。

解法就是如果是queue內是指標，不應該使用const auto &, 應該使用const auto。這樣就會複製一個指標指向該物件但不是跟queue共用指標。

queue<int *> q;
while(!q.empty()) {
  const auto &ptr = q.front(); q.pop();  // Possible UAF
}

emplace_back and push_back

emplace_back是C++11新增的feature, 目標是加速新增元素的一個method。但他跟std::move基本上是同一個時間release的。在鮮少地方emplace_back會比push_back更有效率，但大部分狀況是沒太大的差別的，原因是push_back也support move constructor，不同處有二

  1. push_back本身是method overload, emplace_back是template, 所以兩者在編譯上對編譯器要做的工有明顯的差異, push_back就單純的method overload, 但emplace_back的使用 compiler要做template type deduction產生一個對應的method, function。

傳統使用push_back總共做了兩件事

  1. 建立一個tmp物件
  2. 使用copy或move constructor把它移到container裡面

Reference:

queue

empty, size
front,back
push,pop

queue底部實作也是用deque

Reference: deque implemenation

set

  • element cannot be modified and should be unique in value
  • element can be inserted or removed
  • unbalanced binary search tree(RB Tree)
  • slower than unorder set
begin/end: return iterator
empty/size
insert/erase(val,it): erase可以用value或者iterator當參數(會刪掉iterator只到的值)

set operation

set_intersection, set_difference, set_union在algorithm內而不是set的class method, 原因之一是set本身是binary search tree的實做, 他並不是一個真正的set(hash map之類的mapping實做),所以binary search tree做union, intersect這些Operation的代價就很高 但這些不限於set container, array, vector也都可以用

set_union(iterater1,iterator2,outputit): 基本上就是比較兩個set的元素(兩個set或array本身是有sorted的,然後比較有沒有那個元素就加進去), 船進去兩個iterator把結果輸出到第三個iterator, 所以要先創好第三個container和他的size

int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  std::vector<int>::iterator it;

  std::sort (first,first+5);     //  5 10 15 20 25
  std::sort (second,second+5);   // 10 20 30 40 50

  it=std::set_union (first, first+5, second, second+5, v.begin());
                                               // 5 10 15 20 25 30 40 50  0  0
  v.resize(it-v.begin());                      // 5 10 15 20 25 30 40 50

find key

const bool is_in = container.find(element) != container.end();

iterate

std::set<unsigned long>::iterator it;
for (it = SERVER_IPS.begin(); it != SERVER_IPS.end(); ++it) {
    u_long f = *it; // Note the "*" here
}

Unorder set

set with no particular order, fast retrievial of individual element

Implement with kind of bucket, the element are assigned to a specific bucket based on the hash value, and this provide a fast access to a single element.

  • 資料少用unorder(少collision), 資料多用order

Reference: microsoft docs

Set實做

師大演算法-set

bitmap實做: 宣告integer array, 一個integer能記錄32個數字(1個bit記錄一個數字)

Map

  • binary search tree
  • slower than unorder map
  • key elements are sorted with compared object
  • [] , at operator, same as vector
    • at will throw outofrange exception if no key match
begin/end: return iterator
insert(pair)/erase: 
也可以直接用a['hello'] = 'world'這種insert方式, 有多種insert方式
如果a[key] key不存在,他會創造這個key的reference指向null, 所以size會+1, 而不是throw exception

std::map<char,int> mymap;
mymap.insert ( std::pair<char,int>('a',100) );
mymap.insert ( std::pair<char,int>('z',200) );

//erase
mymap.erase(iterator/key)
it = mymap.find(...)
mymap.erase(it)

print map element
 for (it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

find element
std::map<char,int>::iterator it = mymap.find('b');
if(it != mymap.end()){...}

unorder map

  • different from map, elements are not sorted
  • elements are stored in buckets(based on their hash value)
  • less efficient for range iteration through a subset of element
  • key,value are stored in container: pair

construct

#include <unordered_map>
std::unordered_map<std::string,double> mymap = {
     {"mom",5.4},
     {"dad",6.1},
     {"bro",5.9} };
     
const bool is_in = container.find(element) != container.end();

iterator access

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>)

運作原理

unordered_map是以hash table的方式來進行物件的儲存，hash table size初始化為1，可以使用在初始化時調整bucket count或者使用reserve(reserve本身也會觸發reshash, unordered_map的hash不支援consistent hashing) 來調整bucket數量。當儲存的物件太多而bucket太少時容易發生collusion，因此unordered_map

關於bucket數量，可以透過bucket_count() method來查詢目前有的bucket數目，size來查詢目前有的物件數目，而size/bucket_count就是load_factor, 當load_factor小於threshold (max_load_factor)，就會觸發rehash跟擴大bucket數目，bucket數目就是乘以2(但不會大於max_bucket_count的數量)，然後對於所有的物件做rehash, 所以一開始若能先確立bucket數目就可以先init或reserve,減少rehash發生的狀況。rehash發生時unordered_map的iterator就會失效要重新建立(畢竟在unordered_map存放位置不同了,但物件本身的指標不會變)

rehash: 平均複雜度是O(n) n為物件的數量，worst case為O(n^2), 原因是unordered_map採用linear probing, 每次都collision就是O(n^2)

reference:
stackoverflow
cplusplus hash function

List

  • allow constant time insert,remove in the sequence
  • iteration both side (implement with doubly linked list)
  • elements don’t have to store in consecutive storage(linked list)
  • insert / extract / swap element faster than others
  • no direct access to a single element
push_front/push_back
pop_front/pop_back
empty
size
begin/end: return iterator to the begin/end
front/back: access 第一/最後的值(list沒有random access)
remove(v): remove element with specific value
unique: remove duplicate value
sort(cmp): cmp should be either a function or methods(cmp)
merge: 把兩個list merge成一個(前提是兩個都要是sort好的), first.merge(b,cmp)
reverse: reverse order

bool cmp_ex (const std::string& f, const std::string& s)
{
  unsigned int i=0;
  while ( (i<first.length()) && (i<second.length()) )
  {
    if (tolower(first[i])<tolower(second[i])) return true;
    else if (tolower(first[i])>tolower(second[i])) return false;
    ++i;
  }
  return ( first.length() < second.length() );
}

Linked-list變形

Reference: 師大演算法筆記

  • Circular linked list: linked-list結尾連回linked-list的頭
  • Xor linked list: 一種節省memory的doubly linked list實作
    • 原本doubly linked list每個node要維持兩個pointer: prev,next, 現在這種做法每個node只需要存prev node跟next node的address xor的值, 然後在iterate時可以透過記住prev node跟現在這個node, xor prev node記憶體位址跟cur node存的值得到next node, 要得到prev node就一樣把next node address跟cur node的值xor得到prev node, 所以等於每個node只要存一個值就能達到前後移動的linked list
    • youtube
  • Unrolled linked list:
    • linked list裡面元素是array元素, 所以在allocate元素時可以先從linked list找到在哪個block再去找block裡面的array, 增加搜尋的速度(deque時做就是這樣)
    • 當一個block裡面元素太多,就把一個block拆成兩個block, 兩個相鄰block元素太少可以合成一個block,可以達到O(1) insertion,跟O(sqrtN)的search, 假設每個block內的元素都是sqrtN, 然後有sqrtN個block

priority_queue

heap structure,存取最大或最小的element, 允許random access priority queue的參數為<int,vector,cmp) 第一項為datatype,第二項為container(一定要是deque/vector),第三個可以是less/greater或自訂比較方法

push/pop
top
size/empty

priority_queue<int,vector<int>,greater<int>/less<int>>

Reference: priority queue with self-defined struct

Compare Object

  • compare two objects, return true / false, comp(a,b)
    • true: a should go before b
    • false: b should go before a

algorithm

min / max function / unique

max/min(a,b)

it = min/max_element(vec.begin(),vec+n,myobj)

To use unique, the vector should be sorted
it = unique(vector.begin(),vector.end(),func())
vector.resize(distance(vector.begin(),it))

sort / stable_sort

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)
  • sort in acscending order, O(nlogn) for C++11
  • a should have random-acceses iterator (should have swap function implmented), first iterator points to the first element and the second iterator points to the last element
  • cmp is a compare function return boolean
    • true: first element should go first
    • false: first element should go after second element
  • stable sort preserve element order

C++ sort V.S C qsort

  c++ sort c qsort
algorithm introsort+hybrid quick sort
flexibility Support various of container only basic datatype
spped fast slow
complexity C++11 O(nlogn) O(nlogn) on average

https://www.geeksforgeeks.org/c-qsort-vs-c-sort/

Heap

  • make_heap(random access it1,it2): 傳入開頭跟結尾的iterator(但是要能random access的),這段範圍內的data會變成heap(nlogn)
  • pop_heap: 最大的資料被移到array中last-1的位置(然後heap size-1), 所以最大資料現在是在array[last-1] 然後是在heap外面, 這時要再用pop_back把他移除
  • push_heap: 把array[last-1]位置的值進行upheap放到應該要對應的位置,然後heap大小+1
  • front: 回傳heap的root node
  • sort_heap: heap sort vector的element
int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';

  std::sort_heap (v.begin(),v.end());

  std::cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++)
    std::cout << ' ' << v[i];

Reference

http://c.biancheng.net/stl/

String

可以random accses s[i]

有find,substr之類的function

begin/end: return iterator
length/size: 依樣的東西,strlen
+= / append: append string
push_back/pop_back: 最後一個元素
insert(pos,char/string) / erase: 可以insert string或者char
replace(pos,len,string): replace the string
erase(pos,len) / erase(it1,it2): substring between iterator
c_str(): string object轉成char array, strcpy (cstr, str.c_str());
compare: s.compare(s2), 相當於strcmp(回傳0代表相同)
substr: s.substr(3,5) 回傳一個範圍內的string
find: s.find("live") 找live的位置,回傳int

Reference: string insert cplusplus doc

strlen, strcat, strcpy

C語言裡的string operation是極其沒效率的, 這些函式實作是寫在glibc裡面

strlen所花的時間就是O(n) 因為她就是Iterate整個string直到遇到\0, 所以如果string裡面提前有一個\0的符號strlen就只會計算到這裡, 其實蠻多問題的

strcat所花的時間則是O(N+M), 兩個string的長度相加, 原因是要先找到第一個string最後的位置才能做append, 然後在一個一個character把第二個string append到第一個string的後面

strcpy本身是用memcpy的形式來做, 所以並不是一個一個character複製到destination address, 但memcpy有一個參數是要copy的數量, 所以其實等於還是要跑一次strlen才知道要copy多少資料過去給destination address

memcpy & memmove & memset

void *memcpy(void *__dst, const void *__src, size_t __n);

基本上就是把source address的資料複製__n大小到dst address, 但因為src, destionation可能會有overlap的情況, 所以memcpy在glibc裡面會去呼叫___memcpy_chk的巨集來檢查這件事, 在O2以上的編譯優化下, 如果src, dst有overlap會噴warning, 此外__memcpy_chk也會對於記憶體複製有些優化

在src, dest address會overlap的情況下,可以改用memmove來做, 此外memcpy,memset的時間複雜度似乎也是O(n) (linear to the size), 但當然有做一些優化, 例如一次就傳8個byte(long long)而不是一次傳一個byte的形式。 基本上時做細節都是根據compiler的細節決定，所以優化方式都不太一樣。

Function Object

struct cmplarger {
    bool operator()(Ticket const& p1, Ticket const& p2)
    {
        return p1.price < p2.price;
    }
};
struct cmpsmaller {
    bool operator()(Ticket const& p1, Ticket const& p2)
    {
        return p1.price > p2.price;
    }
};

priority_queue<Ticket,vector<Ticket>,cmplarger> t;

Function object定義就是一個object但是他可以被呼叫, 這是一個oop的概念, 在heap或者sort之類的地方, 最後一個參數是cmp, 通常可以是function object, 而C++有幫忙定義好primitive type的function object (greater(), less()之類的), 但要自己比較struct的話,就要自己這樣寫, 創造一個struct但改寫bool operator()()

又如

class Output
{
public:
  void operator() ( int x )
  {
    std::cout << x << ", ";
  }
};

Output a;
a(10);

Reference

Heresy function object