# 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).

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.

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

}
{"ft_lang_label":"__label__en","ft_lang_prob":0.5133717,"math_prob":0.7401759,"size":10081,"snap":"2020-34-2020-40","text_gpt3_token_len":2983,"char_repetition_ratio":0.21335715,"word_repetition_ratio":0.117359415,"special_character_ratio":0.21813312,"punctuation_ratio":0.1388191,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9659603,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-09-26T21:15:31Z\",\"WARC-Record-ID\":\"<urn:uuid:e0af68b8-93a7-46c1-81df-e3e1afb23f7b>\",\"Content-Length\":\"32270\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:379a8b95-a853-4f25-84ea-017c696f0355>\",\"WARC-Concurrent-To\":\"<urn:uuid:e0d50c4e-2cad-4dae-9c7f-1aefd5701c79>\",\"WARC-IP-Address\":\"154.196.120.155\",\"WARC-Target-URI\":\"http://www.shoelucky.com/archives/2887.html\",\"WARC-Payload-Digest\":\"sha1:G73U2JIMISQEHLVXM2IFHX2R4CF7TW52\",\"WARC-Block-Digest\":\"sha1:KJNLBZXW3C6EH5GQRQ6ZHBKFZSBP7MNP\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-40/CC-MAIN-2020-40_segments_1600400245109.69_warc_CC-MAIN-20200926200523-20200926230523-00029.warc.gz\"}"}