Catalogue of series articles

preface

1, Associative container

In the initial stage, we have touched some containers in STL, such as vector, list, deque and forward_list(C++11), etc. these containers are collectively referred to as sequential containers, because their bottom layer is a linear sequence data structure, in which the elements themselves are stored. So what is an associative container? How is it different from sequential containers?

Associative containers are also used to store data. Unlike sequential containers, they store key value pairs of < key, value > structures, which is more efficient than sequential containers in data retrieval.

2, Key value pair

It is used to represent a structure with one-to-one correspondence. Generally, the structure contains only two member variables key and value. Key represents key value and value represents information corresponding to key.

For example, if we want to establish an English Chinese translation dictionary, there must be English words and their corresponding Chinese meanings in the dictionary. Moreover, the English words and their Chinese meanings are one-to-one correspondence, that is, through the corresponding words, we can find their corresponding Chinese meanings in the dictionary.

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

3, Relational container with tree structure

According to the different bucket of the application scenario, STL implements two managed containers with different structures: tree structure and hash structure. There are four kinds of relational containers with tree structure: map, set, multimap and multiset.

What these four containers have in common is that they use a balanced search tree (i.e. red black tree) as their underlying results, and the elements in the container are an ordered sequence. The following describes each container in turn.

4, Introduction and use of set

1. Introduction to set

set document

• set is a container that stores elements in a certain order.
• In the set, the value of the element also identifies it (value is the key and the type is T), and each value must be unique. Elements in set cannot be modified in the container (elements are always const), but they can be inserted or deleted from the container.
• Internally, the elements in a set are always sorted according to the specific strict weak sorting criteria indicated by its internal comparison object (type comparison).
• The set container usually accesses a single element through a key faster than unordered_set containers are slow, but they allow direct iteration of subsets in order.
• set is implemented by binary search tree (red black tree) at the bottom.
• be careful:
• Different from map/multimap, map/multimap stores real key value pairs < key, value >, and only value is placed in the set, but the bottom layer actually stores key value pairs composed of < value, value >.
• When inserting an element into set, you only need to insert value without constructing a key value pair.
• Elements in set cannot be repeated (therefore, set can be used for de duplication).
• Using the iterator of set to traverse the elements in set, we can get an ordered sequence.
• The elements in set are compared by less than by default.
• Find an element in set. The time complexity is: logN.
• The bottom layer of set is implemented by binary search tree (red black tree).

2. Use of set

1. Template parameter list of set

• T: The type of element is stored in set, and the key value pairs of < value, value > are actually stored at the bottom.
• Compare: Elements in the set are compared by less than by default.
• Alloc: the management method of element space in set, which is managed by the space configurator provided by STL.

2. Structure of set

void test_set3()
{
	set<int> s;
	s.insert(5);
	s.insert(4);
	s.insert(3);
	s.insert(6);
	s.insert(7);
	s.insert(4);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	set<int> copy(s);
	for (auto e : copy)
	{
		cout << e << " ";
	}
	cout << endl;
}

3.set capacity

void test_set2()
{
	set<int> s;
	s.insert(5);
	s.insert(4);
	s.insert(3);
	s.insert(6);
	s.insert(7);
	s.insert(4);
	cout << s.size() << endl;
	cout << s.empty() << endl;
}

4. Modification of set

The efficiency of the find algorithm of the six components in STL is O(N), while the efficiency of the find interface of set is a binary search tree, and the efficiency is logN.

5. Iterator of set

void test_set1()
{
	set<int> s;
	s.insert(5);
	s.insert(4);
	s.insert(3);
	s.insert(6);
	s.insert(7);
	s.insert(4);

	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	set<int>::iterator pos1 = s.find(3);
	if (pos1 != s.end()) //Delete only when there are elements
	{
		s.erase(pos1);
	}

	s.erase(5);
	//s.erase(100);

	set<int>::iterator pos2 = find(s.begin(), s.end(), 7);
	s.erase(pos2);

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	s.erase(s.begin(), s.end());
}

5, Introduction and use of map

1. Introduction to map

map document

• A map is an association container that stores elements composed of key values and value values in a specific order (compared by key).
• In a map, the key value key is usually used to sort and uniquely identify elements, and the value value stores the content associated with the key value key. The types of key and value may be different, and inside the map, key and value pass through the member type value_type is bound together, and the name is pair: typedef pair value_type.
• Internally, the elements in the map are always compared and sorted according to the key value key.
• Access to a single element by key value in a map is usually faster than unordered_ The map container is slow, but the map allows direct iteration of elements according to order (that is, when iterating over the elements in the map, you can get an ordered sequence).
• map supports subscript accessors, that is, by putting a key in [], you can find the value corresponding to the key.
• map is usually implemented as a binary search tree (more accurately: balanced binary search tree (red black tree)).

2. Use of map

1. Template parameter description of map

• Key: the type of key in the key value pair.
• T: The type of value in the key value pair.
• Compare: the type of comparator. The elements in the map are compared according to the key. By default, they are compared according to less than. Generally, this parameter (built-in type element) does not need to be passed. If it is impossible to compare (user-defined type), the user needs to explicitly pass the comparison rules (generally, it is passed according to the function pointer or imitation function).
• Alloc: the underlying space is applied for through the space configurator, which does not need to be passed by the user, unless the user does not want to use the space configurator provided by the standard library. Note: when using the map, the header file needs to be included.

2. Structure of map

3. Iterator of map

void test_map1()
{
	map<int, int> m;
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(2, 2));
	m.insert(pair<int, int>(3, 3));
	m.insert(make_pair(4, 4));
	map<int, int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first << ":" << it->second << endl;
		it++;
	}

	for (auto e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

4.map capacity and element access

Function declaration	Function introduction
bool empty ( ) const	Check whether the element in the map is empty. If yes, return true; otherwise, return false
size_type size() const	size_type size() const
–	–
mapped_type& operator[] (constkey_type& k)	Return the value corresponding to the key

void test_map3()  //The first method
{
	string str[] = { "watermelon", "watermelon", "pineapple", "watermelon", "watermelon", "watermelon", "Apple", "Apple" };
	map<string, int>countMap;
	for (auto& e : str)
	{
		map<string, int>::iterator pos = countMap.find(e);
		if (pos != countMap.end())
		{
			pos->second++;
		}
		else
		{
			countMap.insert(pair<string, int>(e, 1));
		}
	}

	for (auto e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}
void test_map4()
{
	string str[] = { "watermelon", "watermelon", "pineapple", "watermelon", "watermelon", "watermelon", "Apple", "Apple" };
	map<string, int>countMap;
	
	for (auto e : str)
	{
		countMap[e]++;
	}

	for (auto e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

5. Modification of map

void test_map2()
{
	map<string, string> m;

	m.insert(pair<string, string>("water", "water"));
	m.insert(pair<string, string>("apple", "Apple"));
	m.insert(make_pair("banan", "Banana"));

	map<string, string>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}

	cout << m.size() << endl;
	cout << m.empty() << endl;

	m.erase("apple");

	for (auto e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << m.size() << endl;

	map<string, string>::iterator pos1 = m.find("banan");
	if (pos1 != m.end())
	{
		m.erase(pos1);
	}
	for (auto e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << m.size() << endl;

	//map<string,string>::iterator pos2 = find(m.begin(), m.end(),"water");
	//m.erase(pos2);

	for (auto e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << m.size() << endl;
}

• [summary]:
• The elements in the map are key value pairs.
• The key in the map is unique and cannot be modified.
• By default, key s are compared by less than.
• If the elements in the map are iterated, an ordered sequence can be obtained.
• The bottom layer of map is a balanced search tree (red black tree), which has high search efficiency logN.
• The [] operator is supported, and the actual insertion search is performed in operator [].

6, Introduction and use of multiset

1. Introduction to multiset

• A multiset is a container that stores elements in a specific order, where elements can be repeated.
• In multiset, the value of the element will also recognize it (because the multiset itself stores the key value pair composed of < value, value >, so the value itself is the key, the key is the value, and the type is t) The value of the multiset element cannot be modified in the container (because the element is always const), but it can be inserted or deleted from the container.
• Internally, elements in a multiset are always sorted according to a specific strict weak sorting criterion indicated by its internal comparison rule (type comparison).
• Multiset containers typically access a single element through a key faster than unordered_ The multiset container is slow, but when traversed with an iterator, you get an ordered sequence.
• Multiset containers typically access a single element through a key faster than unordered_ The multiset container is slow, but when traversed with an iterator, you get an ordered sequence.
• [summary]:
• In the lower layer of multiset, the key value pairs of < value, value > are stored.
• mtltiset only needs to be inserted into the insertion interface.
• The difference from set is that elements in multiset can be repeated, and value in set is unique.
• Using iterators to traverse the elements in multiset can get an ordered sequence.
• Elements in a multiset cannot be modified.
• Find an element in the multiset. The time complexity is logN.
• Function of multiset: you can sort elements.

2. Use of multiset

The interface of multiset is the same as that of set.

7, Introduction and use of multimap

multimap document

1. Introduction to Multimap

• Multimaps is an associative container that stores key value pairs < key, value > mapped by key and value in a specific order, in which keys between multiple key value pairs can be repeated.
• In a multimap, elements are usually sorted and uniquely identified by key, and the mapped value stores the content associated with the key. The types of key and value may be different, through the member type value inside the multimap_ Type combined, value_type is the key value pair combining key and value: typedef pair < const key, t > value_type;
• Internally, the elements in the multimap always sort the key s according to the specified strict weak sorting criteria through their internal comparison objects.
• multimap access to a single element through a key is usually faster than unordered_ The multimap container is slow, but you can get an ordered sequence of keys by directly traversing the elements in the multimap using an iterator.
• multimap is implemented by binary search tree (red black tree) at the bottom.
  Note: the only difference between multimap and map is that the key in map is unique, while the key in multimap can be repeated.

There is no overloaded operator [] operation in the multimap (think about why?).

Because there are multiple same key values, we don't know which value of the returned key value.

summary

The above is what we want to talk about today. This paper introduces the use of associative containers map and set. Associative containers store key value data, facilitate the search of matching data, and provide a large number of functions and methods that enable us to process data quickly and conveniently. We must master them. In addition, if there are any problems above, please understand my brother's advice, but it doesn't matter. It's mainly because I can insist. I hope some students who study together can help me correct them. However, if you can be gentle, please tell me that love and peace are the eternal theme and love you.