C++进阶之一篇文章教会你什么是map和set(上)

简介: 序列式容器和关联式容器序列式容器:序列式容器是一组用于存储数据的容器,其中的数据按照它们在容器中的位置进行存储和访问。序列式容器提供了对元素的线性访问和操作,其主要特点包括:

序列式容器和关联式容器

序列式容器:

序列式容器是一组用于存储数据的容器,其中的数据按照它们在容器中的位置进行存储和访问。序列式容器提供了对元素的线性访问和操作,其主要特点包括:

  1. 线性存储: 序列式容器按照元素在容器中的插入顺序线性存储。元素在容器中的位置是固定的,与键值无关。
  2. 支持重复元素: 序列式容器允许存储重复的元素,同一个值可以出现多次。
  3. 提供随机访问: 序列式容器支持随机访问,可以通过索引或迭代器快速访问任何位置的元素。
  4. 不排序元素: 序列式容器不会自动对元素进行排序,元素按照插入的顺序存储。

C++标准库中的序列式容器包括 std::vectorstd::dequestd::liststd::array 等。这些容器适用于需要按顺序处理数据的情况,如数组、列表、队列等。

总结

  • 关联式容器适用于需要高效的查找和排序的情况,数据按键值有序存储。
  • 序列式容器适用于需要线性存储和随机访问的情况,元素按插入顺序存储。
  • 选择容器类型取决于具体的需求和操作。关联式容器适用于需要快速查找和排序的情况,而序列式容器适用于需要按顺序处理数据的情况。

关联式容器:

关联式容器是一组用于存储数据的容器,其中的数据按照某种规则关联起来,通常是基于键值的关联。关联式容器提供了一种高效的方式来查找、插入和删除元素,其主要特点包括:

  1. 基于键值的存储: 关联式容器通过键值来存储和访问元素。每个元素都有一个关联的键,通过该键可以唯一标识和访问元素。
  2. 有序存储: 关联式容器通常会按照键值的顺序进行排序。这使得元素可以按照一定的顺序进行迭代,例如升序或降序。
  3. 高效的查找: 关联式容器提供了高效的查找操作。由于元素按键值有序存储,可以使用二分查找等算法来快速找到特定键对应的元素。
  4. 不允许重复键: 关联式容器通常不允许存储重复的键值。每个键只能对应一个元素。

C++标准库中的关联式容器包括 std::setstd::multisetstd::mapstd::multimap 等。这些容器适用于需要高效查找和排序的情况,如字典、集合等。

键值对

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量keyvaluekey代表键值,value表示与key对应的信息。比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义

SGI-STL中关于键值对的定义

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)
    {}
};

树形结构的关联式容器

根据应用场景的不同,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构

C++标准库提供了四种主要的树形结构关联式容器,它们分别是 std::setstd::multisetstd::mapstd::multimap。这些容器都是基于树的数据结构,通常使用红黑树实现,用于存储键值对,并提供高效的查找和排序功能。以下是对这四种容器的详细解释:

  1. std::set
  • std::set 是一个集合容器,它存储唯一的键值(key),不允许重复的键。
  • 元素按照键值自动排序(通常升序),这使得查找和插入操作都非常高效。
  • 提供了 inserterasefind 等操作来管理元素集合。
  1. std::multiset
  • std::multisetstd::set 类似,但允许存储重复的键值。因此,它可以包含相同的键多次。
  • 元素按照键值自动排序,查找和插入操作也非常高效。
  • 提供了 inserterasefind 等操作。
  1. std::map
  • std::map 是一个键值对容器,每个键都唯一对应一个值。
  • 元素按照键值自动排序,通常按照键的升序顺序排列。
  • 提供了 inserterasefind 等操作来管理键值对。
  1. std::multimap
  • std::multimapstd::map 类似,但允许存储相同的键对应不同的值,因此一个键可以对应多个值。
  • 元素按照键值自动排序,查找和插入操作非常高效。
  • 提供了 inserterasefind 等操作。

这些容器的共同特点是它们的元素是按照键值有序存储的,这使得它们适用于需要快速查找和自动排序的情况。它们使用平衡二叉树(通常是红黑树)来实现这些功能,保持了插入、删除和查找的平均时间复杂度为O(log N)

选择哪种容器取决于需求。如果需要存储唯一的键或键值对,可以选择 std::setstd::map。如果需要允许重复的键或键对应多个值,可以选择 std::multisetstd::multimap。这些容器提供了丰富的操作,可以满足各种数据组织和访问的需求。

set

1.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;
  1. T(class T):这是模板的第一个参数,表示存储在set容器中的元素的数据类型。set会存储类型为T的元素。
  2. Compare(class Compare = less<T>):这是模板的第二个参数,表示用于比较元素之间的顺序的比较函数。默认情况下,它采用less<T>,它使用元素的小于运算符<来进行比较。您可以提供自定义的比较函数,以定义元素之间的排序规则。这个比较函数必须是一个可调用的二元谓词,它接受两个参数(const T&类型)并返回一个bool值,指示它们的顺序。
  3. Alloc(class Alloc = allocator<T>):这是模板的第三个参数,表示用于分配和管理内存的分配器类型。默认情况下,它采用std::allocator<T>,这是C++标准库提供的分配器。您可以提供自定义的分配器类型,以满足特定的内存管理需求。

std::set是一个有序容器,它以红黑树Red-Black Tree)作为底层数据结构来存储元素。红黑树是一种自平衡二叉搜索树,保持了元素的有序性,并且允许高效的插入、删除和查找操作。std::set中的元素是唯一的,即相同的元素只会被存储一次。

成员类型

2.set的构造

关于C++标准库中std::set容器构造函数的不同形式和重载,以及它们的用途的解释:

  1. explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
  • 这是默认构造函数,创建一个空的std::set容器。
  • 参数comp用于指定比较函数,它用于确定元素的顺序。默认情况下,使用key_compare(),即容器类型中指定的比较函数。
  • 参数alloc用于指定分配器,用于管理内存。默认情况下,使用allocator_type(),即容器类型中指定的分配器。
#include <iostream>
#include <set>
int main() {
    // 使用默认构造函数创建一个空的 set
    std::set<int> mySet;
    // 向 set 中插入元素
    mySet.insert(5);
    mySet.insert(2);
    mySet.insert(8);
    // 输出 set 的内容
    for (const int& value : mySet) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    return 0;
}
  1. template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
  • 这是范围构造函数,创建一个std::set容器,并初始化其内容,从范围 [first, last) 中的元素。
  • 参数firstlast是迭代器,用于指定范围。容器将包含该范围内的元素。
  • 参数compalloc与默认构造函数中的含义相同,用于指定比较函数和分配器。
#include <iostream>
#include <set>
#include <vector>
int main() {
    // 创建一个包含 vector 中元素的 set
    std::vector<int> vec = {3, 1, 4, 1, 5, 9};
    std::set<int> mySet(vec.begin(), vec.end());
    // 输出 set 的内容
    for (const int& value : mySet) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    return 0;
}
  1. set (const set& x);
  • 这是拷贝构造函数,创建一个新的std::set容器,并使用另一个set容器x的内容初始化它。
  • 这个构造函数用于创建一个副本,将x中的所有元素复制到新容器中。
#include <iostream>
#include <set>
int main() {
    // 创建一个 set 并初始化
    std::set<int> set1 = {1, 2, 3};
    // 使用拷贝构造函数创建一个新的 set,复制 set1 的内容
    std::set<int> set2(set1);
    // 输出 set2 的内容
    for (const int& value : set2) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    return 0;
}
  1. 这些构造函数提供了不同的方式来初始化和创建std::set容器,以适应不同的需求。您可以根据需要选择适当的构造函数来创建和初始化std::set容器,以存储和管理数据。

赋值运算符重载

set& operator= (const set& x); 是C++标准库中std::set容器的赋值运算符(operator=)重载函数的签名。

这个赋值运算符用于将一个std::set容器的内容复制给另一个std::set容器。具体来说,它将右操作数(x,另一个std::set容器)的内容复制到左操作数(调用该运算符的std::set容器)中,并返回左操作数的引用。

下面是赋值运算符的使用示例:

std::set<int> set1 = {1, 2, 3};
std::set<int> set2;
// 使用赋值运算符将 set1 的内容复制到 set2
set2 = set1;
// 现在 set2 包含了 set1 的内容

在上面的示例中,set2 = set1 使用赋值运算符将set1的内容复制到set2,使得set2包含了与set1相同的元素。

需要注意的是,赋值运算符会删除左操作数原来的内容,并用右操作数的内容替代它。这意味着在赋值之后,左操作数的内容将与右操作数相同,而原来的内容将被销毁。

这个赋值运算符对于将一个std::set容器的内容复制到另一个容器非常有用,可以用于容器之间的数据交换和拷贝。

3.set迭代器

这些函数是C++标准库中std::set容器的成员函数,用于获取不同类型的迭代器和常量迭代器,以便遍历std::set容器的元素。以下是这些迭代器和常量迭代器的描述:

  1. begin:返回一个迭代器,指向std::set容器中第一个元素的位置。
  2. end:返回一个迭代器,指向std::set容器中超出最后一个元素的位置。
  3. rbegin:返回一个反向迭代器,指向std::set容器中最后一个元素的位置。使用反向迭代器可以逆序遍历容器。
  4. rend:返回一个反向迭代器,指向std::set容器中超出第一个元素的位置。它通常与rbegin一起使用,以定义逆序遍历的结束点。
  5. cbegin:返回一个常量迭代器,指向std::set容器中第一个元素的位置。常量迭代器用于遍历容器并防止修改容器中的元素。
  6. cend:返回一个常量迭代器,指向std::set容器中超出最后一个元素的位置。
  7. crbegin:返回一个常量反向迭代器,指向std::set容器中最后一个元素的位置。常量反向迭代器用于逆序遍历容器,并防止修改容器中的元素。
  8. crend:返回一个常量反向迭代器,指向std::set容器中超出第一个元素的位置。通常与crbegin一起使用,以定义逆序遍历的结束点。

示例

#include <iostream>
#include <set>
int main() {
    // 创建一个 std::set 容器并初始化
    std::set<int> mySet = {5, 2, 8, 1, 9};
    // 使用 begin 和 end 迭代器遍历容器
    std::cout << "正序遍历:" << std::endl;
    for (std::set<int>::iterator it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    // 使用 rbegin 和 rend 反序遍历容器
    std::cout << "逆序遍历:" << std::endl;
    for (std::set<int>::reverse_iterator rit = mySet.rbegin(); rit != mySet.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;
    // 使用 cbegin 和 cend 常量迭代器遍历容器
    std::cout << "使用常量迭代器:" << std::endl;
    for (std::set<int>::const_iterator cit = mySet.cbegin(); cit != mySet.cend(); ++cit) {
        std::cout << *cit << " ";
    }
    std::cout << std::endl;
    // 使用 crbegin 和 crend 常量反序遍历容器
    std::cout << "使用常量反序迭代器:" << std::endl;
    for (std::set<int>::const_reverse_iterator crit = mySet.crbegin(); crit != mySet.crend(); ++crit) {
        std::cout << *crit << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出

正序遍历:
1 2 5 8 9 
逆序遍历:
9 8 5 2 1 
使用常量迭代器:
1 2 5 8 9 
使用常量反序迭代器:
9 8 5 2 1

这个示例演示了如何使用不同类型的迭代器来遍历std::set容器中的元素。正序遍历使用beginend迭代器,逆序遍历使用rbeginrend反向迭代器,常量迭代器使用cbegincend,常量反序迭代器使用crbegincrend。这些迭代器允许您以不同的方式访问容器中的元素,并提供了对元素的只读访问(对于常量迭代器)或读写访问(对于非常量迭代器)

4.set容器函数

这里是关于C++标准库中std::set容器的容量相关成员函数的解释和示例:

  1. empty(测试容器是否为空):
  • bool empty() const 是一个公有成员函数,用于测试容器是否为空。
  • 如果容器为空,返回 true;否则,返回 false
  1. 示例:
std::set<int> mySet;
if (mySet.empty()) {
    std::cout << "容器为空" << std::endl;
} else {
    std::cout << "容器不为空" << std::endl;
}
  1. size(返回容器大小):
  • size_type size() const 是一个公有成员函数,用于返回容器中元素的数量。
  • 返回一个无符号整数类型 (size_type),表示容器中元素的个数。
  1. 示例:
std::set<int> mySet = {1, 2, 3, 4, 5};
std::cout << "容器的大小为: " << mySet.size() << std::endl;
  1. max_size(返回最大可能大小):
  • size_type max_size() const 是一个公有成员函数,用于返回容器的最大可能大小。
  • 返回一个无符号整数类型 (size_type),表示容器可以容纳的最大元素数量,这取决于系统和编译器。
  1. 示例:
std::set<int> mySet;
std::cout << "容器的最大可能大小为: " << mySet.max_size() << std::endl;

这些容量相关的成员函数允许您查询容器的状态,例如检查容器是否为空、获取容器的大小以及了解容器可以容纳的最大元素数量。这对于在使用容器时进行状态检查和资源规划非常有用。

5.set修改器函数

std::set容器的修改器(Modifiers)相关成员函数,它们用于修改std::set容器的内容:

  1. insert(插入元素):
  • std::pair<iterator, bool> insert(const value_type& val);
  • iterator insert(iterator position, const value_type& val);
  • template <class InputIterator> void insert(InputIterator first, InputIterator last);
  • 这些成员函数用于向std::set容器中插入元素。它们允许插入单个元素或一组元素。
  • 如果插入成功,insert函数返回一个迭代器指向插入的元素(或已存在的元素),以及一个bool值指示是否插入成功。
  1. erase(删除元素):
  • iterator erase(iterator position);
  • size_type erase(const key_type& key);
  • iterator erase(iterator first, iterator last);
  • 这些成员函数用于从std::set容器中删除元素。您可以提供要删除的元素的位置或键(key)。
  • erase函数返回一个迭代器,指向被删除元素之后的位置。
  1. swap(交换内容):
  • void swap(set& x);
  • 这个成员函数用于交换两个std::set容器的内容,使它们互相包含对方的元素。
  1. clear(清除内容):
  • void clear();
  • 这个成员函数用于清除容器中的所有元素,使容器变为空。
  1. emplace(构造并插入元素):
  • template <class... Args> pair<iterator, bool> emplace(Args&&... args);
  • 这个成员函数用于通过构造新元素并插入容器来添加新元素。它通过接受参数包(parameter pack)来构造元素,并返回插入的元素迭代器和一个bool值指示是否插入成功。
  1. emplace_hint(构造并插入元素,带有提示位置):
  • template <class... Args> iterator emplace_hint(iterator position, Args&&... args);
  • 这个成员函数与emplace类似,但允许提供一个插入位置的提示(iterator position),以便更高效地插入新元素。

示例

#include <iostream>
#include <set>
int main() {
    // 创建一个 std::set 容器并初始化
    std::set<int> mySet = {5, 2, 8, 1, 9};
    // 输出容器的内容
    std::cout << "容器的内容:";
    for (const int& value : mySet) {
        std::cout << " " << value;
    }
    std::cout << std::endl;
    // 使用 insert 插入元素
    std::pair<std::set<int>::iterator, bool> result1 = mySet.insert(3); // 插入元素3
    std::pair<std::set<int>::iterator, bool> result2 = mySet.insert(5); // 尝试插入重复元素5
    if (result1.second) {
        std::cout << "成功插入元素3" << std::endl;
    } else {
        std::cout << "元素3已存在" << std::endl;
    }
    if (result2.second) {
        std::cout << "成功插入元素5" << std::endl;
    } else {
        std::cout << "元素5已存在" << std::endl;
    }
    // 输出修改后的容器内容
    std::cout << "修改后的容器内容:";
    for (const int& value : mySet) {
        std::cout << " " << value;
    }
    std::cout << std::endl;
    // 使用 erase 删除元素
    mySet.erase(2); // 删除元素2
    // 输出删除元素后的容器内容
    std::cout << "删除元素后的容器内容:";
    for (const int& value : mySet) {
        std::cout << " " << value;
    }
    std::cout << std::endl;
    // 使用 emplace 插入元素(构造并插入)
    mySet.emplace(6); // 插入元素6
    // 输出插入元素后的容器内容
    std::cout << "插入元素后的容器内容:";
    for (const int& value : mySet) {
        std::cout << " " << value;
    }
    std::cout << std::endl;
    return 0;
}

输出

容器的内容: 1 2 5 8 9
成功插入元素3
元素5已存在
修改后的容器内容: 1 2 3 5 8 9
删除元素后的容器内容: 1 3 5 8 9
插入元素后的容器内容: 1 3 5 6 8 9
相关文章
|
30天前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
2月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
35 6
【数据结构】map&set详解
|
1月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
31 1
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
35 5
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
|
2月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
|
3月前
|
存储 安全 Java
java集合框架复习----(4)Map、List、set
这篇文章是Java集合框架的复习总结,重点介绍了Map集合的特点和HashMap的使用,以及Collections工具类的使用示例,同时回顾了List、Set和Map集合的概念和特点,以及Collection工具类的作用。
java集合框架复习----(4)Map、List、set
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。
|
3月前
|
存储 JavaScript 前端开发
ES6新特性(四): Set 和 Map
ES6新特性(四): Set 和 Map
|
3月前
|
存储 Java 索引
下一篇
无影云桌面