[系统运维]c++ 11标准模板（STL） std::set(三）

迭代器

1、返回指向容器第一个元素的迭代器

std::set<Key,Compare,Allocator>::begin,
std::set<Key,Compare,Allocator>::cbegin

iterator begin();                              (C++11 前) 
iterator begin() noexcept;                     (C++11 起) 
const_iterator begin() const;                  (C++11 前) 
const_iterator begin() const noexcept;         (C++11 起) 
const_iterator cbegin() const noexcept;        (C++11 起) 

返回指向容器首元素的迭代器。

若容器为空，则返回的迭代器将等于 end() 。

参数????????（无）

返回值????????指向首元素的迭代器。

复杂度????????常数。

注意

因为 iterator 和 const_iterator 都是常迭代器（而且实际上可以是同一类型），故不可能通过任何这些成员函数返回的迭代器修改容器元素。

?返回指向容器尾端的迭代器

std::set<Key,Compare,Allocator>::end, 
std::set<Key,Compare,Allocator>::cend

iterator end();                                             (C++11 前) 
iterator end() noexcept;                                    (C++11 起) 
const_iterator end() const;                                 (C++11 前) 
const_iterator end() const noexcept;                        (C++11 起) 
const_iterator cend() const noexcept;                       (C++11 起) 

返回指向容器末元素后一元素的迭代器。

此元素表现为占位符；试图访问它导致未定义行为。

参数? ? ? ? ? ? ? ? ? ? ? ? ?（无）

返回值????????????????????????指向后随最后元素的迭代器。

复杂度????????????????????????常数。

注意

因为 iterator 和 const_iterator 都是常迭代器（而且实际上可以是同一类型），故不可能通过任何这些成员函数返回的迭代器修改容器元素。

返回指向容器最后元素的逆向迭代器

std::set<Key,Compare,Allocator>::rbegin, 
std::set<Key,Compare,Allocator>::crbegin

reverse_iterator rbegin();                             (C++11 前) 
reverse_iterator rbegin() noexcept;                    (C++11 起) 
const_reverse_iterator rbegin() const;                 (C++11 前) 
const_reverse_iterator rbegin() const noexcept;        (C++11 起) 
const_reverse_iterator crbegin() const noexcept;       (C++11 起) 

返回指向逆向容器首元素的逆向迭代器。它对应非逆向容器的末元素。

?

参数????????????????????????（无）

返回值????????????????????????指向首元素的逆向迭代器。

复杂度????????????????????????常数。

注意

因为 iterator 和 const_iterator 都是常迭代器（而且实际上可以是同一类型），故不可能通过任何这些成员函数返回的迭代器修改容器元素。

返回指向前端的逆向迭代器

std::set<Key,Compare,Allocator>::rend, 
std::set<Key,Compare,Allocator>::crend

reverse_iterator rend();                                (C++11 前) 
reverse_iterator rend() noexcept;                       (C++11 起) 
const_reverse_iterator rend() const;                    (C++11 前) 
const_reverse_iterator rend() const noexcept;           (C++11 起) 
const_reverse_iterator crend() const noexcept;          (C++11 起) 

返回指向逆向容器末元素后一元素的逆向迭代器。它对应非逆向容器首元素的前一元素。此元素表现为占位符，试图访问它导致未定义行为。

参数????????????????????????（无）

返回值????????????????????????指向末元素后一元素的逆向迭代器。

复杂度????????????????????????常数。

注意

因为 iterator 和 const_iterator 都是常迭代器（而且实际上可以是同一类型），故不可能通过任何这些成员函数返回的迭代器修改容器元素

示例

    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::cout << "const_iterator:   ";
    for (std::set<char>::const_iterator it = set1.cbegin(); it != set1.cend(); it++)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    std::cout << "const_reverse_iterator:   ";
    for (std::set<char>::const_reverse_iterator it = set1.crbegin(); it != set1.crend(); it ++)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    std::cout << "begin():   " << std::hex << (int)&*set1.begin() << std::endl;
    std::cout << "cbegin():  " << std::hex << (int)&*set1.cbegin() << std::endl;
    std::cout << "end():     " << std::hex << (int)&*set1.end() << std::endl;
    std::cout << "cend():    " << std::hex << (int)&*set1.cend() << std::endl;
    std::cout << "rbegin():  " << std::hex << (int)&*set1.rbegin() << std::endl;
    std::cout << "crbegin(): " << std::hex << (int)&*set1.crbegin() << std::endl;
    std::cout << "rend():    " << std::hex << (int)&*set1.rend() << std::endl;
    std::cout << "crend():   " << std::hex << (int)&*set1.crend() << std::endl;

?查找

返回匹配特定键的元素数量

std::set<Key,Compare,Allocator>::count

size_type count( const Key& key ) const;        (1)  

template< class K > size_type count( const K& x ) const;        (2) (C++14 起) 

返回拥有关键比较等价于指定参数的元素数，因为此容器不允许重复故为 1 或 0。

1) 返回拥有关键 key 的元素数。

2) 返回拥有关键比较等价于值 x 的元素数。此重载仅若有限定 id Compare::is_transparent 合法且指代一个类型才参与重载决议。这允许调用此函数而不构造 Key 的实例。

参数

返回值

拥有比较等价于 key 或 x 的关键的元素数，对于 (1) 为 1 或 0。

复杂度

与容器大小成对数。

示例

    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::cout << "count A: " << set1.count('A') << std::endl;
    std::cout << "count F: " << set1.count('F') << std::endl;

?寻找带有特定键的元素

std::set<Key,Compare,Allocator>::find

iterator find( const Key& key );                 (1)  

const_iterator find( const Key& key ) const;     (2)  

template< class K > iterator find( const K& x ); (3) (C++14 起) 

template< class K > const_iterator find( const K& x ) const; (4) (C++14 起) 

1,2) 寻找键等于 key 的的元素。

3,4) 寻找键比较等价于值 x 的元素。此重载仅若若有限定 id Compare::is_transparent 合法并且指代类型才参与重载决议。允许调用此函数而无需构造 Key 的实例。

参数

返回值

指向键等于 key 的元素的迭代器。若找不到这种元素，则返回尾后（见 end() ）迭代器。

复杂度

与容器大小成对数。

示例

    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::cout << "find A: " << (set1.find('A') != set1.end() ? "true" : "false") << std::endl;
    std::cout << "find F: " << (set1.find('F') != set1.end() ? "true" : "false") << std::endl;

返回匹配特定键的元素范围

std::set<Key,Compare,Allocator>::equal_range

std::pair<iterator,iterator> equal_range( const Key& key ); (1)  

std::pair<const_iterator,const_iterator> equal_range( const Key& key ) const;(2)  

template< class K >std::pair<iterator,iterator> equal_range( const K& x ); (3) (C++14 起) 

template< class K >std::pair<const_iterator,const_iterator> equal_range( const K& x ) const; (4) (C++14 起) 

返回容器中所有拥有给定关键的元素范围。范围以二个迭代器定义，一个指向首个不小于 key 的元素，另一个指向首个大于 key 的元素。首个迭代器可以换用 lower_bound() 获得，而第二迭代器可换用 upper_bound() 获得。

1,2) 比较关键与 key 。

3,4) 比较关键与值 x 。此重载仅若有限定 id Compare::is_transparent 合法且指代一个类型才参与重载决议。它们允许调用此函数而不构造 Key 的实例。

参数

返回值

含一对定义所需范围的迭代器的 std::pair ：第一个指向首个不小于 key 的元素，第二个指向首个大于 key 的元素。

若无元素不小于 key ，则将尾后（见 end() ）迭代器作为第一元素返回。类似地，若无元素大于 key ，则将尾后迭代器作为第二元素返回。

复杂度

与容器大小成对数。

示例

    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::pair<std::set<char>::iterator, std::set<char>::iterator> range = set1.equal_range('C');
    std::cout << "range.first:  " << *range.first << std::endl;
    std::cout << "range.second: " << *range.second << std::endl;

返回指向首个不小于给定键的元素的迭代器

std::set<Key,Compare,Allocator>::lower_bound

iterator lower_bound( const Key& key );            (1)  

const_iterator lower_bound( const Key& key ) const;(1)  

template< class K >iterator lower_bound(const K& x);(2) (C++14 起) 

template< class K >const_iterator lower_bound(const K& x) const;(2) (C++14 起) 

1) 返回指向首个不小于 key 的元素的迭代器。

2) 返回指向首个比较不小于值 x 的元素的迭代器。此重载仅若有限定 id Compare::is_transparent 合法并指代一个类型才参与重载决议。它们允许调用此函数而无需构造 Key 的实例。

参数

返回值

指向首个不小于 key 的元素的迭代器。若找不到这种元素，则返回尾后迭代器（见 end() ）。

复杂度

与容器大小成对数。

返回指向首个大于给定键的元素的迭代器

std::set<Key,Compare,Allocator>::upper_bound

iterator upper_bound( const Key& key );            (1)  

const_iterator upper_bound( const Key& key ) const; (1)  

template< class K >iterator upper_bound( const K& x );(2) (C++14 起) 

template< class K >const_iterator upper_bound( const K& x ) const;(2) (C++14 起) 

1) 返回指向首个大于 key 的元素的迭代器。

2) 返回指向首个比较大于值 x 的元素的迭代器。此重载仅若有限定 id Compare::is_transparent 合法并指代一个类型才参与重载决议。这允许调用此函数而无需构造 Key 的实例。

参数

返回值

指向首个大于 key 的元素的迭代器。若找不到这种元素，则返回尾后（见 end() ）迭代器。

复杂度

与容器大小成对数。

示例

    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::set<char>::iterator itLower = set1.lower_bound('C');
    std::cout << "lower_bound('C') : " << *itLower << std::endl;
    std::set<char>::iterator itUpper = set1.upper_bound('C');
    std::cout << "upper_bound('C') : " << *itUpper << std::endl;

代码汇总

#include <set>
#include <iostream>
#include <ios>
#include <string>
#include <vector>
#include <algorithm>
#include <typeinfo>

// 打印容器元素
template <typename T, typename _Compare = std::less<T>>
void printSet(const std::string &name, const std::set<T, _Compare> &setP)
{
    std::cout << name << " :    ";
    for (auto s : setP)
    {
        std::cout << s << ' ';
    }

    std::cout << std::endl;
}

// 自定义比较
struct myGreaterCompare
{
    myGreaterCompare() {}
    template < typename T>
    bool operator()(const T &a, const T &b)const
    {
        return a > b;
    }
};

void constructor()
{
    std::cout << "constructor start " << std::endl;
    // c++11 初始化容器列表语法：
    // 默认升序
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    printSet("default       ", set1);
    // 递增
    std::set<char, std::less<char>> set2{'A', 'B', 'C', 'D', 'E'};
    printSet("std::less<>   ", set2);
    // 递减
    std::set<char, std::greater<char>> set3{'A', 'B', 'C', 'D', 'E'};
    printSet("std::greater<>", set3);
    // 自定义比较函数
    std::set<char, myGreaterCompare> set4{'A', 'B', 'C', 'D', 'E'};
    printSet("myGreaterCompare", set4);

    // 拷贝构造函数, set<T> 必须同类型，包括比较
    std::set<char, std::greater<char>> set5(set3);
    printSet("copy constructor", set5);

    // 赋值构造函数， set<T> 必须同类型，包括比较
    std::set<char, std::less<char>> set6 = set2;
    printSet("assignment constructor", set6);

    // 范围构造
    std::set<char, myGreaterCompare> set7(set6.begin(), set6.end());
    printSet("range constructor", set7);
    std::cout << "constructor end " << std::endl << std::endl;
}

void capacity()
{
    std::cout << "capacity start " << std::endl;

    // 检查容器是否无元素
    std::set<char> set1;
    std::cout << "set1 is empty ? :   " << (set1.empty() ? "empty" : "no empty") << std::endl;
    set1.insert('A');
    std::cout << "set1 is empty ? :   " << (set1.empty() ? "empty" : "no empty") << std::endl;

    // 返回容器中的元素数
    std::set<char> set2;
    std::cout << "set2 size : " << set2.size() << std::endl;
    set2 = std::set<char> {'A', 'B', 'C', 'D', 'E'};
    std::cout << "set2 size : " << set2.size() << std::endl;

    // 返回根据系统或库实现限制的容器可保有的元素最大数量
    std::set<char> set3;
    std::cout << "std::set<char> max_size() : " << set3.max_size() << std::endl;
    std::set<int> set4;
    std::cout << "std::set<int> max_size() : " << set4.max_size() << std::endl;
    std::set<std::string> set5;
    std::cout << "std::set<std::string> max_size() : " << set5.max_size() << std::endl;
    std::set<double> set6;
    std::cout << "std::set<double> max_size() : " << set6.max_size() << std::endl;
    std::cout << "capacity end " << std::endl << std::endl;
}

void compareFunc()
{
    // 返回比较值的函数对象
    std::cout << "observer start " << std::endl;
    std::set<char> set1;
    std::cout << "std::set<char> key_comp() : "
              << typeid(set1.key_comp()).name() << std::endl;
    // 比较'A','B'大小，'A'比'B'小
    std::cout << "std::less<> compare('A','B') :  " <<
              (set1.key_comp()('A', 'B') ? "true" : "false") << std::endl;

    std::set<char, std::greater<char>> set2;
    std::cout << "std::set<char, std::greater<char>> key_comp() : "
              << typeid(set2.key_comp()).name() << std::endl;
    // 比较'A','B'大小，'A'比'B'大
    std::cout << "std::greater<> compare('A','B') :  " <<
              (set1.key_comp()('A', 'B') ? "true" : "false") << std::endl;

    std::set<char, myGreaterCompare> set3;
    std::cout << "std::set<char, myGreaterCompare> key_comp() : "
              << typeid(set3.key_comp()).name() << std::endl;

    std::cout << "observer end " << std::endl << std::endl;
}

void clearTest()
{
    std::cout << "clearTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::cout << "set1 size: " << set1.size() << std::endl;
    set1.clear();
    std::cout << "clear after set1 size: " << set1.size() << std::endl;
    std::cout << "clearTest end " << std::endl << std::endl;
}

void insertTest()
{
    std::cout << "insertTest start " << std::endl;
    std::set<char> set1;
    std::pair<std::set<char>::iterator, bool> it = set1.insert('A');
    std::cout << "insert 'A' " << (it.second ? "true" : "false") << std::endl;
    it = set1.insert('A');
    std::cout << "insert 'A' " << (it.second ? "true" : "false") << std::endl;

    std::set<char>::const_iterator itb = set1.cbegin();
    std::set<char>::const_iterator itp = set1.insert(itb, 'B');
    std::cout << "insert 'B' : " << *itp << std::endl;

    std::vector<char> arr{'A', 'B', 'C', 'D', 'E'};
    set1.insert(arr.begin(), arr.end());
    printSet("range insert ", set1);

    std::cout << "insertTest end " << std::endl << std::endl;
}

void emplaceTest()
{
    std::cout << "emplaceTest start " << std::endl;
    std::set<char> set1;
    char ch = 'A';
    while (ch != 'C')
    {
        set1.emplace(ch);
        ch++;
    }
    printSet("emplace", set1);

    std::set<char>::const_iterator it = set1.find('B');
    set1.emplace_hint(it, 'D');
    printSet("emplace_hint", set1);

    std::cout << "emplaceTest end " << std::endl << std::endl;
}

void eraseTest()
{
    std::cout << "eraseTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    printSet("erase before", set1);
    std::set<char>::const_iterator it = set1.find('C');
    set1.erase(it);
    printSet("erase(it)", set1);
    set1.erase(set1.find('A'), set1.find('D'));
    printSet("erase() range", set1);
    set1.erase('D');
    printSet("erase() value", set1);
    std::cout << "eraseTest end " << std::endl << std::endl;
}

void swapTest()
{
    std::cout << "swapTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C'};
    std::set<char> set2{'D', 'E'};
    std::cout << "swap() before" << std::endl;
    printSet("set1", set1);
    printSet("set2", set2);
    set1.swap(set2);
    std::cout << "swap() after" << std::endl;
    printSet("set1", set1);
    printSet("set2", set2);
    std::cout << "swapTest end " << std::endl << std::endl;
}

void iteratorTest()
{
    std::cout << "iteratorTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::cout << "const_iterator:   ";
    for (std::set<char>::const_iterator it = set1.cbegin(); it != set1.cend(); it++)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    std::cout << "const_reverse_iterator:   ";
    for (std::set<char>::const_reverse_iterator it = set1.crbegin(); it != set1.crend(); it ++)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    std::cout << "begin():   " << std::hex << (int)&*set1.begin() << std::endl;
    std::cout << "cbegin():  " << std::hex << (int)&*set1.cbegin() << std::endl;
    std::cout << "end():     " << std::hex << (int)&*set1.end() << std::endl;
    std::cout << "cend():    " << std::hex << (int)&*set1.cend() << std::endl;
    std::cout << "rbegin():  " << std::hex << (int)&*set1.rbegin() << std::endl;
    std::cout << "crbegin(): " << std::hex << (int)&*set1.crbegin() << std::endl;
    std::cout << "rend():    " << std::hex << (int)&*set1.rend() << std::endl;
    std::cout << "crend():   " << std::hex << (int)&*set1.crend() << std::endl;

    std::cout << "iteratorTest end " << std::endl << std::endl;
}


void countTest()
{
    std::cout << "countTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::cout << "count A: " << set1.count('A') << std::endl;
    std::cout << "count F: " << set1.count('F') << std::endl;
    std::cout << "countTest end " << std::endl << std::endl;
}

void findTest()
{
    std::cout << "findTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::cout << "find A: " << (set1.find('A') != set1.end() ? "true" : "false") << std::endl;
    std::cout << "find F: " << (set1.find('F') != set1.end() ? "true" : "false") << std::endl;
    std::cout << "findTest end " << std::endl << std::endl;
}

void equal_rangeTest()
{
    std::cout << "equal_rangeTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::pair<std::set<char>::iterator, std::set<char>::iterator> range = set1.equal_range('C');
    std::cout << "range.first:  " << *range.first << std::endl;
    std::cout << "range.second: " << *range.second << std::endl;
    std::cout << "equal_rangeTest end " << std::endl << std::endl;
}

void boundTest()
{
    std::cout << "boundTest start " << std::endl;
    std::set<char> set1{'A', 'B', 'C', 'D', 'E'};
    std::set<char>::iterator itLower = set1.lower_bound('C');
    std::cout << "lower_bound('C') : " << *itLower << std::endl;
    std::set<char>::iterator itUpper = set1.upper_bound('C');
    std::cout << "upper_bound('C') : " << *itUpper << std::endl;
    std::cout << "boundTest end " << std::endl << std::endl;
}

int main()
{
//    constructor();
//    capacity();
//    compareFunc();
//    clearTest();
//    insertTest();
//    emplaceTest();
//    eraseTest();
//    swapTest();
    iteratorTest();
    countTest();
    findTest();
    equal_rangeTest();
    boundTest();
    return 0;
}

?