C++ => станд :: Карта

замечания

Чтобы использовать любой из std::map или std::multimap должен быть включен заголовочный файл <map> .
std::map и std::multimap обе сохраняют свои элементы отсортированными в соответствии с возрастающим порядком ключей. В случае std::multimap сортировка не производится для значений одного и того же ключа.
Основное различие между std::map и std::multimap заключается в том, что std::map не позволяет дублировать значения для того же ключа, где std::multimap .
Карты реализованы как двоичные деревья поиска. Таким образом, search() , insert() , erase() занимает среднее время (log n). Для работы с постоянным временем используйте std::unordered_map .
Функции size() и empty() имеют временную сложность Θ (1), количество узлов кэшируется, чтобы избежать ходьбы по дереву каждый раз, когда вызывается эти функции.

Доступ к элементам

std::map принимает (key, value) пары в качестве входных данных.

Рассмотрим следующий пример инициализации std::map :

std::map < std::string, int > ranking { std::make_pair("stackoverflow", 2), 
                                        std::make_pair("docs-beta", 1) };

На std::map элементы можно вставить следующим образом:

ranking["stackoverflow"]=2;
ranking["docs-beta"]=1;

В приведенном выше примере, если ключевой stackoverflow уже присутствует, его значение будет обновлено до 2. Если он еще не присутствует, будет создана новая запись.

На std::map элементы можно получить напрямую, указав ключ как индекс:

std::cout << ranking[ "stackoverflow" ] << std::endl;

Обратите внимание, что использование operator[] на карте фактически введет новое значение с запрошенным ключом в карту. Это означает, что вы не можете использовать его на const std::map , даже если ключ уже сохранен на карте. Чтобы предотвратить эту установку, проверьте, существует ли элемент (например, с помощью find() ) или используйте его at() как описано ниже.

C ++ 11

К элементам std::map можно обращаться с помощью at() :

std::cout << ranking.at("stackoverflow") << std::endl;

Обратите внимание, что at() будет std::out_of_range исключение std::out_of_range если контейнер не содержит запрошенный элемент.

В обоих контейнерах std::map и std::multimap , элементы могут быть доступны с помощью итераторов:

C ++ 11

// Example using begin()
std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                         std::make_pair(1, "docs-beta"),
                                         std::make_pair(2, "stackexchange")  };
auto it = mmp.begin();
std::cout << it->first << " : " << it->second << std::endl; // Output: "1 : docs-beta"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackoverflow"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackexchange"

// Example using rbegin()
std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                    std::make_pair(1, "docs-beta"),
                                    std::make_pair(2, "stackexchange")  };
auto it2 = mp.rbegin();
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "2 : stackoverflow"
it2++;
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "1 : docs-beta"

Инициализация std :: map или std :: multimap

std::map и std::multimap оба могут быть инициализированы путем предоставления пар ключ-значение, разделенных запятой. Ключи-значения могут быть предоставлены либо {key, value} либо могут быть явно созданы с помощью std::make_pair(key, value) . Поскольку std::map не позволяет дублировать ключи, а оператор запятой выполняет справа налево, пара справа будет перезаписана парой с одним и тем же ключом слева.

std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                     std::make_pair(1, "docs-beta"),
                                     std::make_pair(2, "stackexchange")  };
// 1 docs-beta
// 2 stackoverflow
// 2 stackexchange

std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                std::make_pair(1, "docs-beta"),
                                std::make_pair(2, "stackexchange")  }; 
// 1 docs-beta
// 2 stackoverflow

Оба могут быть инициализированы итератором.

// From std::map or std::multimap iterator
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {6, 8}, {3, 4}, 
                               {6, 7} };
                       // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 8}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); //moved cursor on first {6, 5}
std::map< int, int > mp(it, mmp.end()); // {6, 5}, {8, 9}

//From std::pair array
std::pair< int, int > arr[10];
arr[0] = {1, 3};
arr[1] = {1, 5};
arr[2] = {2, 5};
arr[3] = {0, 1};
std::map< int, int > mp(arr,arr+4); //{0 , 1}, {1, 3}, {2, 5}

//From std::vector of std::pair
std::vector< std::pair<int, int> > v{ {1, 5}, {5, 1}, {3, 6}, {3, 2} };
std::multimap< int, int > mp(v.begin(), v.end()); 
                        // {1, 5}, {3, 6}, {3, 2}, {5, 1}

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

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

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
mmp.clear(); //empty multimap

Удаление элемента из где-то с помощью итератора:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); // moved cursor on first {6, 5}
mmp.erase(it); // {1, 2}, {3, 4}, {3, 4}, {6, 7}, {8, 9}

Удаление всех элементов в диапазоне:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
auto it2 = it;
it++; //moved first cursor on first {3, 4}
std::advance(it2,3);  //moved second cursor on first {6, 5}
mmp.erase(it,it2); // {1, 2}, {6, 5}, {6, 7}, {8, 9}

Удаление всех элементов, имеющих заданное значение в качестве ключа:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
mmp.erase(6); // {1, 2}, {3, 4}, {3, 4}, {8, 9}

Удаление элементов, которые удовлетворяют предикату pred :

std::map<int,int> m;
auto it = m.begin();
while (it != m.end())
{
   if (pred(*it))
       it = m.erase(it);
   else
       ++it;
}

Вставка элементов

Элемент может быть вставлен в std::map только если его ключ еще не присутствует на карте. Дано, например:

std::map< std::string, size_t > fruits_count;

Пара ключ-значение вставляется в std::map через функцию-член insert() . Для этого требуется pair в качестве аргумента:
```
fruits_count.insert({"grapes", 20});
fruits_count.insert(make_pair("orange", 30));
fruits_count.insert(pair<std::string, size_t>("banana", 40));
fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50));
```
Функция insert() возвращает pair состоящую из итератора и значения bool :
- Если вставка прошла успешно, итератор указывает на вновь вставленный элемент, а значение bool равно true .
- Если уже был элемент с одним и тем же key , вставка не выполняется. Когда это происходит, итератор указывает на элемент, вызывающий конфликт, а значение bool равно false .
Для комбинирования операций вставки и поиска можно использовать следующий метод:
```
auto success = fruits_count.insert({"grapes", 20});
if (!success.second) {           // we already have 'grapes' in the map
    success.first->second += 20; // access the iterator to update the value
}
```
Для удобства контейнер std::map предоставляет оператору индексирования доступ к элементам на карте и вставлять новые, если они не существуют:
```
fruits_count["apple"] = 10;
```
Хотя это проще, он не позволяет пользователю проверить, существует ли элемент уже. Если элемент отсутствует, std::map::operator[] неявно создает его, инициализируя его конструктором по умолчанию, прежде чем перезаписывать его с указанным значением.

insert() может быть использована для добавления нескольких элементов одновременно с использованием скопированного списка пар. Эта версия insert () возвращает void:
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```
insert() также может использоваться для добавления элементов с помощью итераторов, обозначающих значения начала и конца value_type :
```
std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}};
fruits_count.insert(fruit_list.begin(), fruit_list.end()); 
```

Пример:

std::map<std::string, size_t> fruits_count;
std::string fruit;
while(std::cin >> fruit){
    // insert an element with 'fruit' as key and '1' as value
    // (if the key is already stored in fruits_count, insert does nothing)
    auto ret = fruits_count.insert({fruit, 1});
    if(!ret.second){            // 'fruit' is already in the map 
        ++ret.first->second;    // increment the counter
    }
}

Сложность времени для операции вставки - O (log n), поскольку std::map реализованы как деревья.

C ++ 11

pair может быть построена явно с использованием make_pair() и emplace() :

std::map< std::string , int > runs;
runs.emplace("Babe Ruth", 714);
runs.insert(make_pair("Barry Bonds", 762));

Если мы знаем, где будет вставлен новый элемент, мы можем использовать emplace_hint() чтобы указать hint итератора. Если новый элемент можно вставить непосредственно перед hint , то вставка может быть выполнена в постоянное время. В противном случае он ведет себя так же, как emplace() :

std::map< std::string , int > runs;
auto it = runs.emplace("Barry Bonds", 762); // get iterator to the inserted element
// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it, "Babe Ruth", 714);

Итерация по std :: map или std :: multimap

std::map или std::multimap может быть пройден следующими способами:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                               
//Range based loop - since C++11
for(const auto &x: mmp) 
    std::cout<< x.first <<":"<< x.second << std::endl;

//Forward iterator for loop: it would loop through first element to last element
//it will be a std::map< int, int >::iterator
for (auto it = mmp.begin(); it != mmp.end(); ++it)
std::cout<< it->first <<":"<< it->second << std::endl; //Do something with iterator

//Backward iterator for loop: it would loop through last element to first element
//it will be a std::map< int, int >::reverse_iterator
for (auto it = mmp.rbegin(); it != mmp.rend(); ++it)
std::cout<< it->first <<" "<< it->second << std::endl; //Do something with iterator

При повторении по std::map или std::multimap использование auto предпочтительнее, чтобы избежать бесполезных неявных преобразований (подробнее см. Этот ответ SO ).

Поиск в std :: map или в std :: multimap

Существует несколько способов поиска ключа в std::map или в std::multimap .

Чтобы получить итератор первого вхождения ключа, можно использовать функцию find() . Он возвращает end() если ключ не существует.

  std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
  auto it = mmp.find(6);
  if(it!=mmp.end())
      std::cout << it->first << ", " << it->second << std::endl; //prints: 6, 5
  else
      std::cout << "Value does not exist!" << std::endl;

  it = mmp.find(66);
  if(it!=mmp.end())
      std::cout << it->first << ", " << it->second << std::endl; 
  else
      std::cout << "Value does not exist!" << std::endl; // This line would be executed.

Другой способ определить, существует ли запись в std::map или в std::multimap , используется функция count() , которая подсчитывает, сколько значений связано с данным ключом. Поскольку std::map связывает только одно значение с каждым ключом, функция count() может возвращать только 0 (если ключ отсутствует) или 1 (если есть). Для std::multimap count() может возвращать значения, превышающие 1, поскольку может быть несколько значений, связанных с одним и тем же ключом.
```
 std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
 if(mp.count(3) > 0) // 3 exists as a key in map
     std::cout << "The key exists!" << std::endl; // This line would be executed.
 else
     std::cout << "The key does not exist!" << std::endl;
```
Если вам все равно, существует ли какой-то элемент, find будет строго лучше: он документирует ваше намерение, и для multimaps он может остановиться после обнаружения первого совпадающего элемента.
В случае std::multimap может быть несколько элементов, имеющих один и тот же ключ. Чтобы получить этот диапазон, используется equal_range() которая возвращает std::pair имеющую нижнюю границу итератора (включительно) и верхнюю границу (исключая) соответственно. Если ключ не существует, оба итератора будут указывать на end() .
```
  auto eqr = mmp.equal_range(6);
  auto st = eqr.first, en = eqr.second;
  for(auto it = st; it != en; ++it){
      std::cout << it->first << ", " << it->second << std::endl; 
  }
      // prints: 6, 5
      //         6, 7
```

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

Контейнер std::map имеет функцию-член empty() , которая возвращает true или false , в зависимости от того, пуста или нет карта. Элемент функции size() возвращает число элементов, хранящихся в std::map :

std::map<std::string , int> rank {{"facebook.com", 1} ,{"google.com", 2}, {"youtube.com", 3}};
if(!rank.empty()){
    std::cout << "Number of elements in the rank map: " << rank.size() << std::endl;
}
else{
    std::cout << "The rank map is empty" << std::endl;
}

Типы карт

Регулярная карта

Карта представляет собой ассоциативный контейнер, содержащий пары ключ-значение.

#include <string>
#include <map>
std::map<std::string, size_t> fruits_count;

В приведенном выше примере std::string - это тип ключа , а size_t - значение .

Ключ действует как индекс на карте. Каждый ключ должен быть уникальным и должен быть заказан.

Если вам нужны mutliple элементы с одним и тем же ключом, рассмотрите возможность использования multimap (объяснено ниже)
Если ваш тип значения не указывает какой-либо заказ или вы хотите переопределить порядок по умолчанию, вы можете указать его:
```
#include <string>
#include <map>
#include <cstring>
struct StrLess {
    bool operator()(const std::string& a, const std::string& b) {
        return strncmp(a.c_str(), b.c_str(), 8)<0;
               //compare only up to 8 first characters
    }
}
std::map<std::string, size_t, StrLess> fruits_count2;
```
Если компаратор StrLess возвращает false для двух ключей, они считаются одинаковыми, даже если их фактическое содержимое отличается.

Multi-Map

Multimap позволяет хранить несколько пар ключ-значение с одним и тем же ключом на карте. В противном случае его интерфейс и создание очень похожи на обычную карту.

 #include <string>
 #include <map>
 std::multimap<std::string, size_t> fruits_count;
 std::multimap<std::string, size_t, StrLess> fruits_count2;

Хэш-карта (неупорядоченная карта)

В хэш-карте хранятся пары ключ-значение, аналогичные обычной карте. Однако он не упорядочивает элементы по отношению к ключу. Вместо этого хэш- значение для ключа используется для быстрого доступа к необходимым парам ключ-значение.

#include <string>
#include <unordered_map>
std::unordered_map<std::string, size_t> fruits_count;

Неупорядоченные карты обычно быстрее, но элементы не сохраняются в каком-либо предсказуемом порядке. Например, итерация по всем элементам в unordered_map дает элементы в кажущемся случайном порядке.

Создание std :: map с определяемыми пользователем типами как ключ

Чтобы иметь возможность использовать класс в качестве ключа на карте, все, что требуется от ключа, состоит в том, что оно может быть copiable и assignable . Порядок в карте определяется третьим аргументом шаблона (и аргументом для конструктора, если он используется). По умолчанию используется std::less<KeyType> , по умолчанию используется оператор < , но нет необходимости использовать значения по умолчанию. Просто напишите оператор сравнения (желательно как функциональный объект):

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

В C ++ предикат «сравнить» должен быть строгим слабым порядком . В частности, compare(X,X) должно возвращать false для любого X т.е. если CmpMyType()(a, b) возвращает true, то CmpMyType()(b, a) должен возвращать значение false, а если оба возвращают false, то элементы считаются равными (членами одного и того же класса эквивалентности).

Строгий слабый порядок

Это математический термин для определения отношения между двумя объектами.
Его определение:

Два объекта x и y эквивалентны, если оба f (x, y) и f (y, x) ложны. Заметим, что объект всегда (по инварианту нерефлексивности) эквивалентен самому себе.

В терминах C ++ это означает, что если у вас есть два объекта данного типа, вы должны вернуть следующие значения по сравнению с оператором <.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

То, как вы определяете эквивалент / меньше, полностью зависит от типа вашего объекта.

Modified text is an extract of the original Stack Overflow Documentation

Лицензировано согласно CC BY-SA 3.0

Не связан с Stack Overflow

C++
станд :: Карта

Поиск…

замечания

Доступ к элементам

Инициализация std :: map или std :: multimap

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

Вставка элементов

Итерация по std :: map или std :: multimap

Поиск в std :: map или в std :: multimap

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

Типы карт

Регулярная карта

Multi-Map

Хэш-карта (неупорядоченная карта)

Создание std :: map с определяемыми пользователем типами как ключ

Строгий слабый порядок