Learn to use the basic interface of set and map

The previous note documented the implementation of a binary search tree,Introduced in this note set 和 map,The bottom layer is implemented by a binary search tree,Let's learn the common interfaces of the two of them.

目录

set的使用

set的模板参数

insert

erase

count

lower_bound

upper_bound

multiset

count

erase

 find

键值对

map

 find

insert

make_pair

insert的返回值

operator []

重载 [] 的实现

---

set的使用

set的模板参数

T: set中存放元素的类型.
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式,使用STL提供的空间配置器管理

insert

insert是向setinsert value inside,Because the bottom layer is a binary search tree,Inorder traversal must be ordered,And there is no data redundancy,The function of deduplication can be realized：

erase

删除某个结点,和find配合使用,

find返回的是一个迭代器,Pass iterator type to delete：

You can also directly pass parameters to delete items：

count

countIt means counting,在 multi The number of occurrences of the data will be returned under the version,在普通版本下,存在就返回 1 ,不存在返回 0 ,相较于 find ,Easier to find：

lower_bound

Returns the position greater than or equal to the argument：

可以和eraseis used in conjunction with the interval deletion of ,

Removes all values ​​greater than or equal to the parameter：

upper_bound

whether or not the parameter exists,Returns all positions greater than the parameter：

可以和 lower_bound配合erase使用,Delete a closed interval of data

We are passing a closed interval,而eraseWhat is deleted is the left-closed right-open interval,使用upper_bound刚刚好：

multiset

Duplication of data is allowedset版本,The interface usage is almost identical,常用的与setThe distinguished interfaces are as follows：

count

计数接口,set版本返回的是0和1,This version returns the number of data：

erase

删除接口,set版本返回的是0和1,In this version, delete returns the number of deleted data：

 find

If you are looking for duplicate data,Returns the position of the first data traversed in inorder：

键值对

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

is such a data structure,We can use it as a node of a binary search tree

Usually only contains two member variableskey和value,key代表键值,
value表示与key对应的信息

map

 find

returns an iterator of found elements,pari 数据结构中,key_typeElements are not allowed to be modified,Also found when looking for itkey_type元素,而pair 中的第二个元素 value_type 允许修改.

因为这种性质,我们可以通过查找 key and find the corresponding value ,并且对 value 进行修改.

void test9()
{
	//Insert the following datamap中,并且计数
	string arr[] = { "马克杯", "玻璃杯", "塑料杯", "玻璃杯", "玻璃杯", "玻璃杯", "马克杯", "马克杯", "塑料杯", "玻璃杯" };
	map<string, int> m;
	for (auto& str : arr)
	{
		map<string, int>::iterator it = m.find(str);
		//找到返回的是key_type（即pair的第一个数据）的迭代器
		if (it != m.end())
		{
			it->second++;    //找到pair的second( value_type ) 自增 1 
		}
		else     //No description found,则插入
		{
			m.insert(make_pair(str, 1));
		}
	}
}

insert

The insertion is generally a key-value pair,目前需要掌握at the time of insertion键值对构造有三种：

	map<int,string> m;

	//1. 声明类型,匿名对象
	m.insert(pair<int, string>(1, "a"));

	//2. 创建对象,插入对象
	pair<int, string> kv(2, "b");
	m.insert(kv);

	//3. 调用函数模板make_pair,不用声明pair类型
	m.insert(make_pair(3, "c"));

make_pair

insert的返回值

在上面find中,我们可以通过find对 key 进行查找,并且计数,But this will repeat the lookup process twice,find先查找一次,insert This is optimized when you want to look it up once：

不用find ,直接通过 insert 也是可以实现的：

insert The one returned after successful insertionpair的类型;

此pair中的firstis an iterator for inserting elements,second是bool值;

Insert successfullypair中的second 元素设置为 true,

Insert if it already existskey,则将为 pair的second 设置为false.

相当于返回的是pair<iterator, bool>,And the iterator here is pointing to the insertionpair.

//insert 插入计数
void test10()
{
	//Insert the following datamap中,并且计数
	string arr[] = { "马克杯", "玻璃杯", "塑料杯", "玻璃杯", "玻璃杯", "玻璃杯", "马克杯", "马克杯", "塑料杯", "玻璃杯" };
	map<string, int> m;
	for (auto& str : arr)
	{
		auto ret = m.insert(make_pair(str, 1));
		if (ret.second == false)
		{
			ret.first->second++;
		}
	}
	//遍历
	auto it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}
}

operator []

在map中,上述 find 和 insert Implementing insert and count is not the easiest way to write,The best way to write it is overloading [] ：

重载 [] 的实现

那么重载的 [] 是怎么样实现的呢：

为了提高可读性,We will analyze it,如下图：

Expand the long list above,我们能清楚的看到,传进来的参数 k ,即 [] 中的 key_type 参数,On entering reload[],后,和用 insert The steps for insert count are roughly the same：

用 k 和 value An anonymous object constructorpair类型插入到map对象中;

通过insert的返回值,Get insertedpair的迭代器,Then access and return through the iteratorsecond的引用,最后进行修改.