Собеседование std::vector

@ct0r · Регистрация: 19.08.2012

Студворк — интернет-сервис помощи студентам

1)
Вечереет. Вы крутой старший разработчик, сидите и делаете вид, что кодите мегапроект. У вас через полчаса собеседование. Вы предвкушаете базар ни о чем и обо всем, а также уже давно приготовили кучу пыточных вопросов, которые будут скрашивать ваше совместное времяпрепровождение. Внезапно вы чуете приближающегося техдира <> (подставить любое ненавистное имя) за спиной, степенно жмете Alt+tab, переключаясь с крайне интересных приложений на куда менее интересные. Начинается диалог.
- Здаров! У тебя через полчаса собеседование, помнишь?
- Канешн помню!
- Так вот, слушай сюда внимательно. Спрашиваешь только про std::vector и все, что к нему относится? Понял?
- ...?
- Ну так понял?
- Да понял я, понял.
Техдир уходит удовлетворенным.
На вас же нападает такое сильное вдохновение к построению многоэтажных зубодробительных языковых конструкций, что вы не можете удерживать это внутри себя: ### ##### ##### ### ###### ##############!

Ну что, народ? Что спрашивать-то с вами будем? Соискатель вроде не совсем дурак, как проверим его только с помощью std::vector?

2)
Если б это был я, то первые два вопроса, которые пришли б в голову:
при перераспределении памяти какой новый объем мы выделяем и почему именно такой?
напишите реализацию push_back (кодом, можно схематично)

Может кстати кто-нибудь хочет на них ответить?

@hoggy · 15.08.2015, 23:25

Сообщение от Tulosba

front возвращает ссылку, push_back принимает ссылку. Теперь представь ссылку как указатель и, я думаю, должно стать понятно.

ну и что?

пуш-бак - это вставка копии.
в чем проблема?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
 
int main()
{
    std::cout << "Hello, world!\n";
    
    
    std::vector<int> vec;
    
    vec.push_back(1);
    
    vec.push_back( vec.front() );
    vec.push_back( vec.front() );
    vec.push_back( vec.front() );
    vec.push_back( vec.front() );
    vec.push_back( vec.front() );
    
    for(const auto& i: vec)
        std::cout<<i<<'\n';
}

Tulosba · 15.08.2015, 23:29

hoggy, проблема в возможной реализации в лоб. Понятно, что сейчас это у всех работает ожидаемым образом.

@ct0r · 15.08.2015, 23:56 **[ТС]**

Сообщение от Tulosba

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

Если мы в процессе не копируем, а перещаем элементы, то будет все равно облом.

Сообщение от hoggy

пуш-бак - это вставка копии.
в чем проблема?

Сигнатуры функций:

C++
1
2
void push_back (const value_type& val);
void push_back (value_type&& val);

Если мы до момента непосредственной вставки как-то инвалидируем ссылки, то вставить нормально не получится.
Можешь тут почитать подробнее https://www.reddit.com/r/cpp/c... r_pitfall/

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

@Mr.X · 16.08.2015, 06:38

Сообщение от hoggy

на плюсах не существует никакого "by default" контейнера

Тут Страуструп с вами не согласен. Он прямо заявляет, что по умолчанию должен использоваться вектор.

Добавлено через 25 минут
Можно спросить как поведет себя вектор в зависимости от того какая функция-член хранимого типа возбудила исключение.

Добавлено через 12 минут
Попросить рассказать о специализации std::vector<bool>.

Tulosba · 16.08.2015, 11:51

Сообщение от ct0r

Если мы в процессе не копируем, а перещаем элементы, то будет все равно облом.

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

@rikimaru2013 · 07.05.2017, 14:17

P.S. Да, я некрофил

Сообщение от ct0r

Кстати вот вопрос еще.
Если мы сделаем v1 = std::move(v2); то потом можно работать с v2? Если да, то как?

Сообщение от Tulosba

Работать с v2 можно как угодно. Если не ошибаюсь,
состояние его после перемещения валидно, но не определено. Понятно, что в
этом случае ни о каком использовании итераторов и ссылок на элементы v2,
полученных до вызова std::move, речи быть не может.

Сообщение от ct0r

В целом верно. Да, контейнер будет в валидном (с
выполняющимися инвариантами) и неспецифицированном состоянии. А как
угодно можно работать, если только перед вызовом функций-членов проверять
их предусловия. Поэтому самый верный подход - вызвать функцию-член, не
требующую предусловий и возвращающую контейнер в известное состояние
(типа clear()). А вот потом - как душа пожелает.

Хотел бы уточнить для себя:

C++
1
2
3
4
5
6
7
    {
        std::vector<int> first = {3, 5, 6};
        std::vector<int> second = std::move( first );
        first.size();   //Value returned is undefined. May be 0, may not
        first.clear();  //Cause the vector to become empty.
        first.size();   //Now the value is guaranteed to be 0.
    }

На второй строке после std::move объект first переходит в состояние valid, but unspecified

From n3290, 17.6.5.15 Moved - from state of library types[ lib.types.movedfrom ]

Objects of types defined in the C++ standard library may be moved from( 12.8 ).
Move operations may be explicitly specified or implicitly generated.Unless otherwise
specified, such moved - from objects shall be placed in a valid but unspecified state.

Согласно видео http://www.youtube.com/watch?v... k&t=47m10s

После 2 строки с объектом можно:
- декструктор
- присвоение
- методы инкапсулируемые присвоение нового состояния: setState(), clear(), ....
- константные методы без precondition внутри: get(), empty(), size()

When an object is in an unspecified state, you can perform any operation on the object
which has no preconditions.If there is an operation with preconditions you wish to perform,
you can not directly perform that operation because you do not know if the unspecified - state
of the object satisfies the preconditions.

Получаем, что вызов метода по типу insert в объект в таком состояние UB, но вызов
empty(), size() имеет определённое поведение, но что именно вернётся в 3 строке,
зависит от того, что сделали с объектом в 2 строке[/B]. Другими словами, объект first не
контролирует своё состояния, после того как разрешил выпотрошить себя в 2 строке.

Отсюда, я не понимаю, ct0r, почему вы считаете, что если спросить у такого
объекта empty он тут же станет валидным для pop_back ?

C++
1
2
3
4
5
6
    {
        std::vector<int> first = {3, 5, 6};
        std::vector<int> second = std::move( first );
        if( !first.empty() )
            first.pop_back();
    }

Так же, фраза "с таким объектом можно делать всё, что угодно" думаю не совсем правильно,
учитывая мой текст выше. Как по мне, с таким объектом практически ничего не можно сделать ....

Вопросы:
1) Верный ли для кода выше комментарий //Value returned is undefined. May be 0, may not ?
2) Верно ли я дошёл к тому, что на вопрос ТС правильный ответ был бы "практически ничего не можно делать" кроме .... (тут была шутка про пессимиста и на половину пустом стакане) ?
3) А если std::move() перекидует объект в метод, который ничего не делает с объектом-from, объект всё равно перейдет в "такое" состояние ?

@ct0r · 07.05.2017, 14:59 **[ТС]**

Сообщение от rikimaru2013

Отсюда, я не понимаю, ct0r, почему вы считаете, что если спросить у такого
объекта empty он тут же станет валидным для pop_back ?

А почему нет? У empty() нет предусловий, его можно вызвать без опасений. А у pop_back() только одно предусловие, которое мы проверили явно сами. Ты же не считаешь, что empty() вернет false, если в векторе ничего нет?

Сообщение от rikimaru2013

1) Верный ли для кода выше комментарий //Value returned is undefined. May be 0, may not ?

Угу.

Сообщение от rikimaru2013

2) Верно ли я дошёл к тому, что на вопрос ТС правильный ответ был бы "практически ничего не можно делать" кроме .... (тут была шутка про пессимиста и на половину пустом стакане) ?

Не вижу разницы, как формулировать, главное, чтоб правильно.

Сообщение от rikimaru2013

3) А если std::move() перекидует объект в метод, который ничего не делает с объектом-from, объект всё равно перейдет в "такое" состояние ?

Смотря как передавать.

@rikimaru2013 · 07.05.2017, 15:08

Сообщение от ct0r

А почему нет? У empty() нет предусловий, его можно вызвать без опасений.
А у pop_back() только одно предусловие, которое мы проверили явно сами. Ты же не считаешь, что
empty() вернет false, если в векторе ничего нет?

Я к тому, что запрещено вызывать некоторые методы у такого объекта - а мы всё же вызываем,
основываясь, что UB по стандарту, но его не будет потому, что мы же убедились, что он не пустой.
Я к тому, что если написано будет UB - то даже, если нам поведение поклялось, что всё будет
хорошо - вызывать такие методы может привести к взрыву компьютера и всё будет закономерно.

Сообщение от ct0r

Угу.

Учитывая это - лучше не пользоваться такими проверками,а сразу работать с объектом second ?

Сообщение от ct0r

Не вижу разницы, как формулировать, главное, чтоб правильно.

Ну ведь слух то режет, если с 100500 методов интерфейса класса можно обратиться только к 3-ём методам
то это уже не "всё что угодно". Но думаю тут вопрос вкусов

Сообщение от ct0r

Смотря как передавать.

Получается можно стрельнуть в ногу, можно нет? Можно примеры?

@ct0r · 07.05.2017, 15:15 **[ТС]**

Сообщение от rikimaru2013

Я к тому, что запрещено вызывать некоторые методы у такого объекта - а мы всё же вызываем,
основываясь, что UB по стандарту, но его не будет потому, что мы же убедились, что он не пустой.
Я к тому, что если написано будет UB - то даже, если нам поведение поклялось, что всё будет
хорошо - вызывать такие методы может привести к взрыву компьютера и всё будет закономерно.

Чел, читай стандарт внимательней, там все написано.

17.3.25 [defns.valid]
valid but unspecified state
an object state that is not specified except that the object’s invariants are met and operations on the object
behave as specified for its type
[Example: If an object x of type std::vector<int> is in a valid but unspecified state, x.empty() can be
called unconditionally, and x.front() can be called only if x.empty() returns false. — end example ]

Сообщение от rikimaru2013

Получается можно стрельнуть в ногу, можно нет? Можно примеры?

А самому подумать, когда вызовется конструктор перемещения, а когда нет?
Выстрел в ногу тут только от незнания основ.

@rikimaru2013 · 07.05.2017, 15:19

ct0r, понятно чел

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367

	Собеседование std::vector 14.08.2015, 17:50. Показов 4289. Ответов 29 Метки нет (Все метки) 1) Вечереет. Вы крутой старший разработчик, сидите и делаете вид, что кодите мегапроект. У вас через полчаса собеседование. Вы предвкушаете базар ни о чем и обо всем, а также уже давно приготовили кучу пыточных вопросов, которые будут скрашивать ваше совместное времяпрепровождение. Внезапно вы чуете приближающегося техдира <> (подставить любое ненавистное имя) за спиной, степенно жмете Alt+tab, переключаясь с крайне интересных приложений на куда менее интересные. Начинается диалог. - Здаров! У тебя через полчаса собеседование, помнишь? - Канешн помню! - Так вот, слушай сюда внимательно. Спрашиваешь только про std::vector и все, что к нему относится? Понял? - ...? - Ну так понял? - Да понял я, понял. Техдир уходит удовлетворенным. На вас же нападает такое сильное вдохновение к построению многоэтажных зубодробительных языковых конструкций, что вы не можете удерживать это внутри себя: ### ##### ##### ### ###### ##############! Ну что, народ? Что спрашивать-то с вами будем? Соискатель вроде не совсем дурак, как проверим его только с помощью std::vector? 2) Если б это был я, то первые два вопроса, которые пришли б в голову: при перераспределении памяти какой новый объем мы выделяем и почему именно такой? напишите реализацию push_back (кодом, можно схематично) Может кстати кто-нибудь хочет на них ответить? 1

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	15.08.2015, 23:29
	hoggy, проблема в возможной реализации в лоб. Понятно, что сейчас это у всех работает ожидаемым образом. 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	07.05.2017, 15:19
	ct0r, понятно чел 0