What about inserting a map? Let’s look at the definition method of map in STL: The template < Class Key, class T, class Compare = less < The Key > Class Alloc = Alloc > The first parameter Key is the keyword type The second parameter, T, is the value type The third parameter, Compare, is the Compare function. The fourth parameter is the memory configuration object
The map internal storage mechanism is actually based on the red-black tree, which, when inserting a node, must perform the insert action at an appropriate location after matching by size. So as a keyword, at least you have to have” < The comparison operator. We know that simple keywords such as int, float, enum, size_t, and so on all have built-in comparison functions, which are fine with maps for insertion and lookup. But as a complex data type, if it is not clearly defined, < The comparison operator cannot be used directly with map unless we define a third parameter.
When selecting a map keyword, pay attention to the following two points, which are also ways to correct errors: A) Keywords clearly defined” < “Comparison operator B) There is no” < “Compare operator, a custom affine replaces the third parameter, Compare, which implements the” () “operator and provides the comparison function. When insertion, the order of each node is the class of the affine.
**STD ::pair is used as the key to blend the map **Let’s first write a function with errors, after analyzing the cause of the error, gradually correct.
#include <map>
int main()
{
std::map<std::pair<int, int>, int> res;
res.insert(std::make_pair(12,33), 33);
}This program must fail. If it must be used in this way, the above method a is obviously not suitable. STD ::pair is a defined structure that cannot be modified. Only method b can be used, and a comparison class transformation is defined as follows:
#include <map>
struct comp
{
typedef std::pair<int, int> value_type;
bool operator () (const value_type & ls, const value_type &rs)
{
return ls.first < rs.first || (ls.first == rs.first && ls.second < rs.second);
}
};
int main()
{
std::map<std::pair<int, int>, int, comp> res;
res.insert(std::make_pair(std::make_pair(12,33), 33));
res.insert(std::make_pair(std::make_pair(121,331), 331));
res.insert(std::make_pair(std::make_pair(122,332), 332));
std::map<std::pair<int, int>, int, comp>::iterator it = res.find(std::make_pair(121,331));
if (it == res.end())
printf("NULL"n");
else
printf("%d %d %d "n", it->first.first, it->first.second, it->second);
return 0;
}Inserts a map with a structure or class as the keyword
#include <map>
struct st
{
int a, b;
st():a(0), b(0){}
st(int x, int y):a(x), b(y){}
};
int main()
{
std::map<struct st, int> res;
res.insert(std::make_pair(st(1,2), 12));
res.insert(std::make_pair(st(30,4), 34));
res.insert(std::make_pair(st(5,6), 56));
std::map<struct st, int>::iterator it = res.find(st(30,4));
if (it == res.end())
printf("NULL"n");
else
printf("first:%d second:%d %d"n", it->first.a, it->first.b, it->second);
return 0;
}Compiling this program is also wrong, and the meaning is probably undefined.” < Compare functions. Since struct st is a structure defined by ourselves, we can modify this program by using the above two methods: a and b. So let’s talk about the first one, and I got it wrong the first time I modified it, and I defined the comparison function this way.
struct st
{
int a, b;
st():a(0), b(0){}
st(int x, int y):a(x), b(y){}
bool operator < (const struct st &rs) {return (this->a < rs.a || (this->a == rs.a && this->b < rs.b));}
};It is still an error to compile the program again according to this change. H :197: passing ‘const st’ as’ this’ argument of’ bool st::operator < (const st &) ‘discards the qualifiers
Why is this a problem? Let’s dive into the source code of the STL. Now that line 197 of /usr/include/c++/3.2.3/bits/stl_function.h is broken, let’s see what that line is.
193 /// One of the @link s20_3_3_comparisons comparison functors@endlink.
194 template <class _Tp>
195 struct less : public binary_function<_Tp,_Tp,bool>
196 {
197 bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }
198 };“In struct st” < “What does it really look like after compilation? Bool operator, roughly < (struct st &ls, const struct st &rs). When less calls this comparator, it is passed in const and cannot be called in non-const. Revised as follows:
struct st
{
int a, b;
st():a(0), b(0){}
st(int x, int y):a(x), b(y){}
friend bool operator < (const struct st &ls, const struct st &rs);
};
inline bool operator < (const struct st &ls, const struct st &rs)
{return (ls.a < rs.a || (ls.a == rs.a && ls.b < rs.b));}Replace the comparison operator defined inside the function with a friendly function, and STL interior is often defined in this way. What if I had to define it internally? Instead of the default less, we can use the b method to customize a comparison functor.
**The insert function returns the value **There are many functions available to insert data in the map container, and only the most common insert operation is discussed here, as defined in the STL. The pair < The iterator, bool > Insert (const value_type & x); The map container does not allow key values to be repeated, and after an insert operation, the result of the operation can be obtained with this return value. The return value is a key-value pair of an iterator that points to the element with the value in the map, and a Boolean that indicates whether the insert was successful. If the Boolean value is true, the insertion is successful, then the iterator is the position of the newly inserted value in the map. The Boolean value is false, indicating that the insert failed (the value already exists), and the iterator is the position of the original value in the map.