STL Container - Associate Container
Associate Container(์ฐ๊ด ์ปจํ ์ด๋)๋ ํค์ ๊ฐ์ฒ๋ผ ๊ด๋ จ์๋ ๋ฐ์ดํฐ๋ฅผ ํ๋์ ์์ผ๋ก ์ ์ฅํ๋ ์ปจํ ์ด๋์ด๋ค. ํค์ ๊ฐ์ ์ด์ฉํ์ฌ ์์๋ค์ ๋ํด ๋น ๋ฅธ ์ ๊ทผ์ด ๊ฐ๋ฅํ๋ค. ํ์ง๋ง ์ฝ์ ๋๋ ์์์ ์์น๋ฅผ ์ง์ ํ ์ ์๋ค.
๋ณดํต balanced binary search tree๋ hash table์ ์ด์ฉํ์ฌ ๊ตฌํํ๋ค.
set & multiset
์งํฉ(set)์ ์ ์ฅํ๋ ๋ฐ์ดํฐ ๊ทธ ์์ฒด๋ฅผ ํค๋ก ์ฌ์ฉํ๋ ๊ฐ์ฅ ๋จ์ํ ์ฐ๊ด ์ปจํ ์ด๋์ด๋ค. set์ ๋ฌ๋ฆฌ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ์์น์ ์์๋ฅผ ์ฝ์ ํ๋ฏ๋ก ๊ฒ์์๋๊ฐ ๋งค์ฐ ๋น ๋ฅด๋ค.
์งํฉ์์ ํค๋ ์ ์ผํด์ผํ๋ฏ๋ก, ํค์ ์ค๋ณต์ ํ์ฉํ์ง ์๋๋ค.
๋ฉํฐ์งํฉ(multiset)์ ํค์ ์ค๋ณต์ ํ์ฉํ๋ฉฐ, ๊ฐ์ ๊ฐ์ ์ฌ๋ฌ๋ฒ ์ ์ฅํ ์ ์๋ค.
#include <set>
๊ตฌ์กฐ
set<T> ๊ฐ์ฒด๋ช
;
multiset<T> ๊ฐ์ฒด๋ช
;
set<int> st;
multiset<int> ms;
์์ฑ์
์์ฑ์
์ค๋ช
set s
s๋ ๋น ์ปจํ ์ด๋
set s(pred)
s๋ ๋น ์ปจํ ์ด๋๋ก ์ ๋ ฌ ๊ธฐ์ค์ pred ์กฐ๊ฑด์๋ฅผ ์ฌ์ฉ
set s(s2)
s๋ s2 ์ปจํ ์ด๋์ ๋ณต์ฌ๋ณธ์ด๋ค.(๋ณต์ฌ ์์ฑ์ ํธ์ถ)
set s(b,e)
s๋ ๋ฐ๋ณต์ ๊ตฌ๊ฐ [b,e)๋ก ์ด๊ธฐํ๋ ์์๋ฅผ ๊ฐ๋๋ค.
set s(b,e,pred)
s๋ ๋ฐ๋ณต์ ๊ตฌ๊ฐ [b,e)๋ก ์ด๊ธฐํ๋ ์์๋ฅผ ๊ฐ๋๋ค. ์ ๋ ฌ๊ธฐ์ค์ pred ์กฐ๊ฑด์๋ฅผ ์ด์ฉํ๋ค.
๋ฉค๋ฒํจ์
ํจ์
์ค๋ช
s.clear()
s์ ๋ชจ๋ ์์๋ฅผ ์ ๊ฑฐ
n=s.count(k)
์์ k์ ๊ฐ์๋ฅผ ๋ฐํํ๋ค.
s.empty()
v๊ฐ ๋น์๋์ง ์กฐ์ฌ
p=s.begin()
p๋ s์ ์ฒซ ์์๋ฅผ ๊ฐ๋ฆฌํจ๋ค.
p=s.end()
p๋ s์ ๋์ ํ์ํ๋ ๋ฐ๋ณต์
pr=s.equeal_range(k)
pr๋ ์์ k์ ๋ฐ๋ณต์ ๊ตฌ๊ฐ์ธ pair ๊ฐ์ฒด
q=s.erase(p)
p๊ฐ ๊ฐ๋ฆฌํค๋ ์์๋ฅผ ์ ๊ฑฐํ๋ค. q๋ ๋ค์ ์์๋ฅผ ๊ฐ๋ฆฌํจ๋ค.
q=s.erase(b,e)
๋ฐ๋ณต์ ๊ตฌ๊ฐ [b,e)์ ๋ชจ๋ ์์๋ฅผ ์ ๊ฑฐํ๋ค. q๋ ๋ค์ ์์๋ฅผ ๊ฐ๋ฆฌํจ๋ค.
p=s.find(k)
p๋ k์์์ ์์น๋ฅผ ๊ฐ๋ฆฌํค๋ ๋ฐ๋ณต์์ด๋ค.
pr=s.insert(k)
s ์ปจํ ์ด๋์ k๋ฅผ ์ฝ์ ํ๋ค. pr์ ์ฝ์ ํ ์์๋ฅผ ๊ฐ๋ฆฌํค๋ ๋ฐ๋ณต์์ ์ฑ๊ณต ์ฌ๋ถ์ bool์ธ pair ๊ฐ์ฒด์ด๋ค.
q=s.insert(p,x)
p๊ฐ ๊ฐ๋ฆฌํค๋ ์์น์ k๊ฐ์ ์ฝ์ ํ๋ค. q๋ ์ฝ์ ํ ์์๋ฅผ ๊ฐ๋ฆฌํค๋ ๋ฐ๋ณต์๋ค.
s.insert(b,e)
๋ฐ๋ณต์ ๊ตฌ๊ฐ [b,e)์ ์์๋ฅผ ์ฝ์ ํ๋ค.
pred = s.key_comp()
pred๋ s์ key ์ ๋ ฌ๊ธฐ์ค์ธ ์กฐ๊ฑด์์ด๋ค.(key_compare ํ์ )
pred = s.value_comp()
pred๋ s์ value ์ ๋ ฌ๊ธฐ์ค์ธ ์กฐ๊ฑด์์ด๋ค.(value_compare ํ์ )
p = s.lower_bound(k)
p๋ k์ ์์๊ตฌ๊ฐ์ ๊ฐ๋ฆฌํค๋ ๋ฐ๋ณต์์ด๋ค.
p = s.upper_bound(k)
p๋ k์ ๋ ๊ตฌ๊ฐ์ ๊ฐ๋ฆฌํค๋ ๋ฐ๋ณต์์ด๋ค.
x=s.max_size()
x๋ s๊ฐ ๋ด์ ์ ์๋ ์ต๋ ์์์ ๊ฐ์(๋ฉ๋ชจ๋ฆฌ์ ํฌ๊ธฐ)
p=s.rbegin()
p๋ s์ ์ญ ์์ฐจ์ด์ ์ฒซ ์์๋ฅผ ๊ฐ๋ฆฌํค๋ ๋ฐ๋ณต์๋ค.
p=s.rend()
p๋ s์ ์ญ ์์ฐจ์ด์ ๋์ ํ์ํ๋ ๋ฐ๋ณต์
s.size()
s์ ์์ ๊ฐฏ์
s.swap(s2)
s์ s2๋ฅผ swapํ๋ค.
์ฐ๊ด ์ปจํ
์ด๋๋ ์ ๋ ฌ ๊ธฐ์ค์ด ์์ผ๋ฏ๋ก insert()
์ ์ํด ์ฝ์
๋ ์์๋ ์๋ ์ ๋ ฌ๋๋ค. set์์ ์์๋ฅผ key๋ผ ํ๋ฉฐ, ์ด ํค๋ฅผ ๋น๊ตํ์ฌ ๋ด๋ถ ์์๋ฅผ ์ ๋ ฌํ๋ค.
์์
set
#include <iostream>
#include <set>
using namespace std;
int main(void){
set<int> s;
pair<set<int>::iterator, bool> pr;
pr = s.insert(50);
if( pr.second == true ){
cout << *pr.first << " ์ฝ์
์ฑ๊ณต" << endl;
}else{
cout << *pr.first << " ์ฝ์
์คํจ" << endl;
}
s.insert(40);
s.insert(80);
set<int>::iterator iter;
// insert๋ก ์ฝ์
ํด ์ ๋ ฌ๋ ๊ฒ์ ํ์ธํ ์ ์๋ค.
for(iter=s.begin();iter!=s.end();++iter){
cout << *iter << ' ';
}
cout << endl;
pr = s.insert(50);
if( pr.second == true ){
cout << *pr.first << " ์ฝ์
์ฑ๊ณต" << endl;
}else{
cout << *pr.first << " ์ฝ์
์คํจ" << endl;
}
copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
cout << endl;
// 50์์น์ 60์ฝ์
s.insert(pr.first, 60);
copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
cout << endl;
// ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ
set<int, greater<int> > s2;
s2.insert(50);
s2.insert(30);
s2.insert(80);
s2.insert(10);
for(iter=s2.begin();iter!=s2.end();++iter){
cout << *iter << ' ';
}
cout << endl;
// key_compare(), value_compare()
cout << "key_compare less : " << typeid(s.key_comp()).name() << endl;
cout << "key_compare greater : " << typeid(s2.key_comp()).name() << endl;
cout << "value_compare less : " << typeid(s.value_comp()).name() << endl;
cout << "value_compare greater : " << typeid(s2.value_comp()).name() << endl;
}
multiset
#include <iostream>
#include <set>
using namespace std;
int main(void){
multiset<int> ms;
ms.insert(50);
ms.insert(30);
ms.insert(40);
ms.insert(30);
ms.insert(80);
ms.insert(50);
ms.insert(30);
ms.insert(50);
ms.insert(10);
multiset<int>::iterator iter;
for(iter=ms.begin(); iter!=ms.end(); ++iter){
cout << *iter << " ";
}
cout << endl;
cout << "30 count : " << ms.count(30) << endl;
// ์์ 30์ ์ฒซ๋ฒ์งธ ์์น
multiset<int>::iterator lower_iter;
lower_iter = ms.lower_bound(50);
// ์์ 30์ ๋ง์ง๋ง ์์น ๋ค์ ์์น
multiset<int>::iterator upper_iter;
upper_iter = ms.upper_bound(50);
cout << "lower iter : " << *lower_iter << ", upper_iter : " << *upper_iter << endl;
pair<multiset<int>::iterator, multiset<int>::iterator> iter_pair;
iter_pair = ms.equal_range(30);
for(iter = iter_pair.first; iter != iter_pair.second; ++iter){
cout << *iter << ' ';
}
cout << endl;
// ํด๋น ์์ ์ ์ฒด ์ญ์
ms.erase(50);
copy(ms.begin(), ms.end(), ostream_iterator<int>(cout, " "));
}
map & multimap
map์ ํค์ ๊ฐ์ ์์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ๊ด๋ฆฌํ๋ ์ปจํ ์ด๋์ด๋ค. ์งํฉ ์ปจํ ์ด๋์ ๋ง์ฐฌ๊ฐ์ง๋ก ์ ๋ ฌ๋ ์์น์ ์์๋ฅผ ์ฝ์ ํ๋ฏ๋ก ๊ฒ์ ์๋๊ฐ ๋งค์ฐ ๋น ๋ฅด๋ค.
map์์ ํค๋ ์ ์ผํด์ผํ๋ฏ๋ก, ํ๋์ ํค์ ํ๋์ ๊ฐ๋ง์ด ์ฐ๊ฒฐ๋ ์ ์๋ค. multimap์ ๊ฐ์ ์ค๋ณต์ ํ์ฉํ๋ฏ๋ก, ํ๋์ ํค์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ๊ณผ ์ฐ๊ฒฐ๋ ์ ์๋ค.
#include <map>
๊ตฌ์กฐ
map<T> ๊ฐ์ฒด๋ช
;
multimap<T> ๊ฐ์ฒด๋ช
;
์์
map์ set๊ณผ ๊ฐ์ ์ธํฐํ์ด์ค ๋ฉค๋ฒ ํจ์๋ฅผ ์ ๊ณตํ๋ฉฐ, ํ ํ๋ฆฟ ํ์๊ณผ ๋ด์ฅ ๋ฉค๋ฒ ํ์๋ง์ด ์ฝ๊ฐ ์ฐจ์ด๋ฅผ ๋ณด์ธ๋ค.
map์
[]
์ฐ์ฐ์๋ฅผ ์ ๊ณตํ์ฌ key์ ํด๋นํ๋ ์์์ value์ ์ฝ๊ฒ ์ ๊ทผํ๊ฑฐ๋ ๋ณ๊ฒฝํ ์ ์๋ค.map
#include <iostream>
#include <map>
using namespace std;
int main(void){
map<string, int> m;
m.insert(pair<string,int>("์ํ",100));
m.insert(pair<string,int>("๊ตญ์ด",80));
pair<string,int> p("์์ด",50);
m.insert(p);
map<string, int>::iterator iter;
for(iter = m.begin(); iter != m.end(); ++iter){
cout << (*iter).first << " : " << (*iter).second << endl;
}
m["์์ด"] = 90;
for(iter = m.begin(); iter != m.end(); ++iter){
cout << iter->first << " : " << iter->second << endl;
}
pair<map<string,int>::iterator, bool> pr;
pr = m.insert(pair<string, int>("๊ณผํ", 60));
if(pr.second){
cout << pr.first->first << " : " << pr.first->second << endl;
}
return 0;
}
multimap
#include <iostream>
#include <map>
using namespace std;
int main(void){
multimap<string, int> mm;
mm.insert(pair<string, int>("๊ตญ์ด", 30));
mm.insert(pair<string, int>("์ํ", 100));
mm.insert(pair<string, int>("์ํ", 90));
mm.insert(pair<string, int>("๊ตญ์ด", 60));
multimap<string, int>::iterator iter;
for(iter=mm.begin(); iter!=mm.end(); ++iter){
cout << iter->first << " : " << iter->second << endl;
}
cout << endl;
cout << "count('๊ตญ์ด') : "<< mm.count("๊ตญ์ด") << endl;
mm.insert(pair<string, int>("์์ด", 60));
mm.insert(pair<string, int>("๊ณผํ", 80));
map<string, int>::iterator lower_iter;
map<string, int>::iterator upper_iter;
lower_iter = mm.lower_bound("์ํ");
// upper๋ ๊ฐ์ฅ ํฐ ์ํ ๋ค์!
upper_iter = mm.upper_bound("์ํ");
cout << "lower " << lower_iter->first << " : " << lower_iter->second << endl;
cout << "upper " << upper_iter->first << " : " << upper_iter->second << endl;
pair<map<string, int>::iterator, map<string,int>::iterator> iter_pair;
iter_pair = mm.equal_range("์ํ");
for(iter=iter_pair.first; iter!=iter_pair.second;++iter){
cout << iter->first << " : " << iter->second << endl;
}
return 0;
}
unordered associate container
์์๊ฐ ์ง์ ๋์ง ์์ ์ฐ๊ด ์ปจํ ์ด๋๋ ์์๊ฐ ์ง์ ๋ ๊ธฐ์กด ์ฐ๊ด ์ปจํ ์ด๋์ ๊ฐ์ ๋์์ ํ๋ค. ๊ธฐ์กด์ ์ฐ๊ด ์ปจํ ์ด๋๋ tree ๊ตฌ์กฐ๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ๋์ํ์ง๋ง, ์ด ์ปจํ ์ด๋๋ hash table์ ๊ธฐ๋ฐ์ผ๋ก ๋์ํ๋ค.
๋ฐ๋ผ์, ์์์ ์ถ๊ฐ, ์ญ์ ์๋๊ฐ ๋นจ๋ผ์ก์ผ๋ฉฐ, ๋ค์ํ ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ ์ ์๊ฒ ๋์๋ค. ์์๊ฐ ์ง์ ๋ ์ฐ๊ด ์ปจํ ์ด๋๋ ์๋ฐฉํฅ ๋ฐ๋ณต์๋ฅผ ์ง์ํ์ง๋ง, ์ด ์ปจํ ์ด๋๋ ์๋ฐํฅ ๋ฐ๋ณต์๋ง์ ์ง์ํ๋ค.
unordered_set
unordered_multiset
unordered_map
unordered_multimap
์ฐธ์กฐ
Last updated
Was this helpful?