Карты в STL

Карты в С++ В этой статье мы начнем обсуждение ассоциативных контейнеров в STL. Первый такой контейнер — «Map» (карта).

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

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

Реализация карты

В STL для реализации карты нам нужно включить заголовок <map> в нашу программу:

#include<map>

Общий синтаксис объявления карты следующий:

map<key type, value type> map_name;

В этой строке, тип ключа и тип значения — это типы данных ключей и значений соответственно.

Используя приведенный выше общий синтаксис, мы можем объявить карту целочисленных ключей и значений следующим образом:

map<int, int> mymap;

Теперь мы можем инициализировать карту во время самого объявления.

Это делается следующим образом:

map<int, int> mymap {{1, 10}, {2, 20}, {3, 30}};

Приведенная выше строка кода инициализирует карту тремя парами ключ-значение.

Обратите внимание, что на карте ключ и соответствующее ему значение всегда инициализируются или вставляются парами. Нельзя добавить его как единственный ключ или единственное значение.

Операции

Вот некоторые основные операции с картой:

at и [ ]: операторы at и [ ] используются для доступа к элементам карты. Оба оператора at и [] имеют одинаковую функциональность с одним отличием. Если полученный ключ отсутствует в карте, оператор at создает исключение. Операторы [ ] вставляют новый ключ в карту, если полученный ключ отсутствует в карте.
begin: возвращает итератор к первому элементу карты.
end: возвращает итератор, указывающий на элемент после последнего элемента на карте.

Давайте рассмотрим приведенный ниже пример использования at и [ ]:

#include <iostream>
#include <map>
using namespace std;
int main()
 {
   map<int, int> mymap {{1,10},{2,20},{3,30}};
   //display the map
   map<int,int> :: iterator it;
   cout << "\nThe map mymap is : \n";
   cout << "\tKEY\tVALUE\n";
     for (it = mymap.begin(); it != mymap.end(); ++it) {
        cout << '\t' << it->first
        << '\t' << it->second << '\n';
 }
cout << endl;
mymap.at(2) = 10; //изменение значения второго элемента
mymap[3] = 10; //изменение значения третьего элемента
//отображение карты
cout << "\nThe map mymap is : \n";
cout << "\tKEY\tVALUE\n";
for (it = mymap.begin(); it != mymap.end(); ++it) {
     cout << '\t' << it->first
     << '\t' << it->second << '\n';
   }
cout << endl;
}

#include <iostream>

#include <map>

using namespace std;

int main()

{

map<int, int> mymap {{1,10},{2,20},{3,30}};

//display the map

map<int,int> :: iterator it;

cout << "\nThe map mymap is : \n";

cout << "\tKEY\tVALUE\n";

for (it = mymap.begin(); it != mymap.end(); ++it) {

cout << '\t' << it->first

<< '\t' << it->second << '\n';

}

cout << endl;

mymap.at(2) = 10; //изменение значения второго элемента

mymap[3] = 10; //изменение значения третьего элемента

//отображение карты

cout << "\nThe map mymap is : \n";

cout << "\tKEY\tVALUE\n";

for (it = mymap.begin(); it != mymap.end(); ++it) {

cout << '\t' << it->first

<< '\t' << it->second << '\n';

}

cout << endl;

}

Вывод данных:

The map mymap is :

KEY VALUE
1 10
2 20
3 30

The map mymap is :

KEY VALUE
1 10
2 10
3 10

Читать также: Цикл Repeat-Until в языке программирования Паскаль

Итак, в приведенном выше коде у нас есть карта mymap с парой ключ-значение целочисленного типа. Мы инициализировали его тремя элементами. Мы отображаем эту карту, используя функции итератора begin и end.

Затем с помощью оператора «at» мы изменяем значение второго значения, а с помощью оператора [ ] изменяем значение третьего элемента таким образом, что теперь все три элемента имеют значение 10. Это становится очевидным, когда мы снова отображаем карту после изменение значений.

insert(key, value): вставляет новый элемент (пару ключей и значений) в карту.
erase: эта операция используется для удаления элемента с карты. Она имеет две версии:
- erase(position) — здесь мы указываем позицию, на которую указывает итератор, и элемент в этой позиции удаляется.
- erase(key) — здесь мы можем указать ключ определенного элемента в качестве аргумента для функции стирания, и элемент, имеющий это конкретное значение ключа, будет удален.
empty: проверяет, пуста ли карта.
size: возвращает размер карты, т.е. количество элементов в карте.
max_size: возвращает максимальный размер, который может содержать карта.
clear: удаляет все элементы из карты.

Вот пример кода, в котором показано использование этих функций:

#include <iostream>
#include <map>
using namespace std;
int main()
{
   map<int,int> mymap;
   mymap.insert(pair<int, int>(1, 1));
   mymap.insert(pair<int, int>(2, 3));
   mymap.insert(pair<int, int>(3, 5));
   mymap.insert(pair<int, int>(4, 7));
   mymap.insert(pair<int, int>(5, 9));
   mymap.insert(pair<int, int>(6, 11));
   mymap.insert(pair<int, int>(7, 13));
   //display the map
   map<int,int> :: iterator it;
   cout << "\nThe map mymap is : \n";
   cout << "\tKEY\tVALUE\n";
   for (it = mymap.begin(); it != mymap.end(); ++it) {
      cout << '\t' << it->first
      << '\t' << it->second << '\n';
      }
   cout << endl;
   cout<<"\n mymap.size(): "<<mymap.size();
   cout<<"\n mymap.max_size(): "<<mymap.max_size();
   cout<<endl;
   int num;
   num = mymap.erase(3);
   cout << "\nmymap.erase(3) : ";
   cout << num << " removed \n";
   cout << "\tKEY\tELEMENT\n";
   for (it = mymap.begin(); it != mymap.end(); ++it) {
      cout << '\t' << it->first
      << '\t' << it->second << '\n';
      }
   cout << endl;
   mymap.clear();
   cout<<"\nAfter clear operation mymap.size() : "<<mymap.size();
}

#include <iostream>

#include <map>

using namespace std;

int main()

{

map<int,int> mymap;

mymap.insert(pair<int, int>(1, 1));

mymap.insert(pair<int, int>(2, 3));

mymap.insert(pair<int, int>(3, 5));

mymap.insert(pair<int, int>(4, 7));

mymap.insert(pair<int, int>(5, 9));

mymap.insert(pair<int, int>(6, 11));

mymap.insert(pair<int, int>(7, 13));

//display the map

map<int,int> :: iterator it;

cout << "\nThe map mymap is : \n";

cout << "\tKEY\tVALUE\n";

for (it = mymap.begin(); it != mymap.end(); ++it) {

cout << '\t' << it->first

<< '\t' << it->second << '\n';

}

cout << endl;

cout<<"\n mymap.size(): "<<mymap.size();

cout<<"\n mymap.max_size(): "<<mymap.max_size();

cout<<endl;

int num;

num = mymap.erase(3);

cout << "\nmymap.erase(3) : ";

cout << num << " removed \n";

cout << "\tKEY\tELEMENT\n";

for (it = mymap.begin(); it != mymap.end(); ++it) {

cout << '\t' << it->first

<< '\t' << it->second << '\n';

}

cout << endl;

mymap.clear();

cout<<"\nAfter clear operation mymap.size() : "<<mymap.size();

}

Вывод данных:

The map mymap is :

KEY VALUE
1 1
2 3
3 5
4 7
5 9
6 11
7 13

mymap.size(): 7
mymap.max_size(): 461168601842738790
mymap.erase(3) : 1 removed

KEY ELEMENT
1 1
2 3
4 7
5 9
6 11
7 13

After clear operation mymap.size() : 0

Читать также: Логические операторы в языке программирования Паскаль

Данная программа показывает использование различных функций для работы с картой. Видно, что после операции стирания (erase) размер карты уменьшается на 1 и становится равным 0 при выполнении очистки.

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

Мультикарта (multimap)

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

Операции, которые мы обсуждали выше для карты, также применимы и для мультикарты.

Вот измененный выше пример, демонстрирующий Multimap:

#include <iostream>
#include <map>
using namespace std;
int main()
{
   multimap<int,int> mymap;
   mymap.insert(pair<int, int>(1, 1));
   mymap.insert(pair<int, int>(2, 3));
   mymap.insert(pair<int, int>(3, 5));
   mymap.insert(pair<int, int>(3, 7));
   mymap.insert(pair<int, int>(4, 9));
   //display the map
   map<int,int> :: iterator it;
   cout << "\nThe multimap mymap is : \n";
   cout << "\tKEY\tVALUE\n";
   for (it = mymap.begin(); it != mymap.end(); ++it) {
      cout << '\t' << it->first
      << '\t' << it->second << '\n';
      }
   cout << endl;
   cout<<"\n mymap.size(): "<<mymap.size();
   cout<<"\n mymap.max_size(): "<<mymap.max_size();
   cout<<endl;
   int num;
   num = mymap.erase(3);
   cout << "\nmymap.erase(3) : ";
   cout << num << " removed \n";
   cout << "\tKEY\tELEMENT\n";
   for (it = mymap.begin(); it != mymap.end(); ++it) {
      cout << '\t' << it->first
      << '\t' << it->second << '\n';
     }
   cout << endl;
   mymap.clear();
   cout<<"\nAfter clear operation mymap.size() : "<<mymap.size();
}

#include <iostream>

#include <map>

using namespace std;

int main()

{

multimap<int,int> mymap;

mymap.insert(pair<int, int>(1, 1));

mymap.insert(pair<int, int>(2, 3));

mymap.insert(pair<int, int>(3, 5));

mymap.insert(pair<int, int>(3, 7));

mymap.insert(pair<int, int>(4, 9));

//display the map

map<int,int> :: iterator it;

cout << "\nThe multimap mymap is : \n";

cout << "\tKEY\tVALUE\n";

for (it = mymap.begin(); it != mymap.end(); ++it) {

cout << '\t' << it->first

<< '\t' << it->second << '\n';

}

cout << endl;

cout<<"\n mymap.size(): "<<mymap.size();

cout<<"\n mymap.max_size(): "<<mymap.max_size();

cout<<endl;

int num;

num = mymap.erase(3);

cout << "\nmymap.erase(3) : ";

cout << num << " removed \n";

cout << "\tKEY\tELEMENT\n";

for (it = mymap.begin(); it != mymap.end(); ++it) {

cout << '\t' << it->first

<< '\t' << it->second << '\n';

}

cout << endl;

mymap.clear();

cout<<"\nAfter clear operation mymap.size() : "<<mymap.size();

}

Вывод данных:

The multimap mymap is :

KEY VALUE
1 1
2 3
3 5
3 7
4 9

mymap.size(): 5
mymap.max_size(): 461168601842738790
mymap.erase(3) : 2 removed

KEY ELEMENT
1 1
2 3
4 9

After clear operation mymap.size() : 0

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

Обратите внимание, что в мультикарте есть два элемента с одним и тем же ключом = 3. Но поскольку это мультикарта, то это разрешено, т.к. пара ключ-значение уникальна. Затем мы отобразили размер мультикарты.

Затем мы вызвали операцию стирания на мультикарте с ключом = 3. Теперь, когда есть две записи с одним и тем же ключом, обратите внимание, что операция стирания удалила два элемента из мультикарты.

Читать также: Реляционные операторы в языке программирования Паскаль

Теперь мы рассмотрим другой вариант карты — неупорядоченную карту, т.е. unordered_map.

Неупорядоченная карта

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

Как и в карте, значение ключа используется для уникальной идентификации элемента. Типы данных ключа и сопоставленного значения могут быть предопределены или определены пользователем.

Внутренне неупорядоченная карта реализована как структура данных «Hash Table» (хэш-таблица), ключ, предоставленный для карты, хэшируется в индексы в хеш-таблице. Следовательно, производительность структуры данных во многом зависит от предоставленной хеш-функции.

Общее объявление неупорядоченной карты:

unordered_map<keyType, valueType> umap_name;

Заголовок, который необходимо включить для реализации неупорядоченной карты, — <unordered_map>.

Давайте обсудим некоторые операции, которые поддерживает unordered_map для доступа к элементам и управления ими:

begin: возвращает ссылку на первый элемент в неупорядоченной карте.
end: указывает на элемент, за которым следует последний элемент в неупорядоченной карте.
at: возвращает ссылку на значение по ключу k.
bucket: возвращает количество элементов с ключом k, которое находится на карте.
bucket_count: возвращает общее количество сегментов в неупорядоченной карте.
bucket_size: возвращает количество элементов в каждом сегменте.
count: возвращает количество элементов, присутствующих в неупорядоченной карте для данного ключа.

Давайте посмотрим пример кода, чтобы проверить использование операций неупорядоченной карты:

#include <iostream> 
#include <unordered_map> 
using namespace std; 
  int main() 
{     
    unordered_map<string, int> umap; 
   
     //вставка значений с помощью [] 
    umap["RED"] = 1; 
    umap["GREEN"] = 2; 
    umap["BLUE"] = 3; 
     
    // вставка значения с помощью функции insert 
    umap.insert(make_pair("YELLOW", 4)); 
   
    unordered_map<string, int>:: iterator it; 
    cout << "\nAll Elements in unordered map umap : \n"; 
    for (it = umap.begin(); it != umap.end(); ++it) 
    { 
         
        cout << it->first << "  " << it->second << endl; 
    } 
     
    cout<<"\numap bucket_count : "<<umap.bucket_count();
    cout<<"\nbucket_size : "<<umap.bucket_size(2);
}

#include <iostream>

#include <unordered_map>

using namespace std;

int main()

{

unordered_map<string, int> umap;

//вставка значений с помощью []

umap["RED"] = 1;

umap["GREEN"] = 2;

umap["BLUE"] = 3;

// вставка значения с помощью функции insert

umap.insert(make_pair("YELLOW", 4));

unordered_map<string, int>:: iterator it;

cout << "\nAll Elements in unordered map umap : \n";

for (it = umap.begin(); it != umap.end(); ++it)

{

cout << it->first << " " << it->second << endl;

}

cout<<"\numap bucket_count : "<<umap.bucket_count();

cout<<"\nbucket_size : "<<umap.bucket_size(2);

}

Вывод данных:

All Elements in unordered map umap :
YELLOW 4
BLUE 3
GREEN 2
RED 1
umap bucket_count : 11
bucket_size : 0

В приведенном выше коде мы объявили неупорядоченную карту и вставили в нее значения с помощью оператора [ ] и операции вставки. Затем мы отобразили карту с помощью итераторов.

Мы также объявили операции «bucket_count», которые дают общее количество сегментов в этой конкретной неупорядоченной карте (это внутренний расчет), а также «bucket_size» для значения ключа = 2.

Итог

На этом мы подошли к концу данной статьи по картам в STL. В следующей статье мы рассмотрим детали контейнера «Set» в STL.

С Уважением, МониторБанк

Реализация карты

Операции

Мультикарта (multimap)

Неупорядоченная карта

Итог

Вам также может понравиться

Введение в объектно-ориентированное программирование на C++

Типы данных С++

Деревья в C++

Добавить комментарий Отменить ответ