关联容器

关联容器简介

关联容器的概念

关联容器是用于存放多个单一数据类型的类模板。

关联容器内部存储的形式大多采用哈希表或者二叉树等非线性的数据结构。

关联容器增删元素时效率较低，但是查找元素的速度比线性表快。

关联容器的种类与选择

set ：集合，不允许有重复元素,容器存储元素作为键，键不能重复，能够快速读取。

map ：映射，容器存储的形式为键值对，一个键对应一个值，键不能重复，值能重复。

multiset ：集合，允许有重复键。

multimap ：映射，允许有重复键。

map简介

pair的概念

pair 是一个类模板，它定义在<utility>头文件中，它能够用来存放两个数据类型的数据。

pair是有两个泛型的模板类，原型声明如下

template<typename T1, typename T2> class pair;

它有两个成员变量first（T1类型）和second（T2类型），分别表示键和其对应的值。

map的概念

map是关联容器的一种，该容器中存放元素的类型是pair。其中pair的键不能重复。

由于map的底层实现是将键按照大小存入二叉树中，以便于查询。所以存入map中的键的类型必须能够比较大小（重载<运算符或者提供比较函数指针）。

map的应用

使用map时需要包含头文件<map>以及使用命名空间std。
可以通过线上C++帮助文档获取map的各个成员函数的介绍及使用方法。
map::insert 将pair元素插入map。
map::operator[] 通过键获取对应的值，如没有键值则创建。
map::erase 通过迭代器将元素从map中删除。

示例代码

声明创建自定义Student类，新建文件Student.h,内容如下

#ifndef _STUDENT_H
#define _STUDENT_H

#include <string>
using namespace std;
class Student
{
private:
	int _id;
	string _name;

public:
	Student(const string &name, int id);
	int getId() const;
	string getName() const;
	void introduce() const;
};

#endif

实现自定义Student类方法，创建文件Student.cpp

#include "Student.h"
#include <iostream>
using namespace std;

Student::Student(const string &name, int id)
		: _name(name), _id(id)
{
}
int Student::getId() const
{
	return _id;
}
string Student::getName() const
{
	return _name;
}
void Student::introduce() const
{
	cout << "Hello!I'm " << _name << ", my id card is " << _id;
}

创建main.cpp，内容如下

string mystr(const int len) 方法是生成长度为len的随机字符串a-z。

struct myCompare 结构体用于比较Student类对象的键值大小，优先比较字符串长度，相同之后再比较学生类的_id属性。

map<Student, int, decltype(myCompareObj)> students; 定义map对象，decltype(myCompareObj) 表示使用myCompare结构体进行比较，decltype是c++11的用法，编译时要使用-std=c++11。

map对象的插入操作，先创建Student对象，再将pair<Student, int>插入到map中。

map的删除操作，通过find方法找到对应的键值，再通过erase方法删除。

#include <iostream>
#include "Student.h"
#include <map>
#include <algorithm>

string mystr(const int len)
{
  string str;
  char c;
  for (int i = 0; i < len; ++i)
  {
    c = rand() % 26 + 'a';
    str.push_back(c);
  }
  return str;
}

struct myCompare
{
  bool operator()(const Student &s1, const Student &s2)
  {
    const int len1 = s1.getName().length();
    const int len2 = s2.getName().length();
    if (len1 != len2)
    {
      return len1 > len2;
    }
    else
    {
      return s1.getId() < s2.getId();
    }
  }
} myCompareObj;

int main(int argc, char **argv)
{
  map<Student, int, decltype(myCompareObj)> students; // 学生-成绩
  int len = 0;
  for (int i = 0; i < 10; ++i)
  {
    len = rand() % 6 + 4;
    Student stu(mystr(len), i);
    pair<Student, int> p(stu, rand() % 50 + 50);
    students.insert(p);
  }

  Student stx = *(new Student("Tom Mick", 12));
  pair<Student, int> pstx(stx, rand() % 50 + 50);

  students.insert(pstx);
  cout << "insert one Student" << endl;
  cout << "==============================" << endl;
  map<Student, int, decltype(myCompareObj)>::iterator it;
  for (it = students.begin(); it != students.end(); ++it)
  {
    it->first.introduce();
    cout << " and my point is " << it->second << "." << endl;
  }

  it = students.find(stx);
  students.erase(it);
  cout << "erase one Student" << endl;
  cout << "==============================" << endl;
  for (it = students.begin(); it != students.end(); ++it)
  {
    it->first.introduce();
    cout << " and my point is " << it->second << "." << endl;
  }
  return 0;
}

在Linux下，可以使用命令g++ -g Student.cpp main.cpp -std=c++11 -o main编译运行,效果如下

insert one Student
==============================
Hello!I'm iddqscdxr, my id card is 3 and my point is 79.
Hello!I'm jybldbef, my id card is 5 and my point is 98.
Hello!I'm Tom Mick, my id card is 12 and my point is 93.
Hello!I'm yggxxpk, my id card is 7 and my point is 77.
Hello!I'm rcbyne, my id card is 6 and my point is 56.
Hello!I'm rellnm, my id card is 8 and my point is 95.
Hello!I'm wlrbb, my id card is 0 and my point is 86.
Hello!I'm zowkk, my id card is 2 and my point is 86.
Hello!I'm bhcd, my id card is 1 and my point is 90.
Hello!I'm owfr, my id card is 4 and my point is 93.
Hello!I'm pqfw, my id card is 9 and my point is 64.
erase one Student
==============================
Hello!I'm iddqscdxr, my id card is 3 and my point is 79.
Hello!I'm jybldbef, my id card is 5 and my point is 98.
Hello!I'm yggxxpk, my id card is 7 and my point is 77.
Hello!I'm rcbyne, my id card is 6 and my point is 56.
Hello!I'm rellnm, my id card is 8 and my point is 95.
Hello!I'm wlrbb, my id card is 0 and my point is 86.
Hello!I'm zowkk, my id card is 2 and my point is 86.
Hello!I'm bhcd, my id card is 1 and my point is 90.
Hello!I'm owfr, my id card is 4 and my point is 93.
Hello!I'm pqfw, my id card is 9 and my point is 64.

set简介

set的概念

set是关联容器的一种，主要用于快速地对元素进行查找。

由于set的底层实现是将键按照大小存入二叉树中，以便于查询。所以存入map中的键的类型必须能够比较大小（重载<运算符或者提供比较函数指针）。与map特性一致，set可以理解成特殊的map，即键值相同的map。

set的应用

使用set时需要包含头文件以及命名空间std;
C++帮助文档https://legacy.cplusplus.com/ 获取set的详细使用方法
set.insert 元素插入容器
set.find 查找元素
set.erase 删除元素

示例代码

这里使用的Student类，与上面map的Student类相同，这里不再赘述，这里使用set存储学生信息，并按照学生的基础信息进行排序。

重新编写main.cpp文件，内容如下

#include <iostream>
#include "Student.h"
#include <set>
#include <algorithm>

string mystr(const int len)
{
  string str;
  char c;
  for (int i = 0; i < len; ++i)
  {
    c = rand() % 26 + 'a';
    str.push_back(c);
  }
  return str;
}

struct myCompare
{
  bool operator()(const Student &s1, const Student &s2)
  {
    const int len1 = s1.getName().length();
    const int len2 = s2.getName().length();
    if (len1 != len2)
    {
      return len1 > len2;
    }
    else
    {
      return s1.getId() < s2.getId();
    }
  }
} myCompareObj;

int main(int argc, char **argv)
{
  set<Student, decltype(myCompareObj)> students;

  for (int idx = 0; idx < 10; ++idx)
  {
    int len = rand() % 5 + 5;
    Student stu(mystr(len), idx);
    students.insert(stu);
  }
  Student stux("Tom Mick", 12);
  students.insert(stux);
  cout << "insert one Student" << endl;
  cout << "==============================" << endl;
  for (auto it = students.begin(); it != students.end(); ++it)
  {
    it->introduce();
    cout << endl;
  }
  const set<Student>::iterator it1;
  auto uu = students.find(stux);
  students.erase(uu);
  cout << "erase one Student" << endl;
  cout << "==============================" << endl;
  for (auto it = students.begin(); it != students.end(); ++it)
  {
    it->introduce();
    cout << endl;
  }
  return 0;
}

编译运行，输出结果

insert one Student
==============================
Hello!I'm mowfrxsjy, my id card is 4
Hello!I'm ldbefsarc, my id card is 5
Hello!I'm wlrbbmqb, my id card is 0
Hello!I'm ynecdygg, my id card is 6
Hello!I'm Tom Mick, my id card is 12
Hello!I'm dqscdxr, my id card is 3
Hello!I'm cdarzo, my id card is 1
Hello!I'm xpklor, my id card is 7
Hello!I'm llnmpa, my id card is 8
Hello!I'm kkyhi, my id card is 2
Hello!I'm qfwkh, my id card is 9
erase one Student
==============================
Hello!I'm mowfrxsjy, my id card is 4
Hello!I'm ldbefsarc, my id card is 5
Hello!I'm wlrbbmqb, my id card is 0
Hello!I'm ynecdygg, my id card is 6
Hello!I'm dqscdxr, my id card is 3
Hello!I'm cdarzo, my id card is 1
Hello!I'm xpklor, my id card is 7
Hello!I'm llnmpa, my id card is 8
Hello!I'm kkyhi, my id card is 2
Hello!I'm qfwkh, my id card is 9