STLチートシート

迷ったら結局リファレンスを見るのが一番速い説

vector

• 参考
  • vector - cpprefjp C++日本語リファレンス

#include <vector>
using namespace std;
// a = {0, 0, 0, 0, 0}
vector<int> a(5, 0);
// a = {1, 1, 1}
a.assign(3, 1);
// a = {1, 1, 1, 2}
a.push_back(2);
// a = {1, 3, 1, 1, 2} O(N)!!!!!!
a.insert(a.begin() + 1, 3);
// 3
a[1];
// 1
a.front();
// 2
a.back();
// 5
a.size();

• insertはO(N)なので、使わない

remove duplications

• 参考
  • c++ - What's the most efficient way to erase duplicates and sort a vector? - Stack Overflow
  • 計算速度への言及あり、重複が少なければvectorのまま, 多ければsetを経由が速い
• 以下引用

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

priority_queue

• 参考
  • priority_queue - cpprefjp C++日本語リファレンス
  • std::priority_queue の使い方および優先順位の付け方の変更 - Qiita

// declaration, default comparer is less: top is the largest element
priority_queue<pair<int, int>> que;
auto p = make_pair(1, 2);
que.push(p);
que.emplace(2, 1);
// t = {2, 1}
auto t = que.top();
que.pop();
// specify comparer to get smallest element
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que2;
que2.emplace(1, 2);
que2.emplace(2, 1);
// u = {1, 2}
cout << u.first << " " << u.second << endl;
// choose the element which has smallest pair.second
auto comp = [](pair<int, int> l, pair<int, int> r) { return l.second > r.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> que3(comp);
que3.emplace(1, 3);
que3.emplace(3, 2);
que3.emplace(2, 1);
// que3: top = {2, 1} < {3, 2} < {1, 3}

• テンプレート引数に与える比較関数でもっとも優先度が低い要素がtopになるので注意
• 自作クラスを要素にする場合、比較演算子を作成するか、ラムダ式で比較関数を作成する
  • 普通はpairかtupleを使ってしまうのが便利

string

• 参考
  • basic_string - cpprefjp C++日本語リファレンス

#include<string>
// s = "AAAAAAAAAA"
string t(10, 'A');
// s = "ABC"
string s("ABC");
// 'B'
s[1];
// s = "ABCD"
s += "D";
// erase i-th element (0-indexed)
s.erase(s.begin()+i);
// erase from i to i+n-1
s.erase(i, n);
// erase elements in [begin, end)
s.erase(s.begin(), str.end());
// initPos is the position we start to look it up
int pos = s.find("E", initPos);
if (pos == string::npos) cout << "not found" << endl;
// get substring from start to start+num-1
s.substr(start, num);
// cast to int
s = "123";
int a = stoi(s);
// cast to long long
long long b = stoll(s);
// cast numbers to string
string u = to_string(a);

• []演算子で取り出した1文字はcharなので、char literal ('0'など)と比較する