C++ map 学习笔记

内容来源:https://zh.cppreference.com/w/cpp/container/map std::map 是有序键值对容器,元素的键是唯一的。用比较函数 Compare 排序键。map 通常实现为红黑树。定义于头文件 map

  1. 成员函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // constructor
    map(); // 空容器
    map( InputIt first, InputIt Last, const Compare& comp = Compare() ); // 构造容器拥有 [first, last) 的内容
    map( const map& other ); // 复制构造函数
    map( map&& other ); // 移动构造函数

    // 示例
    std::map<std::string, int> map1;
    map1["something"] = 69;
    map1["anything"] = 199;
    map1["that thing"] = 50;
    std::map<std::string, int> iter(map1.find("anything"), map1.end());
    std::map<std::string, int> copied(map1);
    std::map<std::string, int> moved(std::move(map1));

    // deconstructor
    ~map();
  2. 元素访问

    1
    2
    T& at( const Key& key); // 返回拥有等于 key 的元素被映射值得引用,无则异常
    T& operator[]( const Key& key ); // 若 key 不存在,则插入 value_type(key, T()),等价于 return insert(std::make_pair(key, T())).first->second;
  3. 迭代器

    1
    2
    3
    4
    iterator begin(); // 返回容器首元素的迭代器
    iterator end(); // 返回容器末元素后一位的迭代器

    // 同 vector,list 还有 rbegin,rend,cbegin...
  4. 容量

    1
    2
    bool empty() const; // 返回容器是否为空
    size_type size() const; // 返回容器中的元素数
  5. 修改器

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void clear(); // 清空容器

    std::pair<iterator, bool> insert( const value_type& value); // 插入 value
    iterator insert(iterator hint, const value_type& value); // 在 hint 前插入 value
    void insert( InputIt first, InputIt last ); // 插入来自范围 [first, last) 的元素

    pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // 存在则更新,不存在则插入

    std::pair<iterator,bool> emplace( Args&&... args ); // 容器中无拥有该关键的元素,则插入以给定的 args 原位构造的新元素到容器。
    pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // 若容器中已存在等价于 k 的关键,则不做任何事。否则行为类似 emplace
    iterator emplace_hint( const_iterator hint, Args&&... args ); // 插入元素到尽可能靠近正好在 hint 之前的位置

    void erase( iterator pos ); // 移除位于 pos 的元素。
    void erase( iterator first, iterator last ); // 移除范围 [first; last) 中的元素,它必须是 *this 中的合法范围。
    size_type erase( const key_type& key ); // 移除关键等于 key 的元素

    void swap( map& other ); // 将内容与 other 的交换
  6. 查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    size_type count( const Key& key ) const; // 返回拥有关键 key 的元素数

    iterator find( const Key& key ); // 寻找键等于 key 的的元素

    bool contains( const Key& key ) const; // 检查容器中是否有关键等价于 key 的元素

    std::pair<iterator,iterator> equal_range( const Key& key ); // 含一对定义所需范围的迭代器的 std::pair :第一个指向首个不小于 key 的元素,第二个指向首个大于 key 的元素
    iterator lower_bound( const Key& key ); // 返回指向首个不小于 key 的元素的迭代器
    iterator upper_bound( const Key& key ); // 返回指向首个大于 key 的元素的迭代器

unordered_map 是关联容器,含有带唯一键的键-值 pair 。搜索、插入和元素移除拥有平均常数时间复杂度。元素在内部不以任何特定顺序排序,而是组织进桶中。元素放进哪个桶完全依赖于其键的哈希。这允许对单独元素的快速访问,因为一旦计算哈希,则它准确指代元素所放进的桶。

  1. 桶接口

    1
    2
    3
    4
    5
    6
    const_local_iterator begin( size_type n ) const; // 返回指向下标为 n 的桶首元素的迭代器
    const_local_iterator end( size_type n ) const; // 返回后随下标为 n 的桶的最后元素的元素的迭代器
    size_type bucket_count() const; // 返回容器中的桶数
    size_type max_bucket_count() const; // 返回容器由于系统或库实现限制的能保有的最大桶数
    size_type bucket_size( size_type n ) const; // 返回下标为 n 的桶中的元素数
    size_type bucket( const Key& key ) const; // 返回关键 key 的桶的下标。始终会在此桶中找到关键等于 key 的元素(若存在)
# C++

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×