C++ STL-map与set的使用

椰

发布于 2025-01-27 00:20:13

5200

代码可运行

文章被收录于专栏：转自CSDN转自CSDN

运行总次数：0

代码可运行

序列式容器与关联式容器

序列式容器和关联式容器是C++标准模板库（STL）中的两大类容器

序列式容器

序列式容器存储的元素在逻辑上呈现为线性序列。这些容器的共同特点是，它们允许通过位置（索引）来访问元素，且元素之间的相对位置是固定的，除非进行插入或删除操作。常见的序列式容器包括：

vector：一个动态数组，支持随机访问，但在中间插入或删除元素时可能需要移动大量元素。
deque（双端队列）：一个支持在两端高效插入和删除的动态数组。它提供了随机访问功能，但与vector相比，在两端进行操作时性能更优。
list：一个双向链表，不支持随机访问，但在任意位置插入和删除元素时性能较好。
forward_list：一个单向链表，与list相比，它只支持向前遍历，但内存开销更小。
array：一个固定大小的数组，不支持动态调整大小，但提供了与vector类似的随机访问性能。

关联式容器

关联式容器存储的元素是按关键字（key）组织起来的，这些关键字用于快速查找、插入和删除元素。关联式容器通常基于平衡二叉树（如红黑树）或哈希表实现。常见的关联式容器包括：

map：一个关联数组，存储键值对（key-value pairs），其中每个键都是唯一的。map中的元素按键的升序排列（默认情况下，可以通过提供自定义比较函数来改变排序规则）。
set：一个元素集合，其中每个元素都是唯一的。set中的元素按升序排列（同样可以通过提供自定义比较函数来改变排序规则）。
unordered_map：一个基于哈希表的关联数组，存储键值对，其中键不需要唯一（但通常在实际使用中保持唯一以避免未定义行为），且不支持按键排序。查找、插入和删除操作的时间复杂度平均为O(1)。
unordered_set：一个基于哈希表的元素集合，其中每个元素都是唯一的，且不支持排序。查找、插入和删除操作的时间复杂度平均为O(1)。

区别

访问方式：序列式容器主要通过位置（索引）访问元素，而关联式容器主要通过关键字访问元素。
有序性：默认情况下，map和set中的元素按键的升序排列，而unordered_map和unordered_set中的元素则无序。
性能：在序列式容器中，随机访问（如vector）通常很快，但在中间插入或删除元素可能较慢。在关联式容器中，查找、插入和删除操作的时间复杂度通常为O(log n)（对于基于红黑树的容器）或O(1)（对于基于哈希表的容器）。
内存使用：序列式容器（如vector）在连续内存中存储元素，通常具有较低的内存碎片。而关联式容器（特别是基于哈希表的容器）可能由于哈希冲突和动态调整大小而导致较高的内存开销。

关联式容器：map和set

map

定义：map是一个关联容器，它存储的是键值对（key-value pairs）。
特性：
- map中的元素按键的升序排列（默认情况下，可以通过自定义比较函数来改变排序规则）。
- key在map中是唯一的。
- 每个元素都是一个pair，其第一个元素是key（键），第二个元素是value（值）。

set

定义：set是一个关联容器，它存储的是唯一的元素（即key）。
特性：
- set中的元素是唯一的。
- set中的元素按升序排列（默认情况下，同样可以通过自定义比较函数来改变排序规则）。

set的使用

set类

set的声明需要T（也就是关键字Key的类型）
set默认T排序支持小于排序，也可以写仿函数自行提供排序方式
set的储存数据内存是从空间配置器来申请，也可以自己实现内存池
set的第二个和第三个模板参数一般不需要自己填写
set的底层是红黑树，增删查改效率为O（logN），是有序的，迭代器走的是中序

template < class T,                        // key类型T
           class Compare = less<T>,        // Compare的比较仿函数
           class Alloc = allocator<T>      // 内存池
           > class set;

set的构造与迭代器

set的构造与之的STL构造一样
set的迭代器支持正向和反向迭代器，遍历默认升序
支持范围for
迭代器不支持修改数数据，不能修改key

//empty (1)	无参构造
explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
//range (2)	迭代器区间构造
template <class InputIterator>
  set (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());
//copy (3)	拷贝构造
    set (const set& x);

//这里还有一个移动构造 移动构造函数我会但开一篇

//初始化器列表 （5）	
set (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());
//迭代器 双向迭代器
iterator	a bidirectional iterator to const value_type	
//const迭代器
const_iterator	a bidirectional iterator to const value_type	
//反向迭代器
reverse_iterator	reverse_iterator<iterator>	
//const的反向迭代器
const_reverse_iterator	reverse_iterator<const_iterator>	
//正向迭代器
iterator begin()/end()
//反向迭代器
reverse_iterator rbegin()/rend()

示例（构造）

int main() {
    set<int> A;
    array<int, 10>B = {0,1,2,3,4,5,6,7,8,9};
    set<int> C(B.begin(), B.end());
    set<int> D = {1,2,3,4,5};
    return 0;
}

set的增删查（不支持改！）

//成员类型
key_type	The first template parameter (T)	
value_type	The first template parameter (T)	

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find (const value_type& val);
// 查找val，返回Val的个数
size_type count (const value_type& val) const;

// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);

// 返回⼤于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound (const value_type& val) const;

示例（insert与迭代器）

    set<int> A = {1,3,5,7,9};//列表构造
    cout << A.insert(1).second << endl;
    A.insert({2,4});
    array<int, 2> arr = { 6,8 };
    A.insert(arr.begin(), arr.end());
    auto it = A.begin();
    while (it != A.end())
        cout << *it++ << " ";
    cout << endl;
    for (auto itt : A)
        cout << itt << ' ';
    cout << endl;
    return 0;

示例（find与erase与cout的使用）

//find与erase使用
    set<int> A = { 1,9,2,8,3,7,4,6,5 };
    for (auto it : A) cout << it << ' ';
    cout << endl;

    A.erase(A.begin());//删除min
    for (auto it : A) cout << it << ' ';
    cout << endl;

    int x;
    cin >> x;
    if (A.erase(x) == 0)
        cout << "我找不到" << endl;
    
    for (auto it : A) cout << it << ' ';
    cout << endl;

    cin >> x;
    if (A.find(x) != A.end())
        A.erase(A.find(x));//有点刻意
    else
        cout << "我找不到" << endl;

    for (auto it : A) cout << it << ' ';
    cout << endl;

    cin >> x;
    //在算法库中找位置 O（N）的效率
    auto pos1 = find(A.begin(), A.end(), x);
    //自身查找效率为O（logn）
    auto pos2 = A.find(x);

    //count是对特定元素进行计数
    if (A.count(x))
        cout << "找到啦" << endl;
    else
        cout << "我找不到" << endl;

    return 0;

示例（lower与upper的使用）

    set<int> A = { 1,9,2,8,3,7,4,6,5 };
    for (auto it : A) cout << it << ' ';
    cout << endl;

    //在erase的删除 是[low，up）的情况 有时候可能不好操作 因为up不会被删
    //所以采用lower_bound 与 upper_bound
    auto low = A.lower_bound(2);
    auto up = A.upper_bound(7);
    A.erase(low, up);

    for (auto it : A) cout << it << ' ';
    cout << endl;

multiset与set的差异

insert操作：
- set：在set中插入元素时，如果元素已经存在，则插入操作会失败，不会改变set的内容。
- multiset：在multiset中插入元素时，即使元素已经存在，插入操作也会成功，multiset会允许重复元素的存在。
find操作：
- set 和 multiset：两者都提供find操作来查找元素。如果元素存在，find操作会返回一个指向该元素的迭代器；如果元素不存在，则返回指向容器末尾的迭代器（end()）。
- 特别说明：在multiset中，由于可能存在多个相同的元素，find操作返回的是指向第一个匹配元素的迭代器。
count操作：
- set：由于set中元素唯一，因此count操作对于任何元素都会返回0或1，表示该元素是否存在于set中。
- multiset：在multiset中，count操作会返回指定元素在容器中出现的次数。
erase操作：
- set：在set中，erase操作可以删除指定元素（如果存在的话），只会删除第一个匹配的元素（因为set中不会有重复元素）。
- multiset：在multiset中，erase操作同样可以删除指定元素，但如果有多个相同的元素，它会删除所有匹配的元素（除非指定了只删除一个的迭代器版本）。

    multiset<int> A;
    A.insert(1);
    A.insert(1);
    A.insert(1);
    A.insert(1);
    A.insert(2);

    for (auto it : A)
        cout << it<<' ';
    cout << endl;
    cout<< A.count(1);
    A.erase(1);
    cout << endl;
    cout << A.count(1);

map的使用

map类

map要Key和Value的底层关键字
Key要支持比较
Comare可以自己写
我们一般建议只管Key和Value的类型
map底层是红黑树
增删查“改”的效率为O(logN)
迭代器走中序遍历，key是有序的

emplate < class Key, // 关键字Key类型
    class T, // 键值对Value类型
    class Compare = less<Key>, // Compare仿函数
    class Alloc = allocator<pair<const Key,T> > //。。。
    > class map;

pair类

pair是存储键值对的玩意

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair
{
    typedef T1 first_type; //第一个类型
    typedef T2 second_type;//第二个类型
    T1 first;
    T2 second;
    pair() : first(T1()), second(T2())
    {}
    pair(const T1& a, const T2& b) : first(a), second(b)
    {}
    template<class U, class V>
    pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
    {}
};

template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{
    return (pair<T1, T2>(x, y));
}

map的构造

map支持正向和反向迭代器
key默认升序
迭代器走中序
支持范围for
可以i更改value（不支持修改key）

//empty (1) 无参构造	
explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
explicit map (const allocator_type& alloc);
//range (2) 迭代器构造	
template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& = allocator_type());
//copy (3)拷贝构造	
map (const map& x);
map (const map& x, const allocator_type& alloc);
//move (4)移动构造 这里不提及	
map (map&& x);
map (map&& x, const allocator_type& alloc);
//initializer list (5)列表构造	
map (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type())

// 迭代器是⼀个双向迭代器
iterator -> a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

int main()
{
    map<int, int> A;
    A.insert({ 1,1 });
    A.insert({ 2,2 });
    A[3] = 3;
    map<int, int> B(A.begin(), A.end());
    map<int, int> C(B);
    map<char, int> D({ { 'a','a' }, { 'b','b' }, { 'c','c' }, { 'd','d' }});
    for (auto it : D)
    {
        cout <<it.first<< it.second <<' ';
    }
    auto rit = D.rbegin();
    cout << endl;
    while (rit != D.rend())
    {
        cout<<rit->first<< rit->second<<' ';
        rit++;
    }
    return 0;
}

map的增删查

与set类似
map增的是pair
只用关键字key删
find返回的迭代器可以映射出value
支持改value

key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>
// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find (const key_type& k);
// 查找k，返回k的个数
size_type count (const key_type& k) const;
// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除k，k存在返回0，存在返回1
size_type erase (const key_type& k);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);
// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type& k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type& k) const;

示例（增删查）

    map<int, char> n{ {1,'1'},{2,'2'} ,{3,'3'} ,{4,'4'} ,{5,'5'}, {6,'6'} };
    //这里做使用
    if (n.insert({ 1,'2' }).second == false)
        cout << n.insert({ 1,'2' }).first->second << endl;

    n.insert({ {7,'7'},{8,'8'} });
    map<int, char> nn;
    nn.insert(n.begin(), n.end());

    if (n.find(1) != n.end())
        cout << n.find(1)->second;
    cout << endl;
    cout << n.count(1);

    n.erase(n.find(1));
    n.erase(2);
    n.erase(n.lower_bound(1), n.upper_bound(6));
    cout << endl;
    for (auto it : nn)
        cout << it.second << ' ';
    cout << endl;

    for (auto rit : n)
        cout << rit.second << ' ';
    cout << endl;

map的数据修改

map支持value的数据的修改
map不支持key的数据的修改
map的修改支持通过迭代器修改
map有一个重要接口 [ ]，它可以支持修改还支持查找还支持插入修改

iterator find (const key_type& k);
pair<iterator,bool> insert (const value_type& val);
mapped_type& operator[] (const key_type& k);
mapped_type& operator[] (const key_type& k)
{
pair<iterator, bool> ret = insert({ k, mapped_type() });
iterator it = ret.first;
return it->second;
}
/*
我来简单的解释一下过程
    1.调用[]的时候 先进行插入{k，value}的行为
         无论插入成功与否，都会返回一个pari的元素
                pari的first 存储的是key的位置的迭代器
                pari地scound存储地是bool类型 插入成功是true 失败是false
                    插入成功就是这里本没有数据 失败就是这里本来有数据
    2.返回地pair类型存储在ret内 
        创建一个it迭代器指向 first
            it指向key的迭代器
    3.返回key指向的value 
*/

map的 [ ]案例

    map<string, string> dict;
    dict.insert(make_pair("sort", "排序"));
    // key不存在->插⼊ {"insert", string()}
    dict["insert"];
    // 插⼊+修改
    dict["left"] = "左边";
    // 修改
    dict["left"] = "左边、剩余";
    // key存在->查找
    cout << dict["left"] << endl;

multimap与map的差异

键值唯一性

map：在map中，键（key）是唯一的，即每个键只能映射到一个值（value）。如果尝试插入一个已存在的键，那么新的值会替换旧的值。
multimap：与map不同，multimap允许一个键对应多个值。这意味着在同一个multimap中，可以有多个键值对拥有相同的键。

操作符支持

map：map支持使用at()方法或[]操作符来查找或修改数据。如果使用[]操作符访问一个不存在的键，map会自动插入一个具有该键和默认值的键值对。
multimap：由于multimap允许键重复，因此它未提供at()成员方法，也没有重载[]运算符。相反，multimap提供了其他查找方法，如find()、lower_bound()、upper_bound()和equal_range()，这些方法可以返回指向具有特定键的键值对的迭代器范围。

插入与返回值

map：当向map中插入元素时，如果键已存在，则插入操作会失败。map的insert()方法返回一个pair<iterator, bool>，其中迭代器指向插入的位置（或已存在的元素），而布尔值表示插入是否成功。
multimap：向multimap中插入元素时，即使键已存在，插入操作也会成功，因为multimap允许键重复。multimap的insert()方法只返回一个迭代器，指向插入的位置。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-25，如有侵权请联系 cloudcommunity@tencent.com 删除

c++