C++_STL — map, multimap, set, multiset

It’s all done inside by red black trees

Functions (methods) mentioned in other articles in this column will not be mentioned

Reference: cplusplus

Ordered hash table

Ordered non-repeatable hash table (map) map

template < class Key, / /map::key_type
           class T, / /map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;
Copy the code

A map is an associative container that stores elements formed by combinations of key and map values in a specific order.

In a map, a key value is typically used to sort and uniquely identify elements, and a map value stores the content associated with that key. Key and map values may have different types and are combined in the member type value_type;

typedef pair<const Key, T> value_type;

Internally, elements in a map are always sorted by their keys according to the specific strict weak sorting criteria indicated by their internal comparison object (type comparison). Map and multimap red black tree (height balance tree) implementation

Map containers are generally slower than Unordered_map to access individual elements through their keys, but they allow direct iteration of subsets based on their order.

The map is usually implemented as a binary search tree.

Properties:

Elements in an associative container are referred to by their keys, not by their absolute position in the container.

The elements in the container always follow a strict order. All inserted elements specify a position in this order.

Each element associates a key with a mapped value: the key identifies the element whose primary content is the mapped value.

No two elements in a container can have equivalent keys.

Containers use allocator objects to handle their storage needs dynamically.

Parameters:

Key: indicates the key value type

T: element type

Compare: type of comparison

Alloc: allocator

constructor

The key_compare argument is a comparison function

empty (1)	explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
range (2)	template <class InputIterator> map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
copy (3)	map (const map& x);

The classcomp in the following table is also called pseudo-function

// constructing maps
#include <iostream>
#include <map>

bool fncomp (char lhs, char rhs) {returnlhs<rhs; }struct classcomp {
  bool operator(a) (const char& lhs, const char& rhs) const
  {return lhs<rhs;}
};

int main (a)
{
  std::map<char.int> first;

  first['a'] =10;
  first['b'] =30;
  first['c'] =50;
  first['d'] =70;

  std::map<char.int> second (first.begin(),first.end());

  std::map<char.int> third (second);

  std::map<char.int,classcomp> fourth;                 // class as Compare

  bool(*fn_pt)(char.char) = fncomp;
  std::map<char.int.bool(*)(char.char)> fifth (fn_pt); // function pointer as Compare

  return 0;
}
Copy the code

2, STD: : map: : equal_range

pair<const_iterator,const_iterator> equal_range (const key_type& k) const;
pair<iterator,iterator>             equal_range (const key_type& k);
Copy the code

2.1 features

Returns the boundary of a range (iterator) that contains all elements in the container with keys equivalent to k. If no match is found, the range length returned is zero, and both iterators refer to the first element with a key that is considered to be after k according to the container’s internal comparison object (key_comp).

2.2 parameter

The key to search.

2.3 the return value

pair<iterator,iterator> 
Copy the code

The first iterator is the left bound of the range, just like lower_bound. The second iterator is the right bound of upper_bound.

The function returns a pair whose members ::first is the lower bound of the range (same as lower_bound) and pair::second is the upper bound (same as upper_bound). If the mapping object is const qualified, this function returns a pair of const_iterators. Otherwise, it returns a pair of iterators. The member types iterator and const_iterator are bidirectional iterator types that refer to elements (of type value_type). Note that value_type in the map container is itself a pair type: pair<const key_type,mapped_type>.

// map::equal_range
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> mymap;

  mymap['a'] =10;
  mymap['b'] =20;
  mymap['c'] =30;

  std::pair<std::map<char.int>::iterator,std::map<char.int>::iterator> ret;
  ret = mymap.equal_range('b');

  std::cout << "lower bound points to: ";
  std::cout << ret.first->first << "= >" << ret.first->second << '\n';

  std::cout << "upper bound points to: ";
  std::cout << ret.second->first << "= >" << ret.second->second << '\n';

  return 0;
}
Copy the code

3, STD: : map: : erase

(1)	iterator erase (const_iterator position);
(2)	size_type erase (const key_type& k);
(3)	iterator erase (const_iterator first, const_iterator last);

3.1 features

Removes a single element or series of elements ([first,last)) from the map container. This effectively reduces the size of the container by removing the number of elements that are destroyed.

3.2 parameter

Position: Iterator pointing to a single element to be deleted from the map.

K: The key of the element to be removed from the map. The member type key_type is the type of the element in the container, defined in the map as an alias for its first template parameter (Key).

First, last: iterators specify the scope of the map container to delete: The member types iterator and const_iterator are bidirectional iterator types that refer to elements.

3.3 the return value

For the key-based version (2), this function returns the number of erased elements. The size_type member type is an unsigned integer type. Other versions return an iterator pointing to the element after the last element removed (or map::end, if the last element was removed).

// erasing from map
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> mymap;
  std::map<char.int>::iterator it;

  // insert some values:
  mymap['a'] =10;
  mymap['b'] =20;
  mymap['c'] =30;
  mymap['d'] =40;
  mymap['e'] =50;
  mymap['f'] =60;

  it=mymap.find('b');
  mymap.erase (it);                   // erasing by iterator

  mymap.erase ('c');                  // erasing by key

  it=mymap.find ('e');
  mymap.erase ( it, mymap.end());// erasing by range

  // show content:
  for (it=mymap.begin(a); it! =mymap.end(a); ++it) std::cout << it->first <<"= >" << it->second << '\n';

  return 0;
}
Copy the code

4, STD: : map: : the find

iterator find (const key_type& k);
const_iterator find (const key_type& k) const;
Copy the code

4.1 features

Searches the container for elements with keys equivalent to k, returning an iterator if found, otherwise returning an iterator to map::end. Another member function, map::count, can be used to check only if a particular key exists.

4.2 parameter

K: The key to search. The member type key_type is the Key type of the element in the container, defined in the map as an alias for its first template parameter (Key).

4.3 the return value

Iterator of the element if an element with the specified key is found, otherwise map::end.

// map::find
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> mymap;
  std::map<char.int>::iterator it;

  mymap['a'] =50;
  mymap['b'] =100;
  mymap['c'] =150;
  mymap['d'] =200;

  it = mymap.find('b');
  if(it ! = mymap.end())
    mymap.erase (it);

  // print content:
  std::cout << "elements in mymap:" << '\n';
  std::cout << "a => " << mymap.find('a')->second << '\n';
  std::cout << "c => " << mymap.find('c')->second << '\n';
  std::cout << "d => " << mymap.find('d')->second << '\n';

  return 0;
}
Copy the code

5, STD: : map: : count

size_type count (const key_type& k) const;
Copy the code

5.1 features

Searches the container for elements with a key equal to k using a specific key and returns the number of matches. Since all elements in the map container are unique, this function can only return 1 (if the element is found) or zero (otherwise). If the container’s comparison object reflexively returns false (that is, regardless of the order in which the keys were passed as arguments), the two keys are considered equivalent.

// map::count
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> mymap;
  char c;

  mymap ['a'] =101;
  mymap ['c'] =202;
  mymap ['f'] =303;

  for (c='a'; c<'h'; c++)
  {
    std::cout << c;
    if (mymap.count(c)>0)
      std::cout << " is an element of mymap.\n";
    else 
      std::cout << " is not an element of mymap.\n";
  }

  return 0;
}
Copy the code

6, STD: : map: : key_comp

key_compare key_comp(a) const;
Copy the code

6.1 features:

Returns a copy of the comparison object used by the container to compare key values.

6.2 the return value

Object of comparison. The member type key_compare is the type of the comparison object associated with the container and is defined in the map as an alias for its third template argument (Compare).

// map::key_comp
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> mymap;

  std::map<char.int>::key_compare mycomp = mymap.key_comp(a); mymap['a'] =100;
  mymap['b'] =200;
  mymap['c'] =300;

  std::cout << "mymap contains:\n";

  char highest = mymap.rbegin()->first;     // key value of last element

  std::map<char.int>::iterator it = mymap.begin(a);do {
    std::cout << it->first << "= >" << it->second << '\n';
  } while ( mycomp((*it++).first, highest) );

  std::cout << '\n';

  return 0;
}
Copy the code

7, STD: : map: : insert

// Insert a single element
pair<iterator,bool> insert (const value_type& val);
template <class P> pair<iterator,bool> insert (P&& val);
//with hint (2
iterator insert (const_iterator position, const value_type& val);
template <class P> iterator insert (const_iterator position, P&& val);
//range (3) // Iterator range insertion
template <class InputIterator>
  void insert (InputIterator first, InputIterator last);
//initializer list (4) Initializes the list for insertion
void insert (initializer_list<value_type> il);
Copy the code

7.1 features

Insert new elements and expand the container size

7.2 parameter

Val: The value to be copied to (or moved to) the inserted element.

Position: indicates where to insert elements. This is only a hint and does not force new elements to be inserted into the map container at that position. (Elements in the hash table always follow a specific order, depending on their keys.)

First,last: Iterators that specify the range of elements. A copy of the element in the range [first,last] is inserted into the container. Note that the range includes all elements between first and last, including elements referred to by first but not elements referred to by last. The function template argument InputIterator should be an InputIterator type that points to the element that can construct the type of the value_type object.

Il: an Initializer_List object. Insert copies of these elements. These objects are automatically constructed from the initializer list declarator. Member type value_type is the type of the element contained in the container and is defined in map as pair<const key_type,mapped_type>

7.3 the return value

The single-element version returns the newly inserted key-value pair, whose member pair::first is set to an iterator pointing to the newly inserted element or an element in the map that has an equivalent key. If a new element is inserted, the pair::second element is set to true, or false if the equivalent key already exists. The remaining versions return an iterator that points to the newly inserted element or an element in the map that already has an equivalent key

// map::insert (C++98)
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> mymap;

  // first insert function version (single parameter):
  mymap.insert ( std::pair<char.int> ('a'.100)); mymap.insert ( std::pair<char.int> ('z'.200)); std::pair<std::map<char.int>::iterator,bool> ret;
  ret = mymap.insert ( std::pair<char.int> ('z'.500));// An existing insert will fail
  if (ret.second==false) {
    std::cout << "element 'z' already existed";
    std::cout << " with a value of " << ret.first->second << '\n';
  }

  // second insert function version (with hint position):
  std::map<char.int>::iterator it = mymap.begin(a); mymap.insert (it, std::pair<char.int> ('b'.300));  // max efficiency inserting
  mymap.insert (it, std::pair<char.int> ('c'.400));  // No Max efficiency inserting // default keys to sort. C is larger than B and cannot be inserted into IT

  // third insert function version (range insertion):
  std::map<char.int> anothermap;
  anothermap.insert(mymap.begin(),mymap.find('c'));

  // showing contents:
  std::cout << "mymap contains:\n";
  for (it=mymap.begin(a); it! =mymap.end(a); ++it) std::cout << it->first <<"= >" << it->second << '\n';

  std::cout << "anothermap contains:\n";
  for (it=anothermap.begin(a); it! =anothermap.end(a); ++it) std::cout << it->first <<"= >" << it->second << '\n';

  return 0;
}
Copy the code

8, STD ::map::lower_bound, STD ::map::upper_bound

iterator lower_bound (const key_type& k);
const_iterator lower_bound (const key_type& k) const;
Copy the code

8.1 features

Lower_bound: Returns an iterator that points to a value less than or equal to K (the KEY with the largest value). The lower_bound function is the same as the algorithm’s, but is generally faster using an inner class than an outer one

Upper_bound: Returns an iterator that points to a value greater than K (the one with the smallest KEY), as lower_bound does in the algorithm, but is generally faster with the inner than the outer

8.2 parameter

K: The key to look for.

8.3 the return value

Iterator type

// map::lower_bound/upper_bound
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> mymap;
  std::map<char.int>::iterator itlow,itup;

  mymap['a'] =20;
  mymap['b'] =40;
  mymap['c'] =60;
  mymap['d'] =80;
  mymap['e'] =100;

  itlow=mymap.lower_bound ('b');  // itlow points to b
  itup=mymap.upper_bound ('d');   // itup points to e (not d!)

  mymap.erase(itlow,itup);        // erases [itlow,itup)// Delete elements in the range [itlow,itup)

  // print content:
  for (std::map<char.int>::iterator it=mymap.begin(a); it! =mymap.end(a); ++it) std::cout << it->first <<"= >" << it->second << '\n';

  return 0;
}
Copy the code

9, STD: : map: : operator =

//copy (1)	
map& operator= (const map& x);
//move (2)	
map& operator= (map&& x);
//initializer list (3)	
map& operator= (initializer_list<value_type> il);
Copy the code

9.1 features

Assign new content to the container to replace its current content.

9.2 parameter

X: An object of the same type to be assigned.

Y: List initializes objects

9.3 the return value

Dereference of the this pointer

// assignment operator with maps
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> first;
  std::map<char.int> second;

  first['x'] =8;
  first['y'] =16;
  first['z'] =32;

  second=first;                // second now contains 3 ints
  first=std::map<char.int> ();// and first is now empty

  std::cout << "Size of first: " << first.size() < <'\n';
  std::cout << "Size of second: " << second.size() < <'\n';
  return 0;
}
Copy the code

10, STD: : map: : operator []

mapped_type& operator[] (const key_type& k);
mapped_type& operator[] (key_type&& k);
Copy the code

10.1 features

If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Note that this always increases the container size by 1, even if no mapping value is assigned to the element (the element is constructed using its default constructor).

10.2 parameter

K: key

10.3 the return value

A reference to a mapped value of an element with a key equivalent to k.

// accessing mapped values
#include <iostream>
#include <map>
#include <string>

int main (a)
{
  std::map<char,std::string> mymap;

  mymap['a'] ="an element";// The default constructor is inserted, and the string is assigned
  mymap['b'] ="another element";// Insert
  mymap['c']=mymap['b'];// Insert

  std::cout << "mymap['a'] is " << mymap['a'] < <'\n';
  std::cout << "mymap['b'] is " << mymap['b'] < <'\n';
  std::cout << "mymap['c'] is " << mymap['c'] < <'\n';
  std::cout << "mymap['d'] is " << mymap['d'] < <'\n';// Insert d to call the default construct

  std::cout << "mymap now contains " << mymap.size() < <" elements.\n";

Copy the code

11, STD: : map: : swap

void swap (map& x);
Copy the code

11.1 features

Exchanging the contents of x for the contents of the container is another mapping of the same type. Sizes may vary. After this member function is called, the elements in this container are the elements in x before the call, and the elements in x are the elements in this. All iterators, references, and Pointers remain valid for swapped objects.

// swap maps
#include <iostream>
#include <map>

int main (a)
{
  std::map<char.int> foo,bar;

  foo['x'] =100;
  foo['y'] =200;

  bar['a'] =11;
  bar['b'] =22;
  bar['c'] =33;

  foo.swap(bar);

  std::cout << "foo contains:\n";
  for (std::map<char.int>::iterator it=foo.begin(a); it! =foo.end(a); ++it) std::cout << it->first <<"= >" << it->second << '\n';

  std::cout << "bar contains:\n";
  for (std::map<char.int>::iterator it=bar.begin(a); it! =bar.end(a); ++it) std::cout << it->first <<"= >" << it->second << '\n';

  return 0;
}
Copy the code

Ordered repeatable hash table multimap

Here are the main differences with Map

1. Keys are not repeated, but values can be repeated. They are stored in the order of keys and arranged in weak order, that is, from small to large

Internally, elements in a multimap are always sorted by their keys according to the specific strict weakly sorted criteria indicated by their internal comparison object (type comparison). The same key is inserted in order

2, no [] direct access element, no at()

Everything else is just like map, only slightly different, multimap

Have a sequel to the set

Here are the main differences with Map

1. There are only values, and values cannot be repeated. They are stored in the order of values, in strict weak order, that is, from small to large, and values cannot be modified (constant).

Internally, elements in a set are always sorted by their keys according to the specific strict weakly sorted criteria indicated by their internal comparison object (type comparison).

2, no [] direct access element, no at()

The rest is just like a map, with minor differences: set

Repeatable with sequels multiset

1. It is equivalent to having only values, which can be repeated, stored in the order of values, in strict weak order, that is, from small to large, and the stored values cannot be modified (constant).

Internally, elements in a multiset are always sorted by their keys according to the specific strict weakly sorted criteria indicated by their internal comparison object (type comparison). The same key is inserted in order

2, no [] direct access element, no at()

Multiset – C++ Reference (cplusplus.com)