c++11 standard template (STL) std::map (2)

std::map is an ordered key-value pair container, the key of its elements is unique. Sort keys with comparison function Compare. Search, remove, and insert operations have logarithmic complexity. Maps are usually implemented as red-black trees.

In every place where the standard library uses the Compare concept, uniqueness is checked with an equivalence relation. Imprecisely, if two objects a and b are not smaller than each other when compared: !comp(a, b) & amp; & amp; !comp (b, a) , they are considered equivalent (not unique).

std::map satisfies Container (Container), AllocatorAwareContainer (AllocatorAwareContainer), AssociativeContainer (AssociativeContainer ) and Reversible Container (ReversibleContainer) requirements.

Member function

Construct map

std::map<Key,T,Compare,Allocator>::map

Constructs a new container from various data sources, optionally using a user-supplied allocator alloc or a comparison function object comp .

1) Constructs an empty container.

2) Construct the container so that it has content in the range [first, last). If multiple elements in the range have keys that compare equivalent, it is unspecified which element is inserted (pending LWG2844 ).

3) Copy constructor. Constructs the container so that it has a copy of the contents of other. If alloc is not provided, an allocator is obtained by calling std::allocator_traits::select_on_container_copy_construction(other.get_allocator()).

4) Move constructor. Constructs the container with move semantics to have the content of other. If alloc is not provided, the allocator is move-constructed from an allocator belonging to other

5) Construct the container so that it has the content of initializer_list init. If multiple elements in the range have keys that compare equivalent, it is unspecified which element is inserted (pending LWG2844 ).

parameter

Complexity

1) Constant.

2) N log(N), where N = std::distance(first, last) usually, if the range has been sorted by value_comp(), it will be equal to N linear.

3) Linear in size of other.

4) Constant. Linear if alloc is given and alloc != other.get_allocator().

5) N log(N), which usually has N = init.size()), if init has been sorted according to value_comp(), it will be the same as N code> into linear.

Exception

A call to Allocator::allocate may throw.

Destruct map

std::map<Key,T,Compare,Allocator>::~map

Destroy the container. The element’s destructor is called, then the used storage is deallocated. Note that if the element is a pointer, the pointed object is not destroyed.

Complexity

Linear in container size.

Call example

#include <iostream>
#include <forward_list>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <map>
#include <time.h>

using namespace std;

struct Cell
{
    int x;
    int y;

    Cell() = default;
    Cell(int a, int b): x(a), y(b) {}

    Cell & amp; operator + =(const Cell & amp; cell)
    {
        x + = cell.x;
        y + = cell.y;
        return *this;
    }

    Cell & amp; operator + (const Cell & amp; cell)
    {
        x + = cell.x;
        y + = cell.y;
        return *this;
    }

    Cell & amp; operator *(const Cell & amp; cell)
    {
        x *= cell.x;
        y *= cell.y;
        return *this;
    }

    Cell & operator + + ()
    {
        x + = 1;
        y + = 1;
        return *this;
    }


    bool operator <(const Cell & cell) const
    {
        if (x == cell.x)
        {
            return y < cell.y;
        }
        else
        {
            return x < cell.x;
        }
    }

    bool operator >(const Cell & cell) const
    {
        if (x == cell.x)
        {
            return y > cell.y;
        }
        else
        {
            return x > cell.x;
        }
    }

    bool operator ==(const Cell & cell) const
    {
        return x == cell.x & amp; & amp; y == cell.y;
    }
};

struct myCompare
{
    bool operator()(const int & amp; a, const int & amp; b)
    {
        return a < b;
    }
};

std::ostream & amp;operator<<(std::ostream & amp;os, const Cell & amp;cell)
{
    os << "{" << cell.x << "," << cell.y << "}";
    return os;
}

std::ostream & amp;operator<<(std::ostream & amp;os, const std::pair<const int, Cell> & amp;pCell)
{
    os << pCell.first << "-" << pCell.second;
    return os;
}

int main()
{
    auto genKey = []()
    {
        return std::rand() % 10 + 100;
    };

    auto generate = []()
    {
        int n = std::rand() % 10 + 100;
        Cell cell{n, n};
        return cell;
    };

    //1) Construct an empty container.
    std::map<int, Cell> map1;
    std::cout << "map1 is empty: " << map1.empty() << std::endl;
    for (size_t index = 0; index < 5; index ++ )
    {
        map1.insert({genKey(), generate()});
    }
    std::cout << std::endl;

    //2) Construct the container so that it has the content of the range [first, last).
    std::map<int, Cell> map2(map1.begin(), map1.end());
    std::cout << "map2: ";
    std::copy(map2.begin(), map2.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    // reverse order
    std::map<int, Cell, std::greater<int>> map8(map1.begin(), map1.end());
    std::cout << "map8: ";
    std::copy(map8.begin(), map8.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::cout << std::endl;

    //3) Copy constructor. Constructs the container so that it has a copy of the contents of other.
    std::map<int, Cell> map3(map2);
    std::cout << "map3: ";
    std::copy(map3.begin(), map3.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::map<int, Cell, std::greater<int>> map9(map8);
    std::cout << "map9: ";
    std::copy(map9.begin(), map9.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::cout << std::endl;

    //4) Move constructor. Constructs a container with move semantics to have the contents of other.
    std::map<int, Cell> map4(std::move(map2));
    std::cout << "map4: ";
    std::copy(map4.begin(), map4.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::cout << "map2(move) is empty: " << map2.empty() << std::endl;
    std::map<int, Cell, std::greater<int>> map10(std::move(map8));
    std::cout << "map10: ";
    std::copy(map10.begin(), map10.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::cout << "map8(move) is empty: " << map10.empty() << std::endl;
    std::cout << std::endl;

    //5) Construct the container so that it has the content of initializer_list init.
    std::map<int, Cell> map5({<!-- -->{genKey(), generate()}, {genKey(), generate()},
        {genKey(), generate()}, {genKey(), generate()}, {genKey(), generate()}});
    std::cout << "map5: ";
    std::copy(map5.begin(), map5.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::map<int, Cell, std::greater<int>> map11({<!-- -->{genKey(), generate()}, {genKey(), generate()},
        {genKey(), generate()}, {genKey(), generate()}, {genKey(), generate()}});
    std::cout << "map11: ";
    std::copy(map11.begin(), map11.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::cout << std::endl;

    //Use the system key comparison function
    std::map<int, Cell, std::greater<int>> map6({<!-- -->{genKey(), generate()}, {genKey(), generate()},
        {genKey(), generate()}, {genKey(), generate()}, {genKey(), generate()}});
    std::cout << "map6: ";
    std::copy(map6.begin(), map6.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    std::cout << std::endl;

    //Use a custom key comparison function
    std::map<int, Cell, myCompare> map7({<!-- -->{genKey(), generate()}, {genKey(), generate()},
        {genKey(), generate()}, {genKey(), generate()}, {genKey(), generate()}});
    std::cout << "map7: ";
    std::copy(map7.begin(), map7.end(), std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));
    std::cout << std::endl;
    return 0;
}

Output