#include<iostream>
#include<set>
using namespace std;
int main() {
set<int>st;//ローカル変数として、stを生成
return 0;
}
set<int> st{3,1,4,1};
setは重複を許さない順序付き集合なので、上記のように重複データがある場合は、重複データは自動的に削除され、｛１，３，４｝だけが格納される。
set<int> org{3,1,4};
set<int> x(org);
上記のコードはorgをコピーするので、{1,3,4}という値をもつ動的配列xを生成する。
#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回インクリメントする
auto itr = st.begin();
for(int i = 0;i < 5; ++i)
++itr;
とすると、6が出力される。
全ての要素を表示するときは、お決まりの書き方。
#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;
}
これで全部表示される。
こんな書き方もあるみたい
#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を利用する。
set<int>st{3,1,4};
st.insert(2);//値２を追加
データの削除
eraseを利用する
erase（値）が格納されていれば、それを削除する。リターン値として、削除したデータの個数(0 or 1)を返す。
set<int>st{3,1,4};
auto c = st.erase(3);//３を削除、１が返ってくる
偶数を全て削除したい例
#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
#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
#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
#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
while (it != se.end() && *it < R[i]) {
res += T[i];
auto it2 = it;
++it2;
se.erase(it);
it = it2;
}
これなら大丈夫だけど
it2つくらないでそのままitでやるとバグる
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}
これが原因？だと思う
対処方法
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について
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