1.set
集合具有共同特征的事物,可以是由两个迭代器定义的范围内的一系列对象,也可以是一种有特殊特征的容器类型。
set<T> 容器内部元素的组织方式和 map<K,T> 相同,都是平衡二叉树
std::set<int> numbers {8, 7, 6, 5, 4, 3, 2, 1};
默认的比较函数是 less<int>,因此容器中的元素会升序排列。
打印:
std::copy( std::begin(numbers), std::end(numbers),
std:: ostream_iterator<int>{std::cout," "});
输出一个从 1 至 8 的整数递增序列
std::set<std::string, std::greater<string>> words {"one", "two", "three", "four", "five", "six", "seven" , "eight"};
这个容器中的元素会降序排列。
用元素段来创建 set 容器,并且可以指定它的比较函数:
std::set<string> words2 {std::begin(words), std::end(words)};std::set<string, std::greater<string>> words3 {++std::begin(words2), std::end(words2)};
std::set<string, std::greater<string>> words {"one", "two", "three"};
auto pr1 = words.insert("four");
auto pr2 = words.insert ("two") ;
auto iter3 = words.insert(pr.first, "seven");
words.insert ({ "five","six"}) ;
string wrds[] {"eight", "nine", "ten"};
words.insert(std::begin(wrds) , std::end(wrds));
插入单个元素会返回一个 pair<iterator,bool> 对象。
插入单个元素和一个标识,会返回一个迭代器。
插入一段元素或一个初始化列表就不会有返回值。
std::set<std::pair<string,string>> names;auto pr = names.emplace("Lisa", "Carr");auto iter = names.emplace_hint(pr.first, "Joe", "King");
成员函数 emplace() 会返回一个 pair<iterator,bool> 对象
emplace_hint() 只返回一个迭代器。emplace_hint() 的第一个参数是一个迭代器,它指出了元素可能的插入位置,随后的参数会被传入元素的构造函数。
删除
clear() 删除 set 的所有元素。
erase() 删除迭代器指定位置的元素或与对象匹配的元素。
std::set<int> numbers {2, 4, 6, 8, 10, 12, 14};
auto iter = numbers.erase(++std::begin(numbers));
auto n = numbers.erase(12);n = numbers.erase(13);numbers.clear();
erase() 删除一段元素:
std::set<int> numbers {2, 4, 6, 8, 10, 12, 14};
auto iter1 = std::begin(numbers); // iter1 points to 1st element
advance(iterl, 5); // Points to 6th element-12
auto iter = numbers.erase(++std:rbegin(numbers), iter1);// Remove 2nd to 5th inclusive. iter points to 12
访问
set 的成员函数 find() 会返回一个和参数匹配的元素的迭代器。
如果对象不在 set 中,会返回一个结束迭代器。
std::set<string> words {"one", "two","three", "four","five"};
auto iter = words.find ("one") ; // iter points to "one"
iter = words.find(string{"two"}); // iter points to "two"
iter = words.find ("six"); // iter is std:: end (words)
调用成员函数 count() 可以返回指定键所对应的元素个数,返回值通常是 0 或 1,因为 set 容器中的元素是唯一的。
合并
#include <set>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
//初始化
std::set<int> numbers{8, 7, 6, 5, 4, 3, 2, 1};
std::copy( std::begin(numbers), std::end(numbers), std::ostream_iterator<int>{std::cout," "});
cout<<endl;
std::set<std::string, std::greater<string>> words{"one", "two", "three", "four",
"five", "six", "seven" , "eight"};
std::copy( std::begin(words), std::end(words), std::ostream_iterator<string>{std::cout," "});
cout<<endl;
std::set<string> words2 {std::begin(words), std::end(words)};
std::set<string, std::greater<string>> words3{++std::begin(words2), std::end(words2)};
std::copy( std::begin(words3), std::end(words3), std::ostream_iterator<string>{std::cout," "});
cout<<endl;
//添加,删除和访问
std::set<string, std::greater<string>> _words{"one", "two", "three"};
auto pr1 = _words.insert("four");
//不允许有重复元素插入
auto pr2 = _words.insert ("two") ;
auto pr3 = _words.insert(pr2.first, "seven");
if(pr2.second) //插入成功则输出被插入元素
cout << *pr2.first << " inserted" << endl; //输出: 5 inserte
else
cout << *pr2.first << " already exists" << endl;
_words.insert ({ "five","six"}) ;
string wrds[] {"eight", "nine", "ten"};
_words.insert(std::begin(wrds) , std::end(wrds));
std::copy( std::begin(_words), std::end(_words), std::ostream_iterator<string>{std::cout," "});
cout<<endl;
//?????
std::set<std::pair<string,string>> names;
auto pr = names.emplace("Lisa", "Carr");
auto iter = names.emplace_hint(pr.first, "Joe", "King");
cout<<pr.second<<endl;
auto count=names.size();
cout<<count<<endl;
//删除
std::set<int> _numbers{2, 4, 6, 8, 10, 12, 14};
auto _iter = _numbers.erase(++std::begin(_numbers));
auto n = _numbers.erase(12);
//循环遍历
set<int>::iterator starti = _numbers.begin();
set<int>::iterator endi = _numbers.end();
for (;starti != endi;starti++)
printf("%d\n",*starti);
n = _numbers.erase(13);
_numbers.clear();
std::set<int> numbers1{2, 4, 6, 8, 10, 12, 14};
auto iter1 = std::begin(numbers1); // iter1 points to 1st element
advance(iter1, 5); // Points to 6th element-12
auto iter2 = numbers1.erase(++std::begin(numbers1), iter1);// Remove 2nd to 5th inclusive. iter points to 12
//查找
std::set<string> words1{"one", "two","three", "four","five"};
auto iter4 = words1.find("one") ; // iter points to "one"
iter4 = words1.find(string{"two"}); // iter points to "two"
iter4 = words1.find ("six"); // iter is std:: end (words)
return 0;
}
结果显示:
set的入门题:原文链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1412
Problem Description
给你两个集合,要求{A} + {B}.
注:同一个集合中不会有两个相同的元素.
Input
每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.
Output
针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开.
Sample Input
1 2
1
2 3
1 2
1
1 2
Sample Output
1 2 3
1 2
AC代码:
#include<iostream>
#include<set>
using namespace std;
int main()
{
int n,m,x;
set<int>s;
set<int>::iterator it;
while (cin>>n>>m){
s.clear();
for (int i=0;i<n+m;i++){
cin>>x;
s.insert(x);
}
it=s.begin();
int cnt=s.size();
for (int i=1;i<=cnt;i++){
if (i==1)
cout<<*it;
else
cout<<" "<<*it;
it++;
}
cout<<endl;
}
return 0;
}
multiset<T> 容器就像 set<T> 容器,但它可以保存重复的元素。这意味我们总可以插入元素,当然必须是可接受的元素类型。默认用 less<T> 来比较元素,但也可以指定不同的比较函数。在元素等价时,它必须返回 false。
std::multiset<string, std::greater<string>> words{{"dog", "cat", "mouse"}, std::greater<string>()};
set 容器中的成员函数表现不同的是:
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm> // For replace_if() & for_each()
#include <set> // For map container
#include <iterator> // For advance()
#include <cctype> // For isalpha()
using std::string;
int main()
{
std::cout << "Enter some text and enter * to end:\n";
string text_in {};
std::getline(std::cin, text_in, '*');
//空格代替无字符
std::replace_if(std::begin(text_in), std::end(text_in),
[](const char& ch){ return !isalpha(ch); }, ' ');
std::istringstream text(text_in);
std::istream_iterator<string> begin(text);
std::istream_iterator<string> end;
std::multiset<string> words;
size_t max_len {};
// 把获得单词存储到容器中,并找到最大长度
std::for_each(begin, end, [&max_len, &words](const string& word){
words.emplace(word);
max_len = std::max(max_len, word.length());
});
size_t per_line {4},
count {};
//每次循环迭代结束后,iter 被设为 upper_bound() 返回的值,它指向一个不同于当前元素的元素
//如果不存在这样的元素,upper_bound() 会返回容器的结束迭代器,循环就此结束。
for(auto iter = std::begin(words); iter != std::end(words); iter = words.upper_bound(*iter))
{
//容器中的元素是有序的,因而相等的元素位置是连续的。
//通过调用容器的成员函数 count(),可以获取和它的参数 iter 所指向元素相等的元素的个数。
std::cout << std::left << std::setw(max_len + 1) << *iter<< std::setw(3)
<< std::right << words.count(*iter) << " ";
if(++count % per_line == 0)
std::cout << std::endl;
}
std::cout << std::endl;
}
结果显示: