STL关联容器概述

  1. 概念

std::set

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

STL容器大的方向分为两类,序列式容器和关联式容器,这两者通过数据在容器内的排列来区分,关联容器是通过键(key)存储和读取元素的,而顺序容器则通过元素在容器中的位置顺序存储和访问元素。标准的STL序列容器包括:vector、list、deque、heap、stack(适配器)、queue、priority_queue(适配器)。标准的STL关联式容器包括:set、multiset、map、multimap。SGI
STL还提供了一些非标准的关联式容器,eg:hash_table、hash_set。

Set

Sets are containers that store unique elements following a specific
order.

In a set, the value of an element also identifies it (the value is
itself the key, of type T), and each value must be unique. The value of
the elements in a set cannot be modified once in the container (the
elements are always const), but they can be inserted or removed from the
container.

Internally, the elements in a set are always sorted following a specific
strict weak ordering criterion indicated by its internal comparison
object (of type Compare).

澳门新葡亰手机版,set containers are generally slower than unordered set containers to
access individual elements by their key, but they allow the direct
iteration on subsets based on their order.

Sets are typically implemented as binary search trees.

2.
底层实现先了解几个概念:二叉搜索树是一种特殊的二叉树,其具有如下性质:1)
若左子树不空,则左子树所有结点的值均小于它的根结点的值2)若右子树不空,则右子树所有节点的值均大于它的根节点的值3)左右子树也分别为二叉搜索树二叉搜索树支持各种动态集合操作,包括:插入、查找、删除,其操作的时间复杂度与树的高度成正比,在遇到二叉树极端不平衡的情况下,其形状就与链表是一样的,二叉树插入、查找、删除的时间复杂度都退化为O。平衡二叉搜索树是一种特殊的二叉搜索树,其没有一个节点深度过大,不同的平衡条件,造就不同的效率表现。常见的平衡二叉搜索树有:AVL-tree和RB-tree。关联容器一般以平衡二叉搜索树作为内部数据结构,RB-tree的应用尤其广泛。RB-tree是许多平衡二叉查找树的一种,一颗有n个内结点的红黑树的高度至多为2lg(n+1),它能保证在最坏情况下,基本的动态集合操作时间为O(lgn)。

Container properties

  • Associative Elements in associative containers are referenced by
    their key and not by their absolute position in the container.
  • Ordered The elements in the container follow a strict order at
    all times. All inserted elements are given a position in this order.
  • Set The value of an element is also the key used to identify it.
  • Unique keys No two elements in the container can have equivalent
    keys.
  • Allocator-aware The container uses an allocator object to
    dynamically handle its storage needs.
  1. set / multiset3.1
    概念set不区分键值和实值,其键值就是实值。顾名思义,可以把set当做集合使用,由于set的底层是平衡二叉搜索树,因此其在插入、查询和删除时都是O(lgn)的时间复杂度。set和multiset唯一的不同是,set不允许任何两个元素有相同的值,而multiset允许键值重复。3.2
    迭代器set的迭代器本质上是const_iterator,这是因为RB-tree的结构依赖于数据的组织,如果允许通过iterator改变set元素值,会严重破坏RB-tree结构。此外,当对set进行插入和删除时,除了影响指向操作元素本身的迭代器之外,不影响指向其它元素的迭代器。3.3
    Set API(constructor) Construct set (public member function)(destructor)
    Set destructor (public member function)operator= Copy container content
    (public member function)Iterators:begin Return iterator to beginning
    (public member function)end Return iterator to end (public member
    function)rbegin Return reverse iterator to reverse beginning (public
    member function)rend Return reverse iterator to reverse end (public
    member function)Capacity:empty Test whether container is empty (public
    member function)size Return container size (public member
    function)max_size Return maximum size (public member
    function)Modifiers:insert Insert element (public member function)erase
    Erase elements (public member function)swap Swap content (public member
    function)clear Clear content (public member function)Observers:key_comp
    Return comparison object (public member function)value_comp Return
    comparison object (public member function)Operations:find Get iterator
    to element (public member function)count Count elements with a specific
    key (public member function )lower_bound Return iterator to lower bound
    (public member function)upper_bound Return iterator to upper bound
    (public member function)equal_range Get range of equal elements (public
    member function)Allocator:get_allocator Get allocator (public member
    function)3.4 set实例:

Template parameters

  • T
    Type of the elements. Each element in a set container is also
    uniquely identified by this value (each value is itself also the
    element’s key).
    Aliased as member types set::key_type and set::value_type.

  • Compare
    A binary predicate(断言) that takes two arguments of the same type
    as the elements and returns a bool. The expression comp(a,b), where
    comp is an object of this type and a and b are key values,
    shall return true if a is considered to go before b in the strict
    weak ordering the function defines.

    The set object uses this expression to determine both the order the
    elements follow in the container and whether two element keys are
    equivalent (by comparing them reflexively: they are equivalent if
    !comp(a,b) && !comp(b,a)). No two elements in a set container can be
    equivalent.

    This can be a function pointer or a function object (see constructor
    for an example). This defaults to less, which returns the same as
    applying the less-than operator (a<b).
    Aliased as member types set::key_compare and set::value_compare.

  • Alloc
    Type of the allocator object used to define the storage allocation
    model. By default, the allocator class template is used, which
    defines the simplest memory allocation model and is
    value-independent.
    Aliased as member type set::allocator_type.

[cpp]view plaincopy

Member types

member type definition notes
key_type The first template parameter (T)
value_type The first template parameter (T)
key_compare The second template parameter (Compare) defaults to: less
value_compare The second template parameter (Compare) defaults to: less
allocator_type The third template parameter (Alloc) defaults to: allocator
reference allocator_type::reference for the default allocator: value_type&
const_reference allocator_type::const_reference for the default allocator: const value_type&
pointer allocator_type::pointer for the default allocator: value_type*
const_pointer allocator_type::const_pointer for the default allocator: const value_type*
iterator a bidirectional iterator to value_type convertible to const_iterator
const_iterator a bidirectional iterator to const value_type
reverse_iterator reverse_iterator
const_reverse_iterator reverse_iterator
difference_type a signed integral type, identical to: iterator_traits::difference_type usually the same as ptrdiff_t
size_type an unsigned integral type that can represent any non-negative value of difference_type usually the same as size_t

#includeiostream

Member functions

  • (constructor) Construct set (public member function )
  • (destructor) Set destructor (public member function )
  • operator= Copy container content (public member function )

Iterators:

  • begin Return iterator to beginning (public member function )
  • end Return iterator to end (public member function )
  • rbegin Return reverse iterator to reverse beginning (public
    member function )
  • rend Return reverse iterator to reverse end (public member
    function )
  • cbegin Return const_iterator to beginning (public member
    function )
  • cend Return const_iterator to end (public member function )
  • crbegin Return const_reverse_iterator to reverse beginning
    (public member function )
  • crend Return const_reverse_iterator to reverse end (public
    member function )

#includeset

Capacity:

  • empty Test whether container is empty (public member function )
  • size Return container size (public member function )
  • max_size Return maximum size (public member function )

usingnamespacestd;

Modifiers:

  • insert Insert element (public member function )
  • erase Erase elements (public member function )
  • swap Swap content (public member function )
  • clear Clear content (public member function )
  • emplace Construct and insert element (public member function )
  • emplace_hint Construct and insert element with hint (public
    member function )

int_tmain(intargc,_TCHAR*argv[])

Observers:

  • key_comp Return comparison object (public member function )
  • value_comp Return comparison object (public member function )

{

Operations:

  • find Get iterator to element (public member function )
  • count Count elements with a specific value (public member
    function )
  • lower_bound Return iterator to lower bound (public member
    function )
  • upper_bound Return iterator to upper bound (public member
    function )
  • equal_range Get range of equal elements (public member function
    )

setintmyset;

Allocator:

  • get_allocator Get allocator (public member function )

setint::iteratorit,itlow,uplow;

Code Example

#include <iostream>
#include <set>

using namespace std;

bool fncomp(int lhs, int rhs)
{ return lhs < rhs; }

struct classcomp
{
    bool operator() (const int& lhs, const int& rhs) const
    { return lhs<rhs; }
};

int main(int argc, char **argv)
{
    set<int> first;

    int myints[] = {10,20,30,40,50};

    set<int> first1(myints, myints+5);
    set<int> first2(first1);

    set<int> first3(first2.begin(),first2.end());

    set<int, classcomp> first4;

    bool (*fn_pt)(int,int) = fncomp;
    set<int, bool(*)(int,int)> first5(fn_pt);
    /** other function please to reference other container */

    set<int> second;
    for(int i=0; i < 10; i++)
    {
        second.insert(i);
    }

    cout << 'n';
    set<int>::key_compare comp = second.key_comp();
    int nNum = *(second.rbegin());
    auto it = second.begin();
    do{
        cout << *it << 't';
    }while( comp(*(++it), nNum) );
    /** outpur:0 1 2 3 4 5 6 7 8 */

    set<int> third;
    for(int i=0; i < 5; i++)
    {
        third.insert(i);
    }
    set<int>::value_compare valComp = third.value_comp();
    nNum = *(third.rbegin());
    it = third.begin();
    cout << 'n';
    do
    {
        cout << *it << 't';
    }while( valComp( *(++it), nNum ) );

    return 0;
}

inti;

Reference

cplusplus

//插入数据

coutinsertelementsendl;

for(i=0;i10;i++)

myset.insert(i*2);

intnum=4;

//查询、删除数据

coutfindanddeleteelement4endl;

it=myset.find(num);

if(it!=myset.end())

{

myset.erase(it);

}

num=7;

//元素边界

itlow=myset.lower_bound(num);

uplow=myset.upper_bound(num);

coutnumlowerboundis*itlowendl;

coutnumupperboundis*uplowendl;

pairsetint::iterator,setint::iteratorret=myset.equal_range(7);

coutnumlowerboundis*ret.firstendl;

coutnumupperboundis*ret.secondendl;

//check数据是否在容器中

if(myset.count(num)0)

coutnumisanelementofmyset.n;

else

coutnumisnotanelementofmyset.n;

//输出容器大小

coutsetsize:(int)myset.size()endl;

//输出容器内元素

coutmysetcontains:;

for(it=myset.begin();it!=myset.end();it++)

{

cout*it;

}

coutendl;

system(pause);

return0;

}