277 / 154 / 52
Регистрация: 30.06.2011
Сообщений: 1,703
1

Изменить std::map

08.12.2019, 15:06. Показов 2101. Ответов 42
Метки нет (Все метки)

Приветствую всех. Мне на работе приходится работать не совсем со свежим компилятором С++ и такой же старенькой библиотекой STL (там даже auto_ptr не deprecated). Обновить все это хозяйство не возможно, поэтому приходится работать с тем, что есть.
Я храню в std::map объекты своего класса. Так вот столкнулся с такой неприятной вещью, что при использовании оператора [] даже для существующего элемента вызывается конструктор по умолчанию. Сделав элементарный пример и проверив его на нескольких онлайн компиляторах я убедился, что такое поведение характерно только для моей STL.
Открыв код std::map было обнаружено, что оператор [] это, по сути, обертка над методом insert. То есть, там не происходит проверки существует ли элемент, как, например, в библиотеке STL C++Builder.
Поэтому такой вопрос. Могу ли я скопировать код файла map в файл, например my_map, добавить проверку в оператор [] и использовать этот свой файл для работы с std::map? Не возникнет ли в будущем каких-то неприятностей?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.12.2019, 15:06
Ответы с готовыми решениями:

Не могу разобраться как обновить в std::map<std::string, вектор_структур>
Не могу разобраться как обновить вектор структур после его добавления в map без удаления и...

переписать std::map
Добрый вечер! Есть работающая программа, в которой используется map, все работало хорошо, но...

Вопрос по std::map
В качестве хэш-таблицы для строк (AnsiString) я использовал std::map. От таблицы мне нужно было ещё...

Обход элементов std::map в порядке их создания
Имеется ассоциативный массив и его заполнение: std::map&lt;unsigned,string&gt; arr; arr = &quot;abc&quot;; arr...

42
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
08.12.2019, 17:31 2
d7d1cd, можно искать элемент функцией map::find. Если элемент нашёлся - работаем с ним. Если итератор ==end(), то инсертим, инсерт возвращает std::pair<iterator,bool> , проверяем second==true, забираем итератор и работаем с ним

И второй вопрос - ну вызывается конструктор, что тут страшного ?
1
277 / 154 / 52
Регистрация: 30.06.2011
Сообщений: 1,703
08.12.2019, 19:03  [ТС] 3
Цитата Сообщение от Алексей1153 Посмотреть сообщение
можно искать элемент функцией map::find. Если элемент нашёлся - работаем с ним.
Это ясно, что можно так делать. Просто каждый раз вместо оператора [] придется городить поиск, проверку и т. д. Хотя, можно функцию написать для этого...
Цитата Сообщение от Алексей1153 Посмотреть сообщение
И второй вопрос - ну вызывается конструктор, что тут страшного ?
Ну так то, в общем, ничего. Просто я класс написал следуя идиоме RAII. Поэтому всякий раз при использовании оператора [] происходит ненужное выделение памяти и тут же ее освобождение.
0
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
08.12.2019, 20:36 4
d7d1cd, ну и что он там такого тяжёлого делает? Ракеты снаряжает? Если при помощи тестирования сможешь доказать, что это реально влияет на производительность, то даже тут есть выход: в дефолтном конструкторе ничего тяжёлого не делай, ресы не захватывай.

Добавлено через 1 минуту
ещё вариант - потомок от map, в нём переопределить оператор []
1
6740 / 4538 / 1840
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
08.12.2019, 21:14 5
Цитата Сообщение от d7d1cd Посмотреть сообщение
Это ясно, что можно так делать. Просто каждый раз вместо оператора [] придется городить поиск, проверку и т. д. Хотя, можно функцию написать для этого...
Напиши функцию, но только не find/insert, а воспользуйся lower_bound/insert(hint, ...), они вроде должны быть.
1
277 / 154 / 52
Регистрация: 30.06.2011
Сообщений: 1,703
09.12.2019, 09:06  [ТС] 6
Цитата Сообщение от Алексей1153 Посмотреть сообщение
в дефолтном конструкторе ничего тяжёлого не делай, ресы не захватывай.
Идет немного вразрез с RAII .

Цитата Сообщение от Алексей1153 Посмотреть сообщение
ещё вариант - потомок от map, в нём переопределить оператор []
Потомка делать от всего шаблона std::map или от его инстанцирования конкретно для моего случая (std::map<int, MyClass>)?

Добавлено через 54 секунды
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Напиши функцию, но только не find/insert, а воспользуйся lower_bound/insert(hint, ...), они вроде должны быть.
Они есть. А в чем отличие lower_bound от find?
0
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
09.12.2019, 09:21 7
Цитата Сообщение от d7d1cd Посмотреть сообщение
Идет немного вразрез с RAII
окай. Идём по твоей же ссылке в википедии

Важный случай использования RAII — «умные указатели»: классы, инкапсулирующие владение памятью. Например, в стандартной библиотеке шаблонов языка C++ для этой цели существует класс auto_ptr (заменён на unique_ptr в C++11).
я могу использовать указатель так:

C++
1
2
    std::shared_ptr<T> p;//в конструкторе нет захвата ресурса
    p.reset(new T);//тут есть
в чём именно заключается "вразрез"? Объект управляет захватом ресурса от начала захвата до деструктора (или нового reset), и неважно, когда этот захват произошёл.

Цитата Сообщение от d7d1cd Посмотреть сообщение
Потомка делать от всего шаблона
как-нибудь так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class KEY,class VAL>
class CMyMap:public std::map<KEY,VAL>
{
public:
    typedef std::map<KEY,VAL> PARENTTYPE;
 
    VAL& operator[](const KEY& key)
    {
        //в данном случае поведение оператора не изменено, вызываем оператор предка
        return PARENTTYPE::operator [](key);
    }
};
...
...
CMyMap<int,int> m;
m[4]=5;
Цитата Сообщение от d7d1cd Посмотреть сообщение
Они есть. А в чем отличие lower_bound от find?
lower_bound в данном случае тебе не нужен, используй find
1
6740 / 4538 / 1840
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
09.12.2019, 09:26 8
Цитата Сообщение от d7d1cd Посмотреть сообщение
Они есть. А в чем отличие lower_bound от find?
Если элемент не найден, find вернёт end(), и для вставки снова придётся искать позицию.
lower_bound в этом случае вернёт итератор, который можно будет использовать в качестве hint, т.е. вставка нового элемента пройдёт за константное время.

Добавлено через 4 минуты
C++
1
2
3
4
5
6
        std::map<int, std::string> items;
 
        const int val = 123;
        auto it = items.lower_bound(val);
        if (it == items.end() || it->first < val)
            items.insert(it, std::make_pair(val, "!!!!!!!!!!!"));
1
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
09.12.2019, 09:31 9
oleg-m1973, кстати, да, согласен, так нЕмного быстрее.

Только проверка it->first < val зачем, в мапе нет повторяющихся ключей
1
6740 / 4538 / 1840
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
09.12.2019, 09:47 10
Цитата Сообщение от Алексей1153 Посмотреть сообщение
Только проверка it->first < val зачем, в мапе нет повторяющихся ключей
В случае, если элеент найден, то insert вызывать не нужно. Я не знаю, как он поведёт себя в этом случае, не начнёт ли искать позицию

https://en.cppreference.com/w/... map/insert
4-6) Inserts value in the position as close as possible, just prior(since C++11), to hint
1
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
09.12.2019, 09:53 11
oleg-m1973, ну тогда уж it->first != val
1
6740 / 4538 / 1840
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
09.12.2019, 09:55 12
Цитата Сообщение от Алексей1153 Посмотреть сообщение
oleg-m1973, ну тогда уж it->first != val
Можно и так, но для единственное требование для ключей map - это чтобы у них был оператор <. Т.е. оператора != в общем случае может и не быть.
1
277 / 154 / 52
Регистрация: 30.06.2011
Сообщений: 1,703
09.12.2019, 09:58  [ТС] 13
Цитата Сообщение от Алексей1153 Посмотреть сообщение
Только проверка it->first < val зачем, в мапе нет повторяющихся ключей
Эта проверка нужна, так как it хранит то место, куда нужно вставить новый элемент. Ведь это может быть не end().
0
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
09.12.2019, 10:11 14
d7d1cd, вставка будет корректная при любом найденном it, речь сейчас идёт о предотвращении лишнего вызова конструктора. Му тут не знаем, как поведёт себя инсерт - сразу проверит, что ключ уже такой же или сначала перевставит его
0
6740 / 4538 / 1840
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
09.12.2019, 10:21 15
Цитата Сообщение от Алексей1153 Посмотреть сообщение
d7d1cd, вставка будет корректная при любом найденном it, речь сейчас идёт о предотвращении лишнего вызова конструктора. Му тут не знаем, как поведёт себя инсерт - сразу проверит, что ключ уже такой же или сначала перевставит его
Кстати, да. Я имел ввиду лишний поиск элемента в дереве, но, т.к. привык работать с emplace, то забыл, что при вызове insert тебе придётся создавать объект. Так что лучше предварительно проверить ключ.

Кстати, проверку лучше делать не при помощи оператора <, а при помощи предиката key_compare, который в map (не знаю, правда, как его здесь достать).
0
277 / 154 / 52
Регистрация: 30.06.2011
Сообщений: 1,703
09.12.2019, 14:29  [ТС] 16
Алексей1153, oleg-m1973, между выбором функция или наследование выбрал второе. То есть, по примеру Алексей1153 создаю наследника map. Код оператора [] взял из системы C++Builder:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <map>
using namespace std; 
 
template<class KEY, class VAL>
class MyMap : public map<KEY, VAL>
{
  public:
  typedef std::map<KEY, VAL> base;
  typedef typename base::mapped_type mt;
  typedef typename base::key_type kt;
  typedef typename base::iterator it;
  typedef typename base::value_type vt;
 
  mt& operator[](const kt& _Keyval)
  {
    it _Where = base::lower_bound(_Keyval);
 
    if (_Where == base::end() ||
        base::comp(_Keyval, base::_Key(_Where._Mynode())))
      _Where = base::insert(_Where, vt(_Keyval, mt()));
 
    return ((*_Where).second);
  }
};
С таким кодом все работает как надо: конструктор лишний раз не вызывается.
Скажите, а нельзя ли типы базового класса использовать напрямую? То есть, можно ли обойтись без этих строк:
C++
1
2
3
4
typedef typename base::mapped_type mt;
typedef typename base::key_type kt;
typedef typename base::iterator it;
typedef typename base::value_type vt;
0
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
09.12.2019, 14:57 17
d7d1cd, можно конечно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class KEY, class VAL>
class MyMap : public map<KEY, VAL>
{
  public:
  typedef std::map<KEY, VAL> base;
 
  typename base::mapped_type& operator[](const typename base::key_type& _Keyval)
  {
    typename base::iterator _Where = base::lower_bound(_Keyval);
 
    if (_Where == base::end() ||
        base::comp(_Keyval, base::_Key(_Where._Mynode())))
      _Where = base::insert(_Where, typename base::value_type(_Keyval, typename base::mapped_type()));
 
    return ((*_Where).second);
  }
};
1
494 / 208 / 70
Регистрация: 27.05.2016
Сообщений: 554
09.12.2019, 19:27 18
Цитата Сообщение от d7d1cd Посмотреть сообщение
между выбором функция или наследование выбрал второе
Это явно плохое решение в плане будущего саппорта кода. Меня бы точно удивило что вот этот код ведет себя не так как я ожидал:
C++
1
2
3
auto map = getMap();
map[0] = someValue; 
assert(map[0] == someValue);
1
фрилансер
3211 / 2407 / 617
Регистрация: 11.10.2019
Сообщений: 7,193
09.12.2019, 19:32 19
notAll, поведение такое же.

Впрочем, почему должно удивлять, если бы поведение было другое, ведь это другой класс
0
Комп_Оратор)
Эксперт по математике/физике
8720 / 4431 / 598
Регистрация: 04.12.2011
Сообщений: 13,301
Записей в блоге: 16
09.12.2019, 22:55 20
Цитата Сообщение от d7d1cd Посмотреть сообщение
Так вот столкнулся с такой неприятной вещью, что при использовании оператора [] даже для существующего элемента вызывается конструктор по умолчанию. Сделав элементарный пример и проверив его на нескольких онлайн компиляторах я убедился, что такое поведение характерно только для моей STL.
Покажите как вы используете этот оператор. Скорее всего проблема в том, что он вам не нужен там, где создаётся проблема.
d7d1cd, автоматическая вставка объекта в мапу по оператору индексирования - известная фича. Для того чтобы контролировать моменты когда ключ уже есть и занят используют поиск. Он возвращает итератор на пару или на конец дерева. Это совершенно нормальный приём. Он за логарифмическое время работает. Но ещё быстрее искать по lower_bound. Он когда не найдёт - предоставит итератор "подсказки" для вставки, как я помню. Это сэкономит время на вставку, если дерево большое. И последнее обстоятельство уговаривает отказаться от оператора индексирования в левой части выражения почти везде.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.12.2019, 22:55

std::string, std::fstream, ошибка кучи
где то начало вылетать при операции += с локальной переменной std::string. Заменил на свой qString....

Как проинициализировать std::stack<const int> obj ( std::stack<int>{} );
добрый день. вопрос в коде: http://rextester.com/VCVVML6656 #include &lt;iostream&gt; #include...

std::filesystem && std::asio и пр
Пытался найти хоть какие-то сроки включения всего этого в стандарт (так же ожидается lexical_cast,...

Где в настройках RAD Studio 10 Seattle изменить аргумент на -std=c99?
ребята, где в настройках RAD Studio 10 Seattle изменить аргумент на -std=c99 , что бы компилятор не...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.