С++, std::map пакости неосведомлённым. Немного об опасностях

Опубликовано 11.01.2022 | Автор: admin

Во время использования map новички или неопытные программисты могут столкнуться с некоторыми трудностями.

Для понимания темы необходимо знать:

В этой публикации будет приведено несколько примеров для демонстрации возможных угроз при работе с map:

Компаратор.
Взаимодействие с алгоритмами.
Несуществующий ключ.
Индексация

Затруднение может возникнуть при использовании своего класса (class, struct) в качестве ключа.

Чтобы использовать свой класс (class, struct) в качестве ключа — необходимо сделать так, чтобы данные класса могли сравниваться между собой.

//С++    Листинг #1     
#include <map>

struct Test{
   int x, y, z;
};

int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    m[t1] = 0;    //В качестве ключа используется структура. Ошибка! не определена операция сравнения
}

//С++ Листинг #1

#include <map>

struct Test{

int x, y, z;

};

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

m[t1] = 0; //В качестве ключа используется структура. Ошибка! не определена операция сравнения

}

По умолчанию для map определена операция сравнения <, которая перегружена во многих классах STL и доступна неклассовым типам, поэтому не требует своего явного написания, но как только дело касается собственных наших типов, то по умолчанию собственные наши типы не умеют сравнивать собственные элементы между собой, поэтому в качестве ключа наш тип должен или иметь встроенную функцию сравнения собственных данных, или быть связан внешней функцией сравнения (см. тему перегрузка операций).

Я пока что часто встречал внешнюю подгрузку операции сравнения. Внешняя используется, когда есть класс, который либо невозможно переписать, либо не имеет смысла дописывать, а в нём не предполагается операций сравнения. С такой подгрузкой видной проблемы нет (на самом деле есть (точнее, может возникнуть), но об этом позднее).

//C++	Листинг #2.1		Внешняя подгрузка операции < для сравнения ключей в map
#include <map>
#include <iostream>
#include <tuple>

using namespace std;

struct Test{
   int x, y, z;
};

bool operator <(Test left, Test right){
  return left.x < right.x && left.y < right.y && left.z < right.z;      //Сравнение со скрытой ошибкой
}

int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    Test t2 = {3, 2, 1};
    Test t3 = {2, 3, 1};
    m[t1] = 0;    //В качестве ключа используется структура. OK. Код запускается
    m[t2] = 1;    //Карта записывается
    m[t3] = 2;

    cout << m[t1] << '\n';
    cout << m[t2] << '\n';
    cout << m[t3] << '\n';
}

//C++ Листинг #2.1 Внешняя подгрузка операции < для сравнения ключей в map

#include <map>

#include <iostream>

#include <tuple>

using namespace std;

struct Test{

int x, y, z;

};

bool operator <(Test left, Test right){

return left.x < right.x && left.y < right.y && left.z < right.z; //Сравнение со скрытой ошибкой

}

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

Test t2 = {3, 2, 1};

Test t3 = {2, 3, 1};

m[t1] = 0; //В качестве ключа используется структура. OK. Код запускается

m[t2] = 1; //Карта записывается

m[t3] = 2;

cout << m[t1] << '\n';

cout << m[t2] << '\n';

cout << m[t3] << '\n';

}

Небольшая проблема может возникнуть с написанием класса под map, когда используется встроенная операция сравнения. Во-первых — это должна быть операция <, а во вторых, у map ключи константные. С константностью ключей вообще связано несколько сложностей у новичков (например, некоторые пытаются отсортировать данные структуры по ключам, но ключи в map невозможно перезаписать, т. е. нельзя их поменять местами).

//C++	Листинг #2.2		Внутренняя для класса-ключа операции < (для сравнения ключей в map)
#include <map>
#include <iostream>
#include <tuple>

using namespace std;

struct Test{
   int x, y, z;
   bool operator <(Test item) const{      //метод должен быть константным!
      return x < item.x && y < item.y && z < item.z; //Сравнение со скрытой ошибкой
   }
};



int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    Test t2 = {3, 2, 1};
    Test t3 = {2, 3, 1};
    m[t1] = 0;    //В качестве ключа используется структура. OK. Код запускается
    m[t2] = 1;    //Карта записывается
    m[t3] = 2;

    cout << m[t1] << '\n';
    cout << m[t2] << '\n';
    cout << m[t3] << '\n';
}

//C++ Листинг #2.2 Внутренняя для класса-ключа операции < (для сравнения ключей в map)

#include <map>

#include <iostream>

#include <tuple>

using namespace std;

struct Test{

int x, y, z;

bool operator <(Test item) const{ //метод должен быть константным!

return x < item.x && y < item.y && z < item.z; //Сравнение со скрытой ошибкой

}

};

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

Test t2 = {3, 2, 1};

Test t3 = {2, 3, 1};

m[t1] = 0; //В качестве ключа используется структура. OK. Код запускается

m[t2] = 1; //Карта записывается

m[t3] = 2;

cout << m[t1] << '\n';

cout << m[t2] << '\n';

cout << m[t3] << '\n';

}

Если в #2.2 сделать метод неконстантным (убрать const), то код просто не скомпилируется.

Основная проблема, которая сейчас возникла — это то, что наш map воспринимает структуры, что мы пытаемся вставить в качестве ключей, как эквивалентные, хоть среди этих структур (t1, t2, t3) нет ни одной одинаковой. Такой момент действительно может удивить неопытного человека. Дело в том, что на ключи map наложены ограничения: операция сравнения должна обеспечивать строгое сравнение (strict weak ordering), в противном случае ключи будут восприниматься как эквивалентные. А поскольку map — структура, предполагающая уникальные ключи, то любые значения ключей, воспринимаемых как эквивалентные, добавлены не будут. Кроме того, может даже произойти ub.

При нарушении обеспечения строгого сравнения (strict weak ordering) поведение программы не определено (ub)

Что такое strict weak ordering? — это математический термин для определения отношений между двумя объектами. Его определение таково:

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

Не каждый поймёт такое определение... Поэтому имейте в виду, что наша самодельная операция сравнения должна обладать такими вот свойствами:

Два ключа не могут быть меньше друг друга.

При (k1 < k2) && (k2 < k3) должно быть гарантировано, что (k1 < k3).

Если есть два ключа и ни один из них не меньше другого, то ключи эквиваленты. При (k1 eq k2) && (k2 eq k3) должно быть гарантировано, что (k1 eq k3).

Во вторых листингах (#2.1, #2.2) получается, что сравниваемые элементы взаимно меньше друг друга, поэтому вставляемые ключи считаются эквивалентными, отсюда и происходит ошибка:

Сначала в map вставляется первый ключ, поскольку нет никаких других ключей. После этого по ключам ищется позиция вставки. Для поиска позиции используется операция сравнения. Если мы взаимно сравним первые две структуры: {1, 2, 3} < {3, 2, 1}? То получим следующий результат:
(1 < 3) && (2 < 2) && (3 < 1) ==> false;
(3 < 1) && (2 < 2) && (1 < 3) ==> false;

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

Один из наиболее простых способов быстро определять эквивалентность — это использование формулы !cmp(a, b) && !cmp(b, a): если результат её true, то эквивалентность есть. Здесь cmp — это функция сравнения.

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

//C++	Листинг #2.3		Использование кортежей для операции сравнения для ключей map
#include <map>
#include <iostream>
#include <tuple>

using namespace std;

struct Test{
   int x, y, z;
   bool operator <(Test item) const{      //метод должен быть константным!
      return tie(x, y, z) < tie(item.x, item.y, item.z); //Теперь сравнение корректно
   }
};


int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    Test t2 = {3, 2, 1};
    Test t3 = {2, 3, 1};
    m[t1] = 0;    //В качестве ключа используется структура. OK. Код запускается
    m[t2] = 1;    //Карта записывается
    m[t3] = 2;

    cout << m[t1] << '\n';
    cout << m[t2] << '\n';
    cout << m[t3] << '\n';
}

//C++ Листинг #2.3 Использование кортежей для операции сравнения для ключей map

#include <map>

#include <iostream>

#include <tuple>

using namespace std;

struct Test{

int x, y, z;

bool operator <(Test item) const{ //метод должен быть константным!

return tie(x, y, z) < tie(item.x, item.y, item.z); //Теперь сравнение корректно

}

};

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

Test t2 = {3, 2, 1};

Test t3 = {2, 3, 1};

m[t1] = 0; //В качестве ключа используется структура. OK. Код запускается

m[t2] = 1; //Карта записывается

m[t3] = 2;

cout << m[t1] << '\n';

cout << m[t2] << '\n';

cout << m[t3] << '\n';

}

//C++	Листинг #2.4		Использование лексикографичекого сравнения для ключей map
#include <map>
#include <iostream>
#include <tuple>

using namespace std;

struct Test{
   int x, y, z;
   bool operator <(Test item) const{      //метод должен быть константным!
      return
        x < item.x ||
        (x == item.x && y < item.y) ||
        (x == item.x && y == item.y && z < item.z);
   }
};

int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    Test t2 = {3, 2, 1};
    Test t3 = {2, 3, 1};
    m[t1] = 0;    //В качестве ключа используется структура. OK. Код запускается
    m[t2] = 1;    //Карта записывается
    m[t3] = 2;

    cout << m[t1] << '\n';
    cout << m[t2] << '\n';
    cout << m[t3] << '\n';
}

//C++ Листинг #2.4 Использование лексикографичекого сравнения для ключей map

#include <map>

#include <iostream>

#include <tuple>

using namespace std;

struct Test{

int x, y, z;

bool operator <(Test item) const{ //метод должен быть константным!

return

x < item.x ||

(x == item.x && y < item.y) ||

(x == item.x && y == item.y && z < item.z);

}

};

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

Test t2 = {3, 2, 1};

Test t3 = {2, 3, 1};

m[t1] = 0; //В качестве ключа используется структура. OK. Код запускается

m[t2] = 1; //Карта записывается

m[t3] = 2;

cout << m[t1] << '\n';

cout << m[t2] << '\n';

cout << m[t3] << '\n';

}

Проще использовать кортежи. С ними код получается более лакончиный. Примеры взяты с форума. Чем больше внутренних переменных к сравнению, тем очевиднее, что кортежи удобны.

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

//C++	Листинг #3.1		Не все обобщённые алгоритмы работают с map
#include <map>
#include <iostream>
#include <tuple>

using namespace std;

struct Test{
   int x, y, z;
};

bool operator <(Test left, Test right){
   return tie(left.x, left.y, left.z) < tie(right.x, right.y, right.z);
}

int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    Test t2 = {3, 2, 1};
    Test t3 = {2, 3, 1};
    m[t1] = 0;    //В качестве ключа используется структура. OK. Код запускается
    m[t2] = 1;    //Карта записывается
    m[t3] = 2;

    sort(m.begin(), m.end());  //Ошибка компиляции!
}

//C++ Листинг #3.1 Не все обобщённые алгоритмы работают с map

#include <map>

#include <iostream>

#include <tuple>

using namespace std;

struct Test{

int x, y, z;

};

bool operator <(Test left, Test right){

return tie(left.x, left.y, left.z) < tie(right.x, right.y, right.z);

}

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

Test t2 = {3, 2, 1};

Test t3 = {2, 3, 1};

m[t1] = 0; //В качестве ключа используется структура. OK. Код запускается

m[t2] = 1; //Карта записывается

m[t3] = 2;

sort(m.begin(), m.end()); //Ошибка компиляции!

}

Дело в том, что sort пытается перезаписать константные ключи. Но кроме того сама операция сортировки для map не имеет смысла.

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

К ассоциативным контейнерам применимы только такие обобщённые алгоритмы, которые читают элементы (алгоритм поиска, алгоритм копирования и др.).

//C++	Листинг #4.1		Некоторые обощённые алгоритмы умеют работать с map
#include <map>
#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

struct Test{
   int x, y, z;
};

bool operator <(Test left, Test right){
   return tie(left.x, left.y, left.z) < tie(right.x, right.y, right.z);
}

int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    Test t2 = {3, 2, 1};
    Test t3 = {2, 3, 1};
    m[t1] = 0;    
    m[t2] = 1;    
    m[t3] = 2;

   vector<pair<Test, int>> v;    //Вектор пар для копирования пар из map

    copy(m.begin(), m.end(), back_inserter(v)); //Используем обобщённый алгоритм copy для map
    
    /*ОБХОДИМ ВЕКТОР ПАР*/
    for (const auto &i: v){
      cout <<  '{' << i.first.x << ',' << i.first.y << ',' << i.first.z  << '}' << "==>" << i.second  << '\n';
    }


}

//C++ Листинг #4.1 Некоторые обощённые алгоритмы умеют работать с map

#include <map>

#include <iostream>

#include <tuple>

#include <vector>

#include <algorithm>

#include <iterator>

using namespace std;

struct Test{

int x, y, z;

};

bool operator <(Test left, Test right){

return tie(left.x, left.y, left.z) < tie(right.x, right.y, right.z);

}

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

Test t2 = {3, 2, 1};

Test t3 = {2, 3, 1};

m[t1] = 0;

m[t2] = 1;

m[t3] = 2;

vector<pair<Test, int>> v; //Вектор пар для копирования пар из map

copy(m.begin(), m.end(), back_inserter(v)); //Используем обобщённый алгоритм copy для map

/*ОБХОДИМ ВЕКТОР ПАР*/

for (const auto &i: v){

cout << '{' << i.first.x << ',' << i.first.y << ',' << i.first.z << '}' << "==>" << i.second << '\n';

}

С листингом #4.1 связана одна важная техническая формальность: значения для map — это не значения second из пары, а непосредственно сами пары, а значения second лучше называть как-то иначе: вторичные значения, поля second, значения second — так вас легче поймут опытные товарищи, если возникнут трудности.

Вы часто можете слышать, что есть алгоритмы общие и есть встроенные в класс, что встроенные в класс оптимизированы для работы конкретными классами. Это можно легко принять, но иногда, особенно в начале пути, сложно понять, как это работает. На примере map можно показать один из примеров: есть обобщённый алгоритм find и встроенный в map.

//C++	Листинг #6.1		find для map
#include <map>
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

struct Test{
   int x, y, z;
};

bool operator <(const Test &left, const Test &right){
   return tie(left.x, left.y, left.z) < tie(right.x, right.y, right.z);
}

/*    (2. Перегрузка операции = для сравнения объектов Test между собой    */
bool operator ==(const Test &left, const Test &right){
   return tie(left.x, left.y, left.z) == tie(right.x, right.y, right.z);
}

/*    (1. Перегрузка = для алгоритма find)   */
bool operator ==(const pair<Test, int> key, const Test& item){
   return key.first == item;
}



int main(){
    map<Test, int> m;

    Test t1 = {1, 2, 3};
    Test t2 = {3, 2, 1};
    Test t3 = {2, 3, 1};
    m[t1] = 0;
    m[t2] = 1;
    m[t3] = 2;


   cout << find(m.begin(), m.end(), Test{3, 2, 1})->second << '\n';    //t2 ==> 1	//Долгий способ поиска
   cout << m.find(Test{3, 2, 1})->second << '\n';    				   //t2 ==> 1	//Быстрый способ поиска	   
}

//C++ Листинг #6.1 find для map

#include <map>

#include <iostream>

#include <algorithm>

#include <utility>

using namespace std;

struct Test{

int x, y, z;

};

bool operator <(const Test &left, const Test &right){

return tie(left.x, left.y, left.z) < tie(right.x, right.y, right.z);

}

/* (2. Перегрузка операции = для сравнения объектов Test между собой */

bool operator ==(const Test &left, const Test &right){

return tie(left.x, left.y, left.z) == tie(right.x, right.y, right.z);

}

/* (1. Перегрузка = для алгоритма find) */

bool operator ==(const pair<Test, int> key, const Test& item){

return key.first == item;

}

int main(){

map<Test, int> m;

Test t1 = {1, 2, 3};

Test t2 = {3, 2, 1};

Test t3 = {2, 3, 1};

m[t1] = 0;

m[t2] = 1;

m[t3] = 2;

cout << find(m.begin(), m.end(), Test{3, 2, 1})->second << '\n'; //t2 ==> 1 //Долгий способ поиска

cout << m.find(Test{3, 2, 1})->second << '\n'; //t2 ==> 1 //Быстрый способ поиска

}

В листинге #6.1 пришлось немного помочь разобраться нашему классу, как должны сравниваться элементы. Алгоритм поиска использует операцию сравнения, и, если класс не умеет выполнять сравнение, то для использования алгоритма классу нужно показать, как надо элементы сравнивать, что и было проделано. Минус использованного алгоритма в том, что при использовании обобщённого find (использован первым) все ключи перебираются последовательно, когда сама структура map — это такая структура, которая организована для эффективного, именно что для непоследовательного перебора. Встроенная функция поиска (использована второй) ищет элементы не последовательно, а специальным алгоритмом обхода map. Обычно map строятся на красно-черных деревьях, но могут быть и другие фундаменты, и для любого из способов организации map встроенная функция обхода практически всегда будет означать, что часть элементов затронута не будет (сработает во всех смыслах как молния), а это скорость работы.

Так уж вышло, что в #6.1 пришлось написать аж две перегрузки: первая перегрузка сравнивает пару pair<Test, int> и наш написанный класс Test, а вторая перегрузка, поверх этой, сравнивает объекты Test между собой.

Если есть два однотипных алгоритма: обобщённый и встроенный в объект, выбирайте всегда встроенный — встроенные алгоритмы, как правило, производительнее и умеют управлять памятью

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

Ещё один из не сложных, но не очень понятных моментов связан с тем, что если обращаться к не существующему ключу key, то может создаваться видимость, что ключ существует:

//C++	Листинг #7.1		Мусорные значения после find
#include <map>
#include <iostream>
#include <string>

using namespace std;

int main(){
   map<string, int> m;
   cout << m.find("str1")->second;  // выводится какое-то значение
}

//C++ Листинг #7.1 Мусорные значения после find

#include <map>

#include <iostream>

#include <string>

using namespace std;

int main(){

map<string, int> m;

cout << m.find("str1")->second; // выводится какое-то значение

}

Это может вызывать недоумение, из-за этого могут возникать ошибки. Но почему так происходит? Дело в том, что алгоритм find, выполняя обход, достигает позиции m.end(), а на этой позиции лежит какое-то мусорное значение, которое и получается вытащить. Мы разыменовываем мусорную область памяти — это ub.

cout << m.find("str1")->second << " | " << m.end()->second;  // выводится какое-то значение

1	cout << m.find("str1")->second << " \| " << m.end()->second; // выводится какое-то значение

Чтобы этого избегать, при использовании find нужно всегда выполнять проверку, что не была достигнута конечная позиция. Для этого зачастую удобно использовать итераторы.

Предпочитайте итераторы циклам.

//C++	Листинг #7.2		Проверяем find на конечную позицию
#include <map>
#include <iostream>
#include <string>

using namespace std;

int main(){
   setlocale(LC_ALL, "");
   map<string, int> m;


   map<string, int>::iterator it;
   it = m.find("str1");

   if (it != m.end()){
      cout << it -> second << '\n';
   } else {
      cout << "ключ str1 не найден\n";
   }
}

//C++ Листинг #7.2 Проверяем find на конечную позицию

#include <map>

#include <iostream>

#include <string>

using namespace std;

int main(){

setlocale(LC_ALL, "");

map<string, int> m;

map<string, int>::iterator it;

it = m.find("str1");

if (it != m.end()){

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

} else {

cout << "ключ str1 не найден\n";

}

Ещё один из нюансов работы с map связан с использованием операции индексирования (квадратные скобки). Совсем новичкам может казаться очень удобно использовать операцию индексирования всегда, но использование квадратных скобок черевато тем, что в map могут добавляться пары, не предназначенные для вставки, т. е. могут возникнуть разные сложности: может не скомпилироваться код, map может резко разбухнуть на пустом месте, можно словить неправильные результаты:

//C++		Листинг #8.1		Операция индексации посягает на запись в константный map
#include <iostream>
#include <map>

using namespace std;

int main(){
    const map<int, int> m = { //если убрать const, то всё ОК
      {10, 20},
      {30, 40},
      {50, 60},
    };

    cout << m[10] << '\n';
}

//C++ Листинг #8.1 Операция индексации посягает на запись в константный map

#include <iostream>

#include <map>

using namespace std;

int main(){

const map<int, int> m = { //если убрать const, то всё ОК

{10, 20},

{30, 40},

{50, 60},

};

cout << m[10] << '\n';

}

В листинге #8.2 есть массив слов (например, это фильтруемый слова) и общий массив слов. Программой выполняется подсчёт в общем массиве количества фильтруемых слов

//C++		Листинг #8.2		Раздули map
#include <iostream>
#include <map>
#include <string>

int main(){
    std::string arr[] = { "abc", "ass", "sds" };
    std::string words[] = { "asgf", "dgr", "adghs", "bddfa" };
    std::map<std::string, int> map;
    
    /*считаем слова*/
    for(const auto& s: words){ 
        ++map[s];
    }
    
    /*выводим информацию на экран*/
    for(const auto& s: arr){
        std::cout << "word: " << map[s] << "\n";
    }
    
    
}

//C++ Листинг #8.2 Раздули map

#include <iostream>

#include <map>

#include <string>

int main(){

std::string arr[] = { "abc", "ass", "sds" };

std::string words[] = { "asgf", "dgr", "adghs", "bddfa" };

std::map<std::string, int> map;

/*считаем слова*/

for(const auto& s: words){

++map[s];

}

/*выводим информацию на экран*/

for(const auto& s: arr){

std::cout << "word: " << map[s] << "\n";

}

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

//C++		Листинг #8.3		Раздули map
#include <iostream>
#include <map>

using namespace std;

int main(){
    map<int, int> m;    //Пустой map

    int count_ = 0;
    for (int i = 0; i < 1000; i++){
        if (m[i] % 100 == 0){
            ++count_;
        }
    }

    cout << count_ << '\n';   //1000 значений, делящиеся на 100!
}

//C++ Листинг #8.3 Раздули map

#include <iostream>

#include <map>

using namespace std;

int main(){

map<int, int> m; //Пустой map

int count_ = 0;

for (int i = 0; i < 1000; i++){

if (m[i] % 100 == 0){

++count_;

}

cout << count_ << '\n'; //1000 значений, делящиеся на 100!

}

Подобное #8.3 легко может написать новичок, не понимающий итераторов. Насколько помню себя, в первую пору я итераторов избегал, но использование итераторов уберегает от возникновения таких проблем, как в #8.2 и в #8.3. Понимание того, что операция индексации для map записывающая, может помочь избежать нелепых ошибок. В тех случаях, когда не нужно изменять map, следует использовать вместо операции [] встроенный в map алгоритм find.

Операция [], применяемая к map, не только ищет значение, но и вставляет его, если его в map нет.

Если map не должен дополняться несуществующими ключами, для поиска значения используйте встроенный в map алгоритм find

Активно используйте итераторы.

Чтобы исправить #8.2, нужно использовать итераторы и алгоритм find:

//C++		Листинг #8.2/1		Исправление 8.2
#include <iostream>
#include <map>
#include <string>
#include <set>    //Для того, чтоб не выводить элементы повторно

using namespace std;

int main()
{
    std::string arr[] = { "raz", "dwa", "tri", "dwa" };
    std::string words[] = { "asgf", "dwa", "adghs", "dwa" };
    std::map<std::string, int> map;
    
    
    /*Заполняем map количеством встречаемости слов*/
    for(const auto& s: words){
        ++map[s];
    }

    set<string> s{begin(arr), end(arr)};  //уникализируем массив, чтобы не выводить одинаковые результаты
    
    
    /*Обходим уникализированный массив s для анализа встречаемости его слов в words*/
    for(const auto& i: s){
        auto it = map.find(i);      //Используем итератор для обнаружения слова и применяем find
         if (it != map.end()){      //Основываясь на результате find, выводим результаты
            cout << it->first << ' ' << it->second << '\n';
         } else {
            //cout << i << ' ' << '0' << '\n';
         }
    }
}

//C++ Листинг #8.2/1 Исправление 8.2

#include <iostream>

#include <map>

#include <string>

#include <set> //Для того, чтоб не выводить элементы повторно

using namespace std;

int main()

{

std::string arr[] = { "raz", "dwa", "tri", "dwa" };

std::string words[] = { "asgf", "dwa", "adghs", "dwa" };

std::map<std::string, int> map;

/*Заполняем map количеством встречаемости слов*/

for(const auto& s: words){

++map[s];

}

set<string> s{begin(arr), end(arr)}; //уникализируем массив, чтобы не выводить одинаковые результаты

/*Обходим уникализированный массив s для анализа встречаемости его слов в words*/

for(const auto& i: s){

auto it = map.find(i); //Используем итератор для обнаружения слова и применяем find

if (it != map.end()){ //Основываясь на результате find, выводим результаты

cout << it->first << ' ' << it->second << '\n';

} else {

//cout << i << ' ' << '0' << '\n';

}

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

Листинг #8.3 можно легко исправить, если делать обход итераторами:

//C++		Листинг #8.3/1		Исправление 8.3
#include <iostream>
#include <map>

using namespace std;

int main(){
    map<int, int> m;    //Пустой map

    int count_ = 0;
    for (const auto &i: m){      //Тип i автоматически будет приведён к итератору
        if (i.second % 100 == 0){
            ++count_;
        }
    }

    cout << count_ << '\n';   //OK
}

//C++ Листинг #8.3/1 Исправление 8.3

#include <iostream>

#include <map>

using namespace std;

int main(){

map<int, int> m; //Пустой map

int count_ = 0;

for (const auto &i: m){ //Тип i автоматически будет приведён к итератору

if (i.second % 100 == 0){

++count_;

}

cout << count_ << '\n'; //OK

}

Рубрика: map, STL, Базовые знания, level "classer", Знакомства, Типы

С++, std::map пакости неосведомлённым. Немного об опасностях

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

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета