Map

Map или "ассоциативный массив" – общий случай для массивов. Когда в привычном массиве ключём для доступа к элементу служит номер в диапазоне $0, 1, \dots, n-1$, в Map ключём может быть что угодно.

In [1]:
#include <iostream>
#include <map>
#include <unordered_map>

typedef unsigned long long ull
In [2]:
void print_map(const std::map<std::string, int>& m)
{
    std::cout << "map {" << std::endl;
    for (auto it : m)
    {
        std::cout << it.first << " " << it.second << std::endl;
    }
    std::cout << "}" << std::endl;
}
In [3]:
void print_map(const std::map<int, std::string>& m)
{
    std::cout << "map {" << std::endl;
    for (auto [key, value] : m)
    {
        std::cout << key << " " << value << std::endl;
    }
    std::cout << "}" << std::endl;
}
In [4]:
{
    std::map<std::string,int> m = {{"first",4},{"second",3},{"third",9}};
    print_map(m);
    std::map<int,std::string> m2 = {{2,"two"},{0,"zero"},{9,"nine"}};
    print_map(m2);
}
map {
first 4
second 3
third 9
}
map {
0 zero
2 two
9 nine
}

--std=c++14 --std=c++17 g++ --std=c++17 file.cpp

In [5]:
{
    std::map<std::string,int> m; 
    m["first"] = 4; 
    m["second"] = 3; 
    m["third"] = 9;
    print_map(m);
    
    std::cout << m["second"] << std::endl;
}
map {
first 4
second 3
third 9
}
3
In [6]:
{
    std::pair<int, int> point(2,3);
    std::cout << "X = " << point.first << " Y = " << point.second << std::endl;
}
X = 2 Y = 3
In [7]:
{
    std::pair<int, std::pair<int, int>> point(2,{3, 4});
    std::cout << "X = " << point.first << " Y = " << point.second.first << " Z = " << point.second.second << std::endl;
}
X = 2 Y = 3 Z = 4
In [8]:
{
    std::map<std::string,int> m;
    m.insert(std::pair<std::string, int>("first",4));
    m.insert({"second",3}); 
    m.insert({"third",9}); 

    print_map(m);
}
map {
first 4
second 3
third 9
}
In [9]:
std::map<int, std::string> reverse(const std::map<std::string, int>& m){
    std::map<int, std::string> result;
    for (auto item : m) {
        result[item.second] = item. first;
    }
    return result;
}
In [10]:
{
    std::map<std::string,int> m = {{"first",4},{"second",3},{"third",4}};
    print_map(m);
    
    auto r = reverse(m);
    print_map(r);
}
map {
first 4
second 3
third 4
}
map {
3 second
4 third
}

Значения std::map в C++ отсортированы по ключу. Из-за этого доступ к элементу гарантировано происходит за $O(\log(n))$.

Структура Добавление Дотсуп Удаление Поиск
std::map $$O(\log{n})$$ $$O(\log{n})$$ $$O(\log{n})$$ $$O(\log{n})$$

Это возможно благодаря использованию Красно-Чёроного дерева, как основы std::map. Подробнее тут: Красно-черные деревья: коротко и ясно.

Автоматическое добавление при первом обращении по ключу

In [11]:
{
    std::string index = "first";
    std::map<std::string, int> m;
    
    std::cout << "Пустой map:" << std::endl;
    print_map(m);
    
    std::cout << "Но при обращении к элементу с индексом " << index  << " " << m[index] << std::endl;
    print_map(m);
}
Пустой map:
map {
}
Но при обращении к элементу с индексом first 0
map {
first 0
}

Задача Каждый участник кружка "БинПоиск" получает "плюсик в карму" за каждое хорошее дело, которое он сделал. Каждый раз, получая плюсик, имя участника записывается в массив. Найдите человека с самой большой "кармой".

In [12]:
{
    std::vector<std::string> transactions = {"Лёша","Маша", "Катя", "Сириус", "Андрей", 
                                "Коля", "Миша","Маша", "Катя", 
                                "Маша", "Катя", "Катя", "Коля"};
    std::map<std::string, int> m;
    
    for (auto n : transactions) {
        m[n]++;
    }
    
    print_map(m);
    
    auto max = m.begin()->second;
    auto max_key = m.begin()->first;
    for (auto n : m){
        if(n.second > max) {
            max = n.second;
            max_key = n.first;
        }
    }
    
    std::cout << "----" << std::endl 
        << "Max value is" << std::endl 
        << max_key << " = " << max << std::endl;
}
map {
Андрей 1
Катя 4
Коля 2
Лёша 1
Маша 3
Миша 1
Сириус 1
}
----
Max value is
Катя = 4

Обращение к элементу с проверкой

In [13]:
{
    std::string index = "first";
    std::map<std::string, int> m;
    try {
        auto element = m.at(index);
        std::cout << "Element at index " << index << " = " << element << std::endl;
    }
    catch(std::out_of_range ex) {
        std::cout << "Error 'std::out_of_range' occured while looking for an element with index = " 
            << index << std::endl;
    }
    
    m[index]++;
    std::cout << m.count(index);
}
Error 'std::out_of_range' occured while looking for an element with index = first
1

Поиск элемента

In [14]:
{
    std::string index = "first";
    std::map<std::string, int> m;
    
    if(m.find(index) != m.end()){
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }   
}
Not found

Удаление элементов

Одного элемента

In [15]:
{
    std::map<std::string,int> m = {{"first",4},{"second",3},{"third",9}};
    print_map(m);
    
    std::cout << "-----" << std::endl;
    m.erase("third");
    print_map(m);
}
map {
first 4
second 3
third 9
}
-----
map {
first 4
second 3
}

Диапазон элементов

In [16]:
{
    std::map<std::string,int> m = {{"first",4},{"second",3},{"third",9}};
    print_map(m);
    
    std::cout << "-----" << std::endl;
    m.erase(m.begin(), m.find("third"));
    print_map(m);
}
map {
first 4
second 3
third 9
}
-----
map {
third 9
}

Всех элементов

In [17]:
{
    std::map<std::string,int> m = {{"first",4},{"second",3},{"third",9}};
    print_map(m);
    
    std::cout << "-----" << std::endl;
    m.clear();
    print_map(m);
}
map {
first 4
second 3
third 9
}
-----
map {
}

Map без сортировки

sdt::unordered_map – особый вид ассоциативного массива. Элементы в нём не отсортированы и после добавления могут быть расположены в любом порядке.

Реализован std::unordered_map как Hash-таблица.

Структура Добавление Дотсуп Удаление Поиск
std::map $$O(\log{n})$$ $$O(\log{n})$$ $$O(\log{n})$$ $$O(\log{n})$$
std::unordered_map Амортизировано $$O(1),$$ в худшем случае $$O(n)$$ Амортизировано $$O(1),$$ в худшем случае $$O(n)$$ Амортизировано $$O(1),$$ в худшем случае $$O(n)$$ Амортизировано $$O(1),$$ в худшем случае $$O(n)$$

Благодаря этому свойству мы можем решить задачу быстрее, используя std::unordered_map вместо std::map.

In [18]:
void print_map(const std::unordered_map<std::string, int>& m)
{
    std::cout << "map {" << std::endl;
    for (auto it : m)
    {
        std::cout << it.first << " " << it.second << std::endl;
    }
    std::cout << "}" << std::endl;
}
In [19]:
{
    std::vector<std::string> transactions = {"Маша", "Лёша", "Сириус", "Андрей", 
                                "Коля", "Миша","Маша", "Лёша", 
                                "Маша", "Лёша", "Лёша", "Коля"};
    std::unordered_map<std::string, int> m;
    
    for (auto n : transactions) {
        m[n]++;
    }
    
    print_map(m);
    
    auto max = m.begin()->second;
    auto max_key = m.begin()->first;
    for (auto n : m){
        if(n.second > max) {
            max = n.second;
            max_key = n.first;
        }
    }
    
    std::cout << "----" << std::endl 
        << "Max value is" << std::endl 
        << max_key << " = " << max << std::endl;
}
map {
Лёша 4
Миша 1
Маша 3
Сириус 1
Андрей 1
Коля 2
}
----
Max value is
Лёша = 4

Интерфейсы std::map и std::unordered_map похожи в базовых функциях добавления, удаления и поиска элементов, которые мы рассмотрели, но отличается в деталях, тесно связанных со структурами данных, стоящими в основе реализации.

Например

При задании std::map можно также указать компаратор – функцию сравнения двух ключей. Этот компаратор будет использован для сортировки записей.

У std::unordered_map нет компаратора, но есть возможность указать функцию хеширования.

Подробнее

Queue, Priority Queue

queue

Очередь (Queue) – структура данных, которая предоставляет 2 стандартных метода:

  • добавление элемента в конец очереди
  • удаление элемента из начала очереди
Структура Добавление Дотсуп Удаление Поиск
std::queue $$O(1)$$ для последнего элемента $$O(1)$$ для верхнего элемента $$O(1)$$ для верхнего элемента
In [20]:
#include <queue>
In [21]:
void print_queue(std::queue<unsigned long long>& q){
    std::cout << "queue {";
    while(!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << "}" << std::endl;
}
In [22]:
{
    std::queue<unsigned long long> q;
    
    q.push(3); 
    q.push(2); 
    q.push(5); 
    
    std::cout << q.front() << std::endl;
    q.pop(); 
    std::cout << q.front() << std::endl;
    
    print_queue(q);
}
3
2
queue {2 5 }

Задача:

Есть массив, содержащий время t звонков на кафедру ПМ. Необходимо вывести все звонки за последние 3000 секунд. $$0 \leq t \leq 8 446 744 073 709 551 615.$$

In [23]:
{
    std::vector<unsigned long long> rings = {1, 2, 300, 7600, 7700};
    std::queue<unsigned long long> recent_calls;
    
    for(auto r : rings) {
        recent_calls.push(r);
        if (r >= 3000) {
            while(recent_calls.front() < r - 3000) {
                recent_calls.pop();
            }
        }
    }
    
    print_queue(recent_calls);
}
queue {7600 7700 }

priority_queue

Очередь с приоритетами (Priority Queue) – очередь, в которой нарушается принцип "Первый пришёл – первый ушёл" (FIFO). Такая очередь поддерживает операции:

  • добавления элемента,
  • получения минимального(максимального) элемента очереди.
Структура Добавление Дотсуп Удаление Поиск
std::queue $$O(1)$$ для последнего элемента $$O(1)$$ для верхнего элемента $$O(1)$$ для верхнего элемента
std::priority_queue $$O(\log{n})$$ $$O(1)$$ $$O(\log{n})$$

Описание класса на http://cppreference.com выглядит следующим образом:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Где:

  • T - тип хранимых элементов.
  • Container - тип контейнера, в котором очередь будет хранить элементы. Контейнер должен поддерживать следующие методы:

    • front()
    • push_back()
    • pop_back() Такими контейнерами могут быть std::vector и std::deque. По умолчанию используется std::vector
  • Compare - тип компаратора, осуществляющего нестрогое упорядочевание. Уметь нестрого упорядочить – значит уметь обрабатывать ситуацию, когда два элемента равны.

По умолчанию очередь отсортирована по убыванию.

In [24]:
template <typename T>
void print_queue(T& q){
    std::cout << "priority_queue {";
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << "}" << std::endl;
}
In [25]:
{
    std::priority_queue<ull> pq;
    pq.push(70);
    pq.push(1);
    pq.push(24);
    pq.push(0);
    print_queue(pq);
}
priority_queue {70 24 1 0 }

Так можно задать обратный порядок очереди, а заодно и указать тип контейнера, который ляжет в её основу.

В качестве компаратора можно явно указывать

  • std::less<T> – сортирует по убыванию,
  • std::greater<T> – сортирует по возрастанию,

где T – тип данных

In [26]:
{
    std::priority_queue<ull, std::vector<ull>, std::greater<ull>> pq;
    pq.push(70);
    pq.push(1);
    pq.push(24);
    pq.push(0);
    print_queue(pq);
}
priority_queue {0 1 24 70 }

Также компараторы можно задавать и для std::map и для std::set.

Где ещё используются компараторы можно почитать на странице описания требований Cpp Refference: Compare

Задача:

Поздравляем, у тебя день рождения! В кармане 100 рублей и, руководствуясь пословицей, ты решаешь отпраздновать с друзьями и купить всем мороженного! Но вот проблема, каждый любит свой вид мороженного. Какое максимальное количество друзей ты можешь получить за 100 рублей?

Формат входных данных

m n
<n цен мороженного>

Ограничения:

$1 \leq m \leq 1 * 10^{18}$ – количество денег в кармане

$1 \leq n \leq 1 * 10^6$ – количество потенциальных друзей

$ 1 \leq s_i \leq 1 * 10^{18}$

In [27]:
{
    std::vector<ull> v = {99,9,1,2,5,6,8,1,2,3,6,3,5,8,15,17,24,5,4,55,6,7};
    std::priority_queue<ull, std::vector<ull>, std::greater<ull>> pq;
    ull m = 100;
    ull f = 0;
    
    for(auto s : v){
        pq.push(s);
    }
    
    while(m>0 and pq.top()<=m){
        m -= pq.top();
        pq.pop();
        f++;
    }
    
    std::cout << f << std::endl;
}
18