Kaidzu.com
Таймеры
Си
C++
Python
Миландр- map или словарь это контейнер для хранения сортированных уникальных записей - пары ключ-значение. Подключается через #include <map>
- Сортировка происходит по ключу.
- Ключи должны быть уникальны. При добавлении записи с существующим ключом - добавляемая запись будет потеряна.
- Ключ не обязательно целое число, может быть строкой и т.д.
- map основан на красно-черных деревьях и поиск, вставка и удаление в нем осуществляются за логарифмическое время OLog(N).
- Для использования сортированных неуникальных записей по ключу, используйте контейнер std::multimap.
- Для использования несортированных уникальных записей по ключу, используйте контейнер std::unordered_map.
- Для использования несортированных неуникальных записей по ключу, используйте контейнер std::unordered_multimap.
| Метод | Описание | Пример | Сложность |
|---|---|---|---|
| value_type& [const key_type& k] | Доступ к элементу по КЛЮЧУ. | auto i = mp.[20]; | O(logN) |
| value_type& at(const key_type& k) | Доступ к элементу по ключу. Выбрасывает исключение при отсутствии ключа. | auto i = mp.at(20); | O(logN) |
| begin() | Возвращает итератор на первый элемент. | cout << mp.begin()->first; | O(1) |
| clear() | Удаляет все элементы map. | mp.clear(); | O(n) |
| count(const key_type& k) | Возвращает количество элементов, 0 или 1 | size_t cnt = mp.count("hoba"); | O(1) |
| emplace(key_type k, value_type value) | Вставляет значение пару ключ-значение в map. При совпадении ключа значение не меняется. | mp.emplace(8, "buba"); | O(logN) |
| emplace_hint(iterator it, key_type k, value_type value) | Вставляет значение пару ключ-значение перед итератором map. При совпадении ключа значение не меняется. | mp.emplace_hint(mp.begin(), 8, "buba"); | O(1) O(logN) |
| empty() | Возвращает пустой ли map. | if(!mp.empty()); | O(1) |
| end() | Возвращает итератор на место после последнего элемента. | auto i = mp.end(); | O(1) |
| erase(const key_type& k) | Удаляет элемент с заданным ключом. | mp.erase(3); | O(n) |
| erase(iterator pos) | Удаляет элемент с заданным итератором. | mp.erase(mp.begin()); | O(1) |
| erase(iterator it_begin, iterator it_end) | Удаляет элементы в заданном диапазоне итераторов. | mp.erase(++mp.begin(), mp.end()); | O(n) |
| find() | Возвращает итератор на элемент по ключу или std::end(). | auto i = mp.find(5); | O(1) |
| insert(initializer_list<value_type<g il) | Вставляет элемент. Если ключ уже существует - значение не меняется. | mp.insert({2, "cow"}); | O(logN) |
| insert_or_assign(const key_type& k, value_type&& value) | Вставляет элемент. Если ключ уже существует - значение заменяется. Возвращает итератор на элемент. С++17 | auto it = mp.insert_or_assign(2, "cow"); | O(logN) |
| map | Конструктор без аргументов. Создает новый пустой map. | map<int, string> mp; | O(1) |
| map(initializer_list<value_type> il) | Конструктор. Создает map из списка инициализации. | map<int, string> mp{{5, "ara"}, {3, "dog"}, {1, "cat"}}; | O(n) |
| map(iterator it_start, iterator it_stop) | Конструктор. Создает map из диапазона итераторов другого контейнера. | map mp1(++mp.begin(), mp.end()); | O(n) |
| map(const map mp) | Конструктор копирования. Создает map со значениями mp | map mp1(mp); map<int, string> mp1(mp); | O(n) |
| max_size() | Возвращает максимально возможный размер map. | size_t msize = mp.max_size(); //128102389400760775 | O(1) |
| lower_bound(const Key& key ); | Возвращает итератор на элемент с ключом не меньше (>=) аргумента, или end() при отсутствии. | auto it = mp.lower_bound(3); | O(logN) |
| rbegin() | Возвращает реверсивный итератор на конец map. | auto i = mp.rbegin(); | O(1) |
| rend() | Возвращает реверсивный итератор на начало map. | auto i = mp.rend(); | O(1) |
| swap(map& v2) | Обменивает содержимое mapов | mp.swap(v2); | O(1) |
| upper_bound(const Key& key ); | Возвращает итератор на элемент с ключом больше (>) аргумента, или end() при отсутствии. | auto it = mp.upper_bound(3); | O(logN) |
#include <iostream> // cout
#include <map> // map
using namespace std;
int main() {
map<string, int> m_empty; // Создание словаря
map<string, int> m_si_test = {{"Apple", 1}, {"Orange", -15}, {"Nut", 5}}; // Создание словаря
map<string, int> m_si{{"Apple", 1}, {"Orange", 15}, {"Nut", 5}}; // Создание словаря
map<int, int> m_ii{{1, 1}, {2, 4}, {3, 9}}; // Создание словаря
map<string, string> m_ss{{"hey", "hop"}, {"la", "la"}, {"ley", "ka"}}; // Создание словаря
m_si["Peach"] = 10; // Добавление элемента в словарь(ключ - строка, значение - int)
m_ii[4] = 16; // Добавление элемента в словарь(ключ - int, значение - int)
m_ss["huba"] = "buba"; // Добавление элемента в словарь(ключ - строка, значение - строка)
m_ii.erase(3); // Удаление записи с ключом 3
m_ii.erase(3); // Можно удалять несуществующие ключи
m_si.erase("Orange"); // Удаление записи с ключом "Orange"
cout << m_si["Nut"] << endl; //5 Обращение к значению по ключу
cout << m_ii[3] << endl; //9
cout << m_ss["hey"] << endl; //hop
if(m_ss.count("para") == 1){ // Поиск по ключу в словаре count(key) возвращает 0 или 1-если найдено совпадение
cout << "para find in key"; //
}
for(auto iter = m_ss.begin(); iter != m_ss.end(); iter++){ // Перебор словаря через итераторы
cout << iter->first << "_" << iter->second << " "; //hey_hop huba_buba la_la ley_ka
}
cout << endl;
for (const auto& [fruct, price] : m_si){ // Перебор словаря
cout << fruct << "_" << price << " "; //Apple_1 Nut_5 Peach_10
}
cout << endl;
}
