关联容器Associative

1、map

map 的特性是, 所有元素会根据元素的键值自动被排序, map 的所有元素都是 pair,同时拥有实值(Value)和键值(Key)。pair 的第一元素被视为键值, 第二个元素被视为实值。 map 不允许两个元素拥有相同的键值。

map 中的元素是自动按 Key 升序排序, 所以不能对 map 用 sort 函数;STL 中默认是采用小于号来排序的, 基本数据类型在排序上是不存在任何问题的, 因为它本身支持小于号运算, 在一些特殊情况, 比如关键字是一个结构体, 涉及到排序就会出现问题, 因为它没有小于号操作, insert 等函数在编译的时候过不去, 就需要给出解决方案。常用的解决方案: 小于号重载, 仿函数, lambda

内存结构

pair

声明和头文件

#include <map>
namespace std {
template <typename Key,
          typename T,
          typename Compare = less<Key>,
          typename Allocator = allocator<pair<const Key,T> > >
class map;
template <typename Key,
          typename T,
          typename Compare = less<Key>,
          typename Allocator = allocator<pair<const Key,T> > >
class multimap;
}

2、api

OperationEffect
map cDefault constructor; creates an empty map/multimap without any elements
map c(op)Creates an empty map/multimap that uses op as the sorting criterion
map c(c2)Copy constructor; creates a copy of another map/multimap of the same type (all elements are copied)
map c = c2Copy constructor; creates a copy of another map/multimap of the same type (all elements are copied)
map c(rv)Move constructor; creates a new map/multimap of the same type, taking the contents of the rvalue rv (since C++11)
map c = rvMove constructor; creates a new map/multimap of the same type, taking the contents of the rvalue rv (since C++11)
map c(beg,end)Creates a map/multimap initialized by the elements of the range [beg,end)
map c(beg,end,op)Creates a map/multimap with the sorting criterion op initialized by the elements of the range [beg,end)
map c(initlist)Creates a map/multimap initialized with the elements of initializer list initlist (since C++11)
map c = initlistCreates a map/multimap initialized with the elements of initializer list initlist (since C++11)
c.~map()Destroys all elements and frees the memory

上表中的 map 可为如下几种类型

OperationEffect
map<Key,Val>A map that by default sorts keys with less<> (operator <)
map<Key,Val,Op>A map that by default sorts keys with Op
multimap<Key,Val>A multimap that by default sorts keys with less<> (operator <)
multimap<Key,Val,Op>A multimap that by default sorts keys with Op

测试代码

#include <iostream>
#include <map>
#include <functional>
using namespace std;
int main()
{
    map<int,string > mis = {
        pair<int,string>(1,"a"),
        pair<int,string>(2,"abc")
    }
    map<int,string,less<int>> mis2;
    map<int,string > mis3(greater<int>());

    mis.insert({make_pair(6,"german"),make_pair(7,"germany")});//这样写可以
    //也可以不是make_pair,而是pair

    map<int,string> ::itrator itr;
    for(itr = mis.begin();itr != mis.end(); ++itr)
    {
        cout<<itr->first<<":"<<itr->second<<endl;
    }
    return 0;
}
OperationEffect
c.key_comp()Returns the comparison criterion
c.value_comp()Returns the comparison criterion for values as a whole (an object that compares the key in a key/value pair)
c.empty()Returns whether the container is empty (equivalent to size()==0 but might be faster)
c.size()Returns the current number of elements
c.max_size()Returns the maximum number of elements possible
c1 == c2Returns whether c1 is equal to c2 (calls == for the elements)
c1 != c2Returns whether c1 is not equal to c2 (equivalent to !(c1==c2))
c1 < c2Returns whether c1 is less than c2
c1 > c2Returns whether c1 is greater than c2 (equivalent to c2<c1)
c1 <= c2Returns whether c1 is less than or equal to c2 (equivalent to !(c2<c1))
c1 >= c2Returns whether c1 is greater than or equal to c2 (equivalent to !(c1<c2))
OperationEffect
c = c2Assigns all elements of c2 to c
c = rvMove assigns all elements of the rvalue rv to c (since C++11)
c = initlistAssigns all elements of the initializer list initlist to c (since C++11)
c1.swap(c2)Swaps the data of c1 and c2
swap(c1,c2)Swaps the data of c1 and c2
OperationEffect
c.begin()Returns a bidirectional iterator for the first element
c.end()Returns a bidirectional iterator for the position after the last element
c.cbegin()Returns a constant bidirectional iterator for the first element (since C++11)
c.cend()Returns a constant bidirectional iterator for the position after the last element (since C++11)
c.rbegin()Returns a reverse iterator for the first element of a reverse iteration
c.rend()Returns a reverse iterator for the position after the last element of a reverse iteration
c.crbegin()Returns a constant reverse iterator for the first element of a reverse iteration (since C++11)
c.crend()Returns a constant reverse iterator for the position after the last element of a reverse iteration (since C++11)
OperationEffect
c.insert(val)Inserts a copy of val and returns the position of the new element and, for maps, whether it succeeded
c.insert(pos,val)Inserts a copy of val and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
c.insert(beg,end)Inserts a copy of all elements of the range [beg,end) (returns nothing)
c.insert(initlist)Inserts a copy of all elements in the initializer list initlist (returns nothing; since C++11)
c.emplace(args...)Inserts a copy of an element initialized with args and returns the position of the new element and, for maps, whether it succeeded (since C++11)
c.emplace_hint(pos,args...)Inserts a copy of an element initialized with args and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
c.erase(val)Removes all elements equal to val and returns the number of removed elements
c.erase(pos)Removes the element at iterator position pos and returns the following position (returned nothing before C++11)
c.erase(beg,end)Removes all elements of the range [beg,end) and returns the following position (returned nothing before C++11)
c.clear()Removes all elements (empties the container)
OperationEffect
c.count(val)Returns the number of elements with key val
c.find(val)Returns the position of the first element with key val (or end() if none found)
c.lower_bound(val)Returns the first position where an element with key val would get inserted (the first element with a key >= val)
c.upper_bound(val)Returns the last position where an element with key val would get inserted (the first element with a key > val)
c.equal_range(val)Returns a range with all elements with a key equal to val (i.e., the first and last positions, where an element with key val would get inserted)

lower_bound 函数用法, 这个函数用来返回要查找关键字的下界(是一个迭代器)。upper_bound 函数用法, 这个函数用来返回要查找关键字的上界(是一个迭代器)例如: map 中已经插入了 1, 2, 3, 4 的话, 如果 lower_bound(2)的话, 返回的 2, 而upper-bound(2) 的话, 返回的就是 3。equal_range 函数返回一个 pair, pair 里面第一个变量是 lower_bound 返回的迭代器,pair 里面第二个迭代器是 upper_bound 返回的迭代器, 如果这两个迭代器相等的话, 则说明 map 中不出现这个关键字,

auto range = mis.equal_range(3);
//等价于pair<map<int,string>::iterator,map<int,string>::iterator> range2 = mis.equal_range(3);
cout<<range2.first->first<<":"<<range2.second->first<<endl;
return 0;

3、multimap

允许 key 重复的 map, 操作规则同上。

4、set

仅有 key 且 key 不能重复的 map, 操作规则同上

multiset

仅有 key 且key 可以重复的 map, 操作规则同上

Last modification:September 16th, 2019 at 07:09 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment