澳门新葡萄京娱乐场C++ std::map

  1. 概念

std::map

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

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。

Map

Maps are associative containers that store elements formed by a
combination of a key value and a mapped value, following a specific
order.

In a map, the key values are generally used to sort and uniquely
identify the elements, while the mapped values store the content
associated to this key.
The types of key and mapped value may differ,
and are grouped together in member type value_type, which is a pair
type combining both:

typedef pair<const Key, T> value_type;

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

map containers are generally slower than unordered_map containers to
access individual elements by their key, but they allow the direct
iteration on subsets based on their order.

The mapped values in a map can be accessed directly by their
corresponding key using the bracket(方括号) operator ((operator[]).

Maps are typically implemented as binary search trees(二叉搜索树).

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.
  • Map: Each element associates a key to a mapped value: Keys are
    meant to identify the elements whose main content is the mapped
    value.
  • 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.

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

  • Key: Type of the keys. Each element in a map is uniquely
    identified by its key value. Aliased as member type map::key_type.
  • T: Type of the mapped value. Each element in a map stores some
    data as its mapped value. Aliased as member type map::mapped_type.
  • Compare: A binary predicate(二元谓词) that takes two element
    keys as arguments 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 map 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 map container can have equivalent keys. 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 type
    map::key_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 map::allocator_type.

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 (Key)
mapped_type The second template parameter (T)
value_type pair
key_compare The third template parameter (Compare) defaults to: less
value_compare Nested function class to compare elements see value_comp
allocator_type The fourth template parameter (Alloc) defaults to: allocator
reference value_type&
const_reference const value_type&
pointer allocator_traits::pointer for the default allocator: value_type*
const_pointer allocator_traits::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

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 map (public member function )
  • (destructor) Map destructor (public member function )
  • operator= Copy container content (public member function )

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

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 )

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;

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 )
  • emplace Construct and insert element (public member function )
  • emplace_hint Construct and insert element with hint (public
    member function )

int_tmain(intargc,_TCHAR*argv[])

Element access:

  • operator[]: Access element (public member function )
  • at: Access element (public member function )

Observers:

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

{

Modifiers:

  • insert: Insert elements (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 )

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;

Observers(观察者):

  • key_comp: Return key comparison object (public member function
    )
  • value_comp: Return value comparison object (public member
    function )

Allocator:

  • get_allocator Get allocator (public member function )

setint::iteratorit,itlow,uplow;

Operations:

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

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;

Allocator:

  • get_allocator: Get allocator (public member function )

Reference

cplusplus

//插入数据

Code Example

#include <iostream>
#include <map>

using namespace std;

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

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

int main(int argc, char **argv)
{
    map<char,int> first1;

    first1['a'] = 10;   first1['b'] = 20;
    first1['c'] = 30;   first1['d'] = 40;

    map<char,int> first2( first1.begin(),first1.end() );
    map<char,int> first3( first2 );

    map<char,int, classcomp> first4; ///< class as Compare

    /** function pointer as Compare */
    bool(*fn_pt)(char,char) = fncomp;
    map<char,int,bool(*)(char,char)> first5(fn_pt);

    map<char,int> second;
    second.emplace('x', 100);
    second.emplace('y', 200);
    second.emplace('z', 300);
    cout << 'n';
    for(auto &x:second) cout << x.first << ":" << x.second << 't';

    auto it = second.end();
    it = second.emplace_hint(it, 'b', 20);
    second.emplace_hint(it, 'a', 10);
    second.emplace_hint(it, 'c', 30);
    cout << 'n';
    for(auto &x:second) cout << x.first << ":" << x.second << 't';

    map<char,int> third;
    /** 获取key 比较器 */
    map<char,int>::key_compare third_comp = third.key_comp();

    third['a'] = 100; third['b'] = 200;
    third['c'] = 300; third['d'] = 400;
    third['e'] = 500; third['f'] = 600;

    char dCh = 'd';
    it = third.begin();

    cout << 'n';
    do{
        cout << it->first << ":" << it->second << 't';
    }while( third_comp( (*it++).first, dCh ) );

    pair<char,int> dValue = *third.rbegin();

    it = third.begin();
    cout << 'n';
    do{
        cout << it->first << ":" << it->second << 't';
    }while( third.value_comp()( *it++, dValue ) );

    it = third.find('b');
    if( it != third.end() )
        third.erase(it);

    cout << 'n';
    for( char cIndex = 'a'; cIndex < 'z'; cIndex++ )
    {
        cout << cIndex;
        /** key == cIndex count */
        if( third.count(cIndex) > 0 )
            cout << " has n";
        else
            cout << " not has.n";
    }

    auto itlow = third.lower_bound('c'); ///< itlow points to c
    auto itup = third.upper_bound('e');  ///< itup points to f (not e)
    third.erase(itlow,itup);
    cout << 'n';
    for(auto &x:third) cout << x.first << ":" << x.second << 't';

    map<char,int> four;

    four['a'] = 10; four['b'] = 20;
    four['c'] = 30; four['d'] = 40;
    four['e'] = 50; four['f'] = 60;

    pair< map<char,int>::iterator, map<char,int>::iterator > ret;
    ret = four.equal_range('b');

    cout << "n lower bound points to:"
         << ret.first->first << ":" << ret.first->second;

    cout << "n upper bound points to: "
         << ret.second->first << ":" << ret.second->second;

    return 0;
}

coutinsertelementsendl;

Reference

cplusplus


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;

}

输出:insert elementsfind and delete element47 lower bound is 87 upper
bound is 87 lower bound is 87 upper bound is 87 is not an element of
myset.set size: 9myset contains: 0 2 6 8 10 12 14 16 18

  1. map/ multimap4.1
    概念和set相比,map同时拥有实值(value)和键值(key),其每一个元素都是pair,pair的第一个元素是键值,第二个元素是实值。map和multimap的区别在于,map不允许两个元素拥有相同的键值,而multimap允许存在重复的键值。pair定义如下:

[cpp]view plaincopy

templateclassT1,classT2

structpair

{

typedefT1first_type;

typedefT2second_type;

T1first;

T2second;

}

4.2 迭代器map和set的底层实现都是很RB-tree,其迭代器特点和set一致。4.3
Map API(constructor) Construct map (public member function)(destructor)
Map 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)Element
access:operator[] Access element (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 key comparison object (public member function)value_comp Return
value 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)4.4 map实例:

[cpp]view plaincopy

#includeiostream

#includemap

usingnamespacestd;

int_tmain(intargc,_TCHAR*argv[])

{

mapchar,intmymap;

mapchar,int::iteratorit;

pairmapchar,int::iterator,boolret1;

pairmapchar,int::iterator,mapchar,int::iteratorret;

//插入元素

mymap[a]=10;

mymap[b]=20;

mymap[c]=30;

mymap[d]=40;

ret1=mymap.insert(pairchar,int(c,500));

if(ret1.second==false)

{

coutelementcalreadyexisted;

coutwithavalueofret1.first-secondendl;

}

//寻找、删除

it=mymap.find(d);

mymap.erase(it);

//边界

ret=mymap.equal_range(b);

coutlowerboundpointsto:;

coutret.first-first=ret.first-secondendl;

coutupperboundpointsto:;

coutret.second-first=ret.second-secondendl;

//输出容器元素

coutmymapcontains:n;

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

cout(*it).first=(*it).secondendl;

system(pause);

return0;

}

输出:element c already existed with a value of 30lower bound points to:
b = 20upper bound points to: c = 30mymap contains:a = 10b = 20c = 305.
结语关联容器是把一个键值与一个元素联系起来,并使用该键来加速诸如查找、插入以及删除元素等操作。和序列容器相比,在使用键值来查找元素时,关联容器有更好的表现。

文章来自:yfk博客,本文知识转载

发表评论

电子邮件地址不会被公开。 必填项已用*标注