STL之关联式容器(set和multiset)

用户9831583

发布于 2022-06-16 14:44:00

4190

发布于 2022-06-16 14:44:00

文章被收录于专栏：码出名企路

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;
}

2.multiset

multiset<T> 容器就像 set<T> 容器，但它可以保存重复的元素。这意味我们总可以插入元素，当然必须是可接受的元素类型。默认用 less<T> 来比较元素，但也可以指定不同的比较函数。在元素等价时，它必须返回 false。

std::multiset<string, std::greater<string>> words{{"dog", "cat", "mouse"}, std::greater<string>()};

set 容器中的成员函数表现不同的是：

insert() 总是可以成功执行。当插入单个元素时，返回的迭代器指向插入的元素。当插入一段元素时，返回的迭代器指向插入的最后一个元素。
emplace() 和 emplace_hint() 总是成功。它们都指向创建的新元素。
find() 会返回和参数匹配的第一个元素的迭代器，如果都不匹配，则返回容器的结束迭代器。
equal_range() 返回一个包含迭代器的 pair 对象，它定义了一个和参数匹配的元素段。如果没有元素匹配的话，pair 的第一个成员是容器的结束迭代器；在这种情况下，第二个成员是比参数大的第一个元素，如果都没有的话，它也是容器的结束迭代器。
lower_bound() 返回和参数匹配的第一个元素的迭代器，如果没有匹配的元素，会返回容器的结束迭代器。返回的迭代器和 range() 返回的 pair 的第一个成员相同。
upper_bound() 返回的迭代器和 equal_range() 返回的 pair 的第二个成员相同。
count() 返回和参数匹配的元素的个数。

  #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;
    }

结果显示：