Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.94/34: Рейтинг темы: голосов - 34, средняя оценка - 4.94
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462

Алгоритм copy, back_inserter и vector

18.07.2016, 14:25. Показов 7323. Ответов 16
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте. Решил подробней пройтись по STL. Заинтересовал такой момент. Применяю алгоритм copy к вектору и копирую его элементы в самого себя с помощью back_inserter.
Почему программа работает? Ведь при вставке изменился объем вектора и итераторы в ходе copy стали невалидными.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <iterator>
 
#include <vector>
 
using namespace std;
 
int main()
{
    vector<int> coll{ 1, 2, 3, 4, 5 };
 
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << coll.capacity() << endl;
 
    copy(coll.begin(), coll.end(), back_inserter(coll));
 
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << coll.capacity() << endl;
 
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
18.07.2016, 14:25
Ответы с готовыми решениями:

copy, iterator, vector
#include &lt;istream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;iterator&gt; int main( ) { std::vector &lt;int&gt;...

алгоритм copy
copy(v.begin(), v.end(), ostream_iterator&lt;char&gt;(cout, &quot; &quot;)); - копирует последовательность v.begin(), v.end() в выходной поток, а как...

Алгоритм copy
У меня есть вектор указателей vector&lt;cString *&gt; (cString - это мой класс), подскажите, можно ли вывести вектор в консоль, однако нужно что...

16
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
18.07.2016, 14:43
HenryDukart, подозреваю, что begin и end запоминаются один раз для копи. Да, потом их значения меняются, но копи использует "старые" записанные значения. Хотя код не валиден, не смотря на то, что работает.
1
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
18.07.2016, 14:48  [ТС]
Тамика, кстати, вот такой код также работает. Странно.

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
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <iterator>
 
#include <vector>
 
using namespace std;
 
int main()
{
    vector<int> coll{ 1, 2, 3, 4, 5 };
 
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << coll.capacity() << endl;
 
    auto it = coll.begin(), stop = coll.end();
    auto ins = back_inserter(coll);
    while (it != stop)
    {
        *ins = *it;
        ++ins;
        ++it;
    }
 
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << coll.capacity() << endl;
}
Хотя, увеличивая список инициализации иногда, после вставки "портится" только вторая двойка, а остальные элементы правильно вставляются.
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
18.07.2016, 14:52
HenryDukart, нарыла исходник
C++
1
2
3
4
5
6
7
8
9
template<class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last, 
              OutputIt d_first)
{
    while (first != last) {
        *d_first++ = *first++;
    }
    return d_first;
}
1
Эксперт С++
 Аватар для Avazart
8484 / 6151 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
18.07.2016, 16:44
Мда я тоже чет не врублюсь...
Скорее всего просто повезло, и разместилось в той же памяти.
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// [url]http://ru.cppreference.com/w/cpp/algorithm/copy[/url]
template<class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last,
              OutputIt d_first)
{
    while (first != last) 
    {
        *d_first++ = *first++;
    }
    return d_first;
}
//----------------------------------------------------------------------
// [url]http://en.cppreference.com/w/cpp/iterator/back_insert_iterator[/url]
template< class Container >
std::back_insert_iterator<Container> back_inserter( Container& c)
{
    return std::back_insert_iterator<Container>(c);
}
//----------------------------------------------------------------------
// Выдрано из MSVC 2010
template<class _Container>
    class back_insert_iterator
        : public _Outit
    {   // wrap pushes to back of container as output iterator
public:
    typedef back_insert_iterator<_Container> _Myt;
    typedef _Container container_type;
    typedef typename _Container::const_reference const_reference;
    typedef typename _Container::value_type _Valty;
 
    explicit back_insert_iterator(_Container& _Cont)
        : container(&_Cont)
        {   // construct with container
        }
 
    _Myt& operator=(const _Valty& _Val)
        {   // push value into container
        container->push_back(_Val);
        return (*this);
        }
 
    _Myt& operator=(_Valty&& _Val)
        {   // push value into container
        container->push_back(_STD forward<_Valty>(_Val));
        return (*this);
        }
 
    _Myt& operator*()
        {   // pretend to return designated value
        return (*this);
        }
 
    _Myt& operator++()
        {   // pretend to preincrement
        return (*this);
        }
 
    _Myt operator++(int)
        {   // pretend to postincrement
        return (*this);
        }
 
protected:
    _Container *container;  // pointer to container
    };
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9005 / 4706 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
18.07.2016, 21:00
HenryDukart, 8-я студия крашит этот код. Инициализацию вектора пишу из массива, но не суть. Не работает.
1
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
18.07.2016, 21:13
Ваш код:
http://rextester.com/PRFC78944
1 2 3 4 5
5
1 2 3 4 5 1 0 3 4 5
10
Цитата Сообщение от HenryDukart Посмотреть сообщение
Ведь при вставке изменился объем вектора и итераторы в ходе copy стали невалидными.
итераторы вектора - random access, поэтому, например, оно может быть так:
C++
1
2
3
4
5
ptrdiff_t N = end - begin;
while(N!=0){
   //...
   --N;
}
0
18.07.2016, 21:22

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
А тут http://ideone.com/B4CS2o без проблем ...

0
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
18.07.2016, 21:49
Цитата Сообщение от Avazart Посмотреть сообщение
А тут http://ideone.com/B4CS2o без проблем
могу привести такое:
C++
1
2
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
//К алгоритму copy имеется требование: диапазоны не должны пересекаться:
Requires: result shall not be in the range [first,last).
//А также:
//Параметр - output iterator


If an algorithm’s Effects section says that a value pointed to by any iterator passed as an argument is
modified, then that algorithm has an additional type requirement: The type of that argument shall satisfy
the requirements of a mutable iterator (24.2). [ Note: This requirement does not affect arguments that are
named OutputIterator, OutputIterator1, or OutputIterator2, because output iterators must always be
mutable. —end note ]
//Третий параметр - всегда mutable iterator
//также смотрим что такое mutable iterator:

Iterators that further satisfy the requirements of output iterators are called mutable iterators. Nonmutable iterators are referred to as constant iterators.
//И для output iterators требование есть такое:
[ Note: The only valid use of an operator* is on the left side of the assignment statement. Assignment through the same value of the iterator happens only once. Algorithms on output iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. Equality and inequality might not be defined. Algorithms that take output iterators can be used with ostreams as the destination for placing data through the ostream_iterator class as well as with insert iterators and insert pointers. —end note ]

//Фрагменты из 24.2
Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges.
A range is a pair of iterators that designate the beginning and end of the computation. A range [i,i) is an
empty range; in general, a range [i,j) refers to the elements in the data structure starting with the element
pointed to by i and up to but not including the element pointed to by j. Range [i,j) is valid if and only if
j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined.
//Фактически, в данном случае, конечный итератор не достижим,
//значит диапазон не валидный, результат - не определенный
1
Эксперт С++
 Аватар для Avazart
8484 / 6151 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
18.07.2016, 21:54
Цитата Сообщение от Croessmah Посмотреть сообщение
//К алгоритму copy имеется требование: диапазоны не должны пересекаться:
Да это понятно, вопрос только каким там чудом реализовано что оно работает на сервисе.

Добавлено через 41 секунду
Но вообще нужно было HenryDukart сразу же глянуть в исходники.
0
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
18.07.2016, 22:00
Цитата Сообщение от Avazart Посмотреть сообщение
Да это понятно, вопрос только каким там чудом реализовано что оно работает на сервисе.
Ну так UB же.
Даже если vector освободил память,
это не значит что она тут же затерлась
А что касается "расширения" вектора, то это банально,
передаются итераторы, точнее - копии итераторов
(в векторе это вообще могут быть указатели),
значения этих итераторов не меняются из-за того,
что контейнер изменился.
Берем вместо вектора список, где итераторы
и сам контейнер более сложной структуры, получаем:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <iterator>
 
#include <list>
 
using namespace std;
 
int main()
{
    list<int> coll{ 1, 2, 3, 4, 5 };
 
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
 
    copy(coll.begin(), coll.end(), back_inserter(coll));
 
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}
terminate called after throwing an instance of 'St9bad_alloc'
what(): std::bad_alloc

Abort signal from abort(3) (SIGABRT)
1 2 3 4 5
http://rextester.com/VEW62673
Идем на Ideone, получаем:
1 2 3 4 5
Превышено ограничение на время
http://ideone.com/QWmg7w
1
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
18.07.2016, 22:48  [ТС]
Croessmah, интересный пример с list вы привели. Помогите понять, пожалуйста, почему так происходит. Я считал, что вставка и удаление элементов в список не делает итераторы некорректными. Почему же здесь обратная картина? Это связано с тем, что вставляем в позицию end и тем самым этот итератор становится некорректным?
0
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
18.07.2016, 23:00
Цитата Сообщение от HenryDukart Посмотреть сообщение
Я считал, что вставка и удаление элементов в список не делает итераторы некорректными.
У list итераторы не Random Access,
поэтому вычислить быстренько кол-во элементов не получится,
придется проходить по списку.
Что конкретно происходит может зависеть от реализации list'а.
Итератор end - это некий итератор на заведомо не валидный элемент.
Также, допустим, что operator++() реализован концептуально так:
C++
1
element = element->next;
В список постоянно добавляются элементы,
поэтому мы никогда не достигнем конца,
т.к. в данном случае он постоянно смещается.
1
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
18.07.2016, 23:12  [ТС]
Цитата Сообщение от Croessmah Посмотреть сообщение
В список постоянно добавляются элементы,
поэтому мы никогда не достигнем конца,
т.к. в данном случае он постоянно смещается.
Спасибо. Посидел, покумекал. Но хочу сказать, что end у list как раз-таки "стоит" на месте. Просто мы не можем добраться до конца, потому что новые элементы добавляем мечту последним "настоящим" элементом и end. Я думал, что end смещается.
0
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
18.07.2016, 23:16
Цитата Сообщение от HenryDukart Посмотреть сообщение
Я думал, что end смещается.
В принципе, всё зависит от реализации list,
мало ли, как он там устроен, поэтому я и написал
Цитата Сообщение от Croessmah Посмотреть сообщение
Что конкретно происходит может зависеть от реализации list'а.
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
19.07.2016, 10:59
IGPIGP, а Вы пробовали в релизе? В дебагге у меня тоже падает.
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9005 / 4706 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
19.07.2016, 11:04
Тамика, в релизе оно не падает а выдаёт 1 2 3 4 5 1 (четыре мусора)
то есть десять штук. UB конечно.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
19.07.2016, 11:04
Помогаю со студенческими работами здесь

std::copy из vector<double> в *double, непонятный warning
double myD={10,20,30,40,50,60,70}; std::vector&lt;double&gt; myvector (7); std::copy ( myD, myD+7, myvector.begin() ); std::copy (...

STL. Алгоритм copy()
Здравствуйте. Решаю задачку из учебника лафоре. Звучит она следующим образом: Алгоритм copy() можно использовать для копирования...

Алгоритм copy и итераторы вставки
Добрый день! Есть программа, она копирует заданный диапазон вектора и вставляет этот диапазон в этот же вектор (в начало)... // level...

boost::copy для создания copy constructor and assignment operator
&lt;boost/iostreams/copy.hpp&gt; кто ниб использовал boost::copy для создания copy constructor and assignment operator поделитесь опытом...

back_inserter()
Здорова! Пытаюсь написать свой back_inserter, но что то ничего не получается вот код #include &lt;iostream&gt; using std::cout; ...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru