Заполнение std::map
От: igna Россия  
Дата: 03.12.09 09:10
Оценка: 7 (1)
При завершении программы std::map записывается в файл, из которого этот же std::map заполняется при повторном запуске программы. Что вы используете для заполнения, map::insert или map::operator[]?
Re: Заполнение std::map
От: ononim  
Дата: 03.12.09 09:12
Оценка: +1
I>При завершении программы std::map записывается в файл, из которого этот же std::map заполняется при повторном запуске программы. Что вы используете для заполнения, map::insert или map::operator[]?
смотря что мне нужно — безусловное заполнение указанными значениями или с проверкой на существование
если пофиг — использую insert как потенциально более шустрый
Как много веселых ребят, и все делают велосипед...
Re: Заполнение std::map
От: Bell Россия  
Дата: 03.12.09 09:22
Оценка: 4 (1)
Здравствуйте, igna, Вы писали:

I>При завершении программы std::map записывается в файл, из которого этот же std::map заполняется при повторном запуске программы. Что вы используете для заполнения, map::insert или map::operator[]?


По крайней мере некоторые распространенные реализации используют тот же самый insert + make_pair в реализации map::operator[]. А поскольку по условию дубликаты в файле отсутствуют, то логичнее сразу же использовать insert — элементы вставляются всегда, "холостых" вызовов make_pair нет.
Любите книгу — источник знаний (с) М.Горький
Re[2]: Заполнение std::map
От: igna Россия  
Дата: 03.12.09 09:22
Оценка:
Здравствуйте, ononim, Вы писали:

O>смотря что мне нужно — безусловное заполнение указанными значениями или с проверкой на существование


Проверка в описанном мной случае вряд ли нужна.

O>если пофиг — использую insert как потенциально более шустрый


А если речь к примеру о map<string, int>?
Re[2]: Заполнение std::map
От: ononim  
Дата: 03.12.09 09:29
Оценка:
I>>При завершении программы std::map записывается в файл, из которого этот же std::map заполняется при повторном запуске программы. Что вы используете для заполнения, map::insert или map::operator[]?
B>По крайней мере некоторые распространенные реализации используют тот же самый insert + make_pair в реализации map::operator[]. А поскольку по условию дубликаты в файле отсутствуют, то логичнее сразу же использовать insert — элементы вставляются всегда, "холостых" вызовов make_pair нет.
map::operator[] возвращает ссылку на уже вставленный (конструктором по умолчанию) объект которому потом присваивается (second.operator=) нужное значение
map::insert вставляет элемент созданный конструктором копирования из указанного, что потенциально быстрее чем создавать объект с дефолтовым конструктором и потом присваивать ему значение
Как много веселых ребят, и все делают велосипед...
Re[3]: Заполнение std::map
От: igna Россия  
Дата: 03.12.09 09:35
Оценка:
Здравствуйте, ononim, Вы писали:

O>map::insert вставляет элемент созданный конструктором копирования из указанного, что потенциально быстрее чем создавать объект с дефолтовым конструктором и потом присваивать ему значение


Верно, но это не только потенциально быстрее, но и потенциально медленнее, поскольку первый элемент вставляемой пары копируется всегда, в то время как при использовании map::operator[] реализация STL может обойтись без этого копирования.
Re[2]: Заполнение std::map
От: igna Россия  
Дата: 03.12.09 10:00
Оценка:
Здравствуйте, Bell, Вы писали:

B>По крайней мере некоторые распространенные реализации используют тот же самый insert + make_pair в реализации map::operator[]. А поскольку по условию дубликаты в файле отсутствуют, то логичнее сразу же использовать insert — элементы вставляются всегда, "холостых" вызовов make_pair нет.


И все же использование map::insert вместо map:operator[] заставляет реализацию STL лишний раз копировать ключ.
Re[4]: Заполнение std::map
От: Bell Россия  
Дата: 03.12.09 10:09
Оценка: 11 (3)
Здравствуйте, igna, Вы писали:

I>Здравствуйте, ononim, Вы писали:


O>>map::insert вставляет элемент созданный конструктором копирования из указанного, что потенциально быстрее чем создавать объект с дефолтовым конструктором и потом присваивать ему значение


I>Верно, но это не только потенциально быстрее, но и потенциально медленнее, поскольку первый элемент вставляемой пары копируется всегда, в то время как при использовании map::operator[] реализация STL может обойтись без этого копирования.


Согласен, STLPOrt5, например, использует оптимизированную версию. Более того, к минусам варианта с insert можно добавить то, что make_pair принимает аргументы и возвращает результат по значению. Насколько такое копирование критично — зависит от задачи. Если учесть, что в данном случае мы читаем из файла — относительный проигрыш из-за копирований очень сильно зависит от задачи ).

Вот небольшой примерчик:

class key
{
   int i_;
public:

   key(int i) : i_(i) { cout << "key ctor\n"; }
   key(const key& rhs) : i_(rhs.i_) { cout << "key cctor\n"; }
   key& operator=(const key& rhs) { i_ = rhs.i_; cout << "key operator=\n"; return *this; }

   friend bool operator < (const key& lhs, const key& rhs) { return lhs.i_ < rhs.i_; }
};

class value
{
   int i_;
public:

   value(int i = 0) : i_(i) { cout << "value ctor\n"; }
   value(const value& rhs) : i_(rhs.i_) { cout << "value cctor\n"; }
   value& operator=(const value& rhs) { i_ = rhs.i_; cout << "value operator=\n"; return *this; }
};

...

map<key, value> m;
key k(1);
value v(2);

...



m[k] = v;


Вывод:

key ctor
value ctor
value ctor
key cctor
value cctor
key cctor
value cctor
value operator=




m.insert(make_pair(k, v));


Вывод:

key ctor
value ctor
key cctor
value cctor
key cctor
value cctor
key cctor
value cctor
key cctor
value cctor



Но у нас же есть boost

m.insert(make_pair(boost::ref(k), boost::ref(v)));

Вывод:

key ctor
value ctor
key cctor
value cctor
key cctor
value cctor

Любите книгу — источник знаний (с) М.Горький
Re[5]: make_pair принимает аргументы по-значению
От: igna Россия  
Дата: 03.12.09 10:20
Оценка:
Здравствуйте, Bell, Вы писали:

B>Более того, к минусам варианта с insert можно добавить то, что make_pair принимает аргументы и возвращает результат по значению.


Кстати, не знаешь, аргументы-то почему по-значению?
Re[6]: make_pair принимает аргументы по-значению
От: Bell Россия  
Дата: 03.12.09 10:21
Оценка:
Здравствуйте, igna, Вы писали:

I>Здравствуйте, Bell, Вы писали:


B>>Более того, к минусам варианта с insert можно добавить то, что make_pair принимает аргументы и возвращает результат по значению.


I>Кстати, не знаешь, аргументы-то почему по-значению?

Возможно, чтобы избежать проблем с появлением "ссылки на ссылку"
Любите книгу — источник знаний (с) М.Горький
Re[2]: Заполнение std::map
От: Bell Россия  
Дата: 03.12.09 10:26
Оценка:
Здравствуйте, Bell, Вы писали:

B>По крайней мере некоторые распространенные реализации используют тот же самый insert + make_pair в реализации map::operator[].


Видимо это было давно — иначе откуда я об этом помню?
В STLPort5 и в DinkumSTL для VC7.1 map::operator[] реализован без использования make_pair...
Любите книгу — источник знаний (с) М.Горький
Re[3]: Заполнение std::map
От: igna Россия  
Дата: 03.12.09 10:34
Оценка:
Здравствуйте, Bell, Вы писали:

B>Видимо это было давно — иначе откуда я об этом помню?

B>В STLPort5 и в DinkumSTL для VC7.1 map::operator[] реализован без использования make_pair...

В VC9 тем не менее сначала конструируется map::value_type, затем при вставлении копируется в node, после чего сконструированное значение уничтожается. То есть избавились от make_pair, но избыточное копирование оставили.

    mapped_type& operator[](const key_type& _Keyval)
        {    // find element matching _Keyval or insert with default mapped
        iterator _Where = this->lower_bound(_Keyval);
        if (_Where == this->end()
            || this->comp(_Keyval, this->_Key(_Where._Mynode())))
            _Where = this->insert(_Where,
                value_type(_Keyval, mapped_type()));
        return ((*_Where).second);
        }
    };
Re[4]: Заполнение std::map
От: Bell Россия  
Дата: 03.12.09 11:00
Оценка:
Здравствуйте, igna, Вы писали:

I>В VC9 тем не менее сначала конструируется map::value_type, затем при вставлении копируется в node, после чего сконструированное значение уничтожается. То есть избавились от make_pair, но избыточное копирование оставили.


I>
I>    mapped_type& operator[](const key_type& _Keyval)
I>        {    // find element matching _Keyval or insert with default mapped
I>        iterator _Where = this->lower_bound(_Keyval);
I>        if (_Where == this->end()
I>            || this->comp(_Keyval, this->_Key(_Where._Mynode())))
I>            _Where = this->insert(_Where,
I>                value_type(_Keyval, mapped_type()));
I>        return ((*_Where).second);
I>        }
I>    };
I>


В STLPort5 и в DinkumSTL то же самое.
Любите книгу — источник знаний (с) М.Горький
Re: Заполнение std::map
От: TimurSPB Интернет  
Дата: 03.12.09 11:20
Оценка:
Здравствуйте, igna, Вы писали:

I>При завершении программы std::map записывается в файл, из которого этот же std::map заполняется при повторном запуске программы. Что вы используете для заполнения, map::insert или map::operator[]?


boost::serialization
Одним махом всю мапу сохраняет и загружает*. При бинарной сериализации работает быстро.

----
* если в мапе указатели то посложнее
Make flame.politics Great Again!
Re[2]: Заполнение std::map
От: igna Россия  
Дата: 03.12.09 11:33
Оценка:
Здравствуйте, TimurSPB, Вы писали:

TSP>boost::serialization


Честно говоря мне не задачу нужно решить, просто попался на глаза Скотт-Мейерсовский "Совет 24. Тщательно выбирайте между map::operator[] и map::insert", который (совет) в общем случае неверен.
Re: Заполнение std::map
От: Alexander G Украина  
Дата: 03.12.09 12:11
Оценка: +1
Здравствуйте, igna, Вы писали:

I>При завершении программы std::map записывается в файл, из которого этот же std::map заполняется при повторном запуске программы. Что вы используете для заполнения, map::insert или map::operator[]?


insert в цикле с результатом предыдущего insert в качестве хинта
Русский военный корабль идёт ко дну!
Re[2]: Заполнение std::map
От: igna Россия  
Дата: 03.12.09 13:15
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>insert в цикле с результатом предыдущего insert в качестве хинта


Ответ правильный, вопрос неправильный. То есть задачу я сформулировал не так, как собственно хотел. А хотел я сравнить именно map::operator[] и map::insert как это делается у Скотта Мейерса в "Совет 24. Тщательно выбирайте между map::operator[] и map::insert". Ну ладно, как сформулировано — так сформулировано, и при этой формулировке я скорее всего вообще не использовал бы insert, а написал бы итератор читающий файл и инициализировал бы map парой итераторов.
Re[6]: make_pair принимает аргументы по-значению
От: Юрий Жмеренецкий ICQ 380412032
Дата: 03.12.09 15:37
Оценка: 14 (3)
Здравствуйте, igna, Вы писали:

I>Здравствуйте, Bell, Вы писали:


B>>Более того, к минусам варианта с insert можно добавить то, что make_pair принимает аргументы и возвращает результат по значению.


I>Кстати, не знаешь, аргументы-то почему по-значению?


Library Defect Report #181

Discussion:
The claim has surfaced in Usenet that expressions such as

make_pair("abc", 3)

are illegal, notwithstanding their use in examples, because template instantiation tries to bind the first template parameter to const char (&)[4], which type is uncopyable.

I doubt anyone intended that behavior...

Proposed resolution:

In 20.2 [utility], paragraph 1 change the following declaration of make_pair():
template <class T1, class T2> pair<T1,T2> make_pair(const T1&, const T2&);

to:
template <class T1, class T2> pair<T1,T2> make_pair(T1, T2);


+ DR# 334. map::operator[] specification forces inefficient implementation
Re[7]: make_pair принимает аргументы по-значению
От: Caracrist https://1pwd.org/
Дата: 05.12.09 11:41
Оценка:
Здравствуйте, Юрий Жмеренецкий, Вы писали:

ЮЖ>Здравствуйте, igna, Вы писали:


I>>Здравствуйте, Bell, Вы писали:


B>>>Более того, к минусам варианта с insert можно добавить то, что make_pair принимает аргументы и возвращает результат по значению.


I>>Кстати, не знаешь, аргументы-то почему по-значению?


ЮЖ>

Library Defect Report #181

ЮЖ>Discussion:
ЮЖ>The claim has surfaced in Usenet that expressions such as

ЮЖ> make_pair("abc", 3)

ЮЖ>are illegal, notwithstanding their use in examples, because template instantiation tries to bind the first template parameter to const char (&)[4], which type is uncopyable.

ЮЖ>I doubt anyone intended that behavior...

ЮЖ>Proposed resolution:

ЮЖ>In 20.2 [utility], paragraph 1 change the following declaration of make_pair():
ЮЖ>template <class T1, class T2> pair<T1,T2> make_pair(const T1&, const T2&);

ЮЖ>to:
ЮЖ>template <class T1, class T2> pair<T1,T2> make_pair(T1, T2);


ЮЖ>+ DR# 334. map::operator[] specification forces inefficient implementation


Короче, кто-то поленился реализовать:

    iterator insert(const typename value_type::first_type &_First, const typename value_type::second_type& _Second);
// и трансформеры...
    template<typename T, int N>
    iterator insert(const T(&_First)[N], const typename  value_type::second_type& _Second) 
    { 
        return insert((const typename value_type::first_type)(_First),_Second);
    }
    template<typename T, int N>
    iterator insert(const  typename value_type::first_type &_First,const T(&_Second)[N]) 
    { 
        return insert(_First,(const  typename value_type::second_type )(_Second));
    }
    template<typename T1, typename T2, int N1, int N2>
    iterator insert(const T1(&_First)[N1],const T2(&_Second)[N2]) 
    { 
        return insert((const  typename value_type::first_type )(_First),(const  typename value_type::second_type )(_Second));
    }

А мы теперь с этим кривым и стандартным работаем...
~~~~~
~lol~~
~~~ Single Password Solution
Re[8]: make_pair принимает аргументы по-значению
От: Юрий Жмеренецкий ICQ 380412032
Дата: 05.12.09 12:48
Оценка:
Здравствуйте, Caracrist, Вы писали:
...
ЮЖ>>+ DR# 334. map::operator[] specification forces inefficient implementation

C>Короче, кто-то поленился реализовать:


C>
C>    iterator insert(const typename value_type::first_type &_First, const typename value_type::second_type& _Second);
C>// и трансформеры...
C>...
C>

C>А мы теперь с этим кривым и стандартным работаем...

С rvalue references все будет проще:

template <class P>
pair<iterator, bool> insert(P&& x);

...
If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it

Re[4]: Заполнение std::map
От: ArtDenis Россия  
Дата: 06.12.09 06:45
Оценка:
Здравствуйте, igna, Вы писали:

I>В VC9 тем не менее сначала конструируется map::value_type, затем при вставлении копируется в node, после чего сконструированное значение уничтожается. То есть избавились от make_pair, но избыточное копирование оставили.

Ну, если учесть, что избыточные копирования убираются оптимизатором компилятора...
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Re[5]: Заполнение std::map
От: igna Россия  
Дата: 06.12.09 09:23
Оценка:
Здравствуйте, ArtDenis, Вы писали:

AD>Ну, если учесть, что избыточные копирования убираются оптимизатором компилятора...


Действительно, компилятору разрешено убирать избыточные копирования в некоторых случаях, но рассматриваемый случай к ним не относится.
Re[8]: make_pair принимает аргументы по-значению
От: igna Россия  
Дата: 06.12.09 09:28
Оценка:
Здравствуйте, Caracrist, Вы писали:

C>А мы теперь с этим кривым и стандартным работаем...


Ну так а где в C++ или в стандартной библиотеке некриво?
Re[8]: make_pair принимает аргументы по-значению
От: gear nuke  
Дата: 08.12.09 04:36
Оценка:
Здравствуйте, Caracrist, Вы писали:

C>Короче, кто-то поленился реализовать:


C>
C>    iterator insert(const typename value_type::first_type &_First, const typename value_type::second_type& _Second);
C>// и трансформеры...
C>    template<typename T, int N>
C>    iterator insert(const T(&_First)[N], const typename  value_type::second_type& _Second) 
C>    { 
C>        return insert((const typename value_type::first_type)(_First),_Second);
C>    }
C>    template<typename T, int N>
C>    iterator insert(const  typename value_type::first_type &_First,const T(&_Second)[N]) 
C>    { 
C>        return insert(_First,(const  typename value_type::second_type )(_Second));
C>    }
C>    template<typename T1, typename T2, int N1, int N2>
C>    iterator insert(const T1(&_First)[N1],const T2(&_Second)[N2]) 
C>    { 
C>        return insert((const  typename value_type::first_type )(_First),(const  typename value_type::second_type )(_Second));
C>    }
C>

C>А мы теперь с этим кривым и стандартным работаем...

А как предлагешь поступить с завершающим '\0' в asciiz стрках?
Как быть с другими типами, где 0й элемент может иметь иной смысл?
.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.