c++ setとmap

```c++

#include<iostream>
#include<set>
using namespace std;

int main() {
	set<int>st;//ローカル変数として、stを生成
	return 0;
}
```

```c++

set<int> st{3,1,4,1};
```
setは重複を許さない順序付き集合なので、上記のように重複データがある場合は、重複データは自動的に削除され、｛１，３，４｝だけが格納される。

```c++

set<int> org{3,1,4};
set<int> x(org);
```
上記のコードはorgをコピーするので、{1,3,4}という値をもつ動的配列xを生成する。

```c++

#include<iostream>
#include<set>
using namespace std;

int main() {
	set<int>st{ 3,1,4,1,5,9,2,6,5,3,5 };
	auto itr = st.begin();
//最初の要素へのイテレータを取得
	cout << *itr;
//イテレータの指す先のデータを表示
	return 0;
}
```
イテレータの型はset<型>::iteratorであるが、タイプが大変なので通常は上記のようにautoを使用する。setのイテレータはランダム・アクセス不可で、前後にのみ移動できる。ix番目の要素に無理やりアクセスしたい場合は、begin()で取ってきたイテレータをix回インクリメントする

```c++

auto itr = st.begin();
for(int i = 0;i < 5; ++i)
   ++itr;
```
とすると、6が出力される。

全ての要素を表示するときは、お決まりの書き方。

```c++

#include<iostream>
#include<set>
using namespace std;

int main() {
	set<int>st{ 3,1,4,1,5,9,2,6,5,3,5 };
	for (auto itr = st.begin(); itr != st.end(); ++itr) {
		cout << *itr;
	}
	return 0;
}
```
これで全部表示される。
こんな書き方もあるみたい

```c++

#include<iostream>
#include<set>
using namespace std;

int main() {
	set<int>st{ 3,1,4,1,5,9,2,6,5,3,5 };
	for (auto x : st) {
		cout << x;
	}
	return 0;
}
```

データの追加
insertを利用する。

```c++

set<int>st{3,1,4};
st.insert(2);//値２を追加
```

データの削除
eraseを利用する
erase（値）が格納されていれば、それを削除する。リターン値として、削除したデータの個数(0 or 1)を返す。

```c++

set<int>st{3,1,4};
auto c = st.erase(3);//３を削除、１が返ってくる
```
偶数を全て削除したい例

```c++

#include<iostream>
#include<set>
using namespace std;

int main() {
	set<int>st{ 1,2,3,4,5,6};
	for (auto itr = st.begin(); itr != st.end();) {
		if (*itr % 2 == 0)
			itr = st.erase(itr);
		else
			++itr;;
	}
	for (auto ITR = st.begin(); ITR != st.end(); ++ITR) {
		cout << *ITR;
	}

	return 0;
}
```

erase(first,last):iterator


```c++

#include<iostream>
#include<set>
using namespace std;

int main() {
	set<int>st{ 1,2,3,4,5,6};
	auto first = st.find(2);
	auto last = st.find(4);
	st.erase(first, last);
	for (auto itr = st.begin(); itr != st.end(); ++itr)
		cout << *itr;
	return 0;
	//要素2,3を削除
}
```
agc 005 b

```c++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////


int main() {
	int N; cin >> N;
	int a[200100];
	REP(i, N)cin >> a[i];
	REP(i, N)a[i]--;
	vector<int>idx(N);
	REP(i, N)idx[a[i]] = i;
	set<int>s;
	ll ans = 0;
	for (int x = 0; x <=N-1; ++x) {
		int i = idx[x];
		int l = -1;
		int r = N;
		s.insert(i);
		auto itr1 = s.find(i);
		if (itr1 != s.begin()) {
			--itr1;
			l = *itr1;
		}
		auto itr2 = s.find(i);
		++itr2;
		if (itr2 != s.end()) {
			r = *itr2;
		}
		ans += (ll)(x + 1)*(i - l)*(r - i);
	}
	cout << ans << endl;
	return 0;
}
```
abc 140 E

```c++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

//Ci:=最大値がiになる区間の個数
//求めるべき値はΣCi*i
//例えば2 1 5 7 3 4 6ならC7は16
//次に考えるべきは2 1 5と3 4 6の二つの区間。7をまたぐと最大値は7に変わるので考える必要がない
//abababaaaa←(x)baabaa a<=x b>x
//2番目に大きいという条件はbをちょうど一つ含む、ということ

int main() {
	int N; cin >> N;
	vector<int>a(N);
	REP(i, N)cin >> a[i];
	REP(i, N)a[i]--;
	vector<int>idx(N);
	REP(i, N)idx[a[i]] = i;
	set<int>s;
	ll ans = 0;
	for (int x = N - 1; x >= 0; --x) {
		int i = idx[x];
		ll c = 0;
		{//calc c
			s.insert(i);
			vector<int>l(2,-1);
			vector<int>r(2,N);
			{// calc l
				auto it = s.find(i);
				REP(j, 2) {
					if (it == s.begin())break;
					--it;
					l[j] = *it;
				}
			}
			{// calc r
				auto it = s.find(i);
				REP(j, 2) {
					++it;
					if (it == s.end())break;
					r[j] = *it;
				}
			}
			vector<int>ls(2);
			ls[0] = i-l[0];
			ls[1] = l[0] - l[1];
			vector<int>rs(2);
			rs[0] = r[0] - i;
			rs[1] = r[1] - r[0];
			c = (ll)ls[0] * rs[1] + (ll)ls[1] * rs[0];
		}
		ans += c * (x + 1);
	}
	cout << ans << endl;
	return 0;
}
```
イテレータ破壊について
2019プログラミング王決定戦D

```c++
while (it != se.end() && *it < R[i]) {
			res += T[i];
			auto it2 = it;
			++it2;
			se.erase(it);
			it = it2;
		}
```
これなら大丈夫だけど
it2つくらないでそのままitでやるとバグる

```c++
std::vector<int> v = {2};
auto i = v.begin();
v.insert(i, 0);   // v == {0, 2}
++i;
v.insert(i, 1);   // v == {0, 0, 2}
// 期待していた結果: v == {0, 1, 2}
```
これが原因？だと思う
対処方法

```c++
std::vector<int> v = {2};
auto i = v.begin();
i = v.insert(i, 0); // v == {0, 2}
++i;
i = v.insert(i, 1); // v == {0, 1, 2}
```

prevについて

```c++
int main()
{
  std::vector<int> v = {3, 1, 4, 5, 2};

  {
    decltype(v)::iterator it = std::prev(v.end()); // イテレータを1回逆に進める
    std::cout << *it << std::endl;
  }//2
  {
    decltype(v)::iterator it = std::prev(v.end(), 2); // イテレータを2回逆に進める
    std::cout << *it << std::endl;
  }
}//5
```