# 目次

• 目次
• 共通テンプレート
• ライブラリ
  • Stack
  • Queue
  • Vector
  • List
  • Set
  • Map
• スニペット
  • 要素の走査
  • ソートの比較関数

# 共通テンプレート

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

int main(void) {
    // code here
}

# ライブラリ

# Stack

O(1): int size()
O(1): T top()
O(1): void pop()
O(1): push(T x)
O(1): bool empty()

# Queue

O(1): int size()
O(1): T front()
O(1): void pop()
O(1): push(T x)
O(1): bool empty()

# Vector

O(1): int size()
O(1): v[i] O(1)
O(1): void push_back(T x)
O(1): void pop_back()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(n): void insert(int p, T x)
O(n): void erase(int p)
O(n): void clear()

# List

int size()
O(1): void push_back(T x)
O(1): void pop_back()
O(1): void push_front(T x)
O(1): void pop_front()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(1): void insert(int p, T x)
O(1): void erase(int p)
O(n): void clear()

# Set

set<T> S
O(1): int size()
O(n): void clear()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(logn): void insert(T key)
O(logn): void erase(T key)
O(logn): iterator<T> find(T key)
// ----
S.find(10) == S.end()

# Map

map<T1, T2> M
O(1): size()
O(n): void clear()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(logn): void insert((T1 key, T2 value))
O(logn): void erase(T1 key)
O(logn): iterator<T> find(T1 key)
O(logn): M[T1 key]
// ----
T["hoge"] = 1
T.insert(make_pair("key", 100))
pair<string, int> target = *T.find("key")
target.first
target.second

# スニペット

# 要素の走査

インデックスを使うと境界判定でミスをする可能性があるのでこちらの記法を使う.

vector<int> vec;
for (auto el: vec) {
    cout << el << endl;
};

for (auto it = vec.begin(); it != vec.end(); it++) {
    cout << *it << endl;
};

# ソートの比較関数

aが前に来るべきならtrueを、そうでないならfalseを返す.

以下は整数のペアをソートする例.

まずは第１要素で比較して、それで決まらなければ第２要素で比較する.

bool compare (pair<Int, Int> a, pair<Int, Int> b) {
  if (a.first != b.first)  return a.first < b.first;
  if (a.second != b.second) return a.second < b.second;
  return false;
}

sort(items.begin(), items.end(), compare);