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

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

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

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

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

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

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

@_Ivana · 14.08.2015, 19:26

Ээээ... Я конечно ничего в этом не понимаю, но если бы понимал - дал бы просто одну задачку: написать свой вектор, лучше (в определенном смысле разумеется) Степановского стд-шного. А лучше 2-3 варианта своих векторов, которые будут лучше стд-шного в разных смыслах

@Nick Alte · 14.08.2015, 19:41

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

при перераспределении памяти какой новый объем мы выделяем и почему именно такой?

Это зависит от реализации. Нетрудно убедиться, что в VS новый объём в 1.5 раза больше предыдущего, а в GCC в 2 раза. Я видел обоснование того, что более оптимальным с учётом повторного использования освобождённой памяти будет коэффициент около 1.25. Соображения о "почему именно такой", понятно, в каждой реализации разные.

@schdub · 14.08.2015, 23:18

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

Что спрашивать-то с вами будем?

Наверное сильно просто, но я бы спросил:
1) удаление n-го элемента в векторе (чем больше вариантов тем лучше);
2) ужатие вектора в C++03 и C++11.

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
#include <iostream>
#include <vector>
 
template<class T>
std::ostream & operator<<(std::ostream & os, const std::vector<T> & v) {
    static int counter = 1;
    os << counter++ << ") [";
    if (!v.empty()) os << v[0];
    for (int i = 1; i < v.size(); os << "," << v[i++]);
    os << "] " << v.capacity() << " " << v.size();
    return os;
}
 
typedef std::vector<int> IntVector;
 
int main() {
    IntVector v(10);
    for (int i = 0; i < 10; v[i] = i, ++i);
    std::cout << v << std::endl;              // 1
 
    v.erase(v.begin() + 0);
    std::cout << v << std::endl;              // 2
 
    std::swap(v[0], v.back());
    v.pop_back();
    std::cout << v << std::endl;              // 3
 
    v[0] = v.back();
    v.pop_back();
    std::cout << v << std::endl;              // 4
 
#if (__cplusplus < 201103L)
    // C++03
    v.clear();
    std::cout << v << std::endl;              // 5
 
    IntVector().swap(v);
    std::cout << v << std::endl;              // 6
#else
    // C++11
    if (v.size() > 0) v[0] = std::move(v.back());
    v.pop_back();
    std::cout << v << std::endl;              // 6
 
    v.clear();
    std::cout << v << std::endl;              // 7
 
    v.shrink_to_fit();
    std::cout << v << std::endl;              // 8
#endif
 
}

@John Prick · 15.08.2015, 00:43

Из не так давно читанной мной книжки: "Как по-настоящему удалить элементы из вектора".

@ct0r · 15.08.2015, 17:43 **[ТС]**

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

Ээээ... Я конечно ничего в этом не понимаю, но если бы понимал - дал бы просто одну задачку: написать свой вектор, лучше (в определенном смысле разумеется) Степановского стд-шного. А лучше 2-3 варианта своих векторов, которые будут лучше стд-шного в разных смыслах

Я боюсь, фигня получится

Даже с одним вариантом. Это только на первый взгляд кажется, что написать вектор можно просто и быстро. Ты кстати никогда сам не копался в коде std::vector?

Сообщение от Nick Alte

Это зависит от реализации. Нетрудно убедиться, что в VS новый объём в 1.5 раза больше предыдущего, а в GCC в 2 раза. Я видел обоснование того, что более оптимальным с учётом повторного использования освобождённой памяти будет коэффициент около 1.25. Соображения о "почему именно такой", понятно, в каждой реализации разные.

Ну да, вопрос легкий. Скорее проверяет любознательность кандидата. А вообще ситуация забавная. Теоретически 1.4-1.6 лучшие значения, которые через определенное число реаллокаций (кстати разное) позволяют переиспользовать память (если повезет). Нетрудно даже написать уравнение и решить. Из-за того, что gcc и clang по-прежнему используют 2, фэйсбук опустила их вектор ниже плинтуса и написала свой folly/fbvector. В ответ gcc-шники заявили, что это все теория, а эмпирически ничто не работает лучше, чем 2.
Второй вопрос поинтереснее будет. Там есть pitfall, на который в свое время напоролась даже реализация STL от MS.

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

Наверное сильно просто

Понятие просто у каждого свое. Настоящий минус этих вопросов в том, что они слишком стандартные - везде об этом сейчас пишут

Сообщение от John Prick

Как по-настоящему удалить элементы из вектора

Это про идиому erase-remove?

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

@Voivoid · 15.08.2015, 18:07

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

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

1) Алгоритмическая сложность операции вставки + обсуждение стратегий аллокации памяти
2) Спросить про emplace, зачем он нужен. Почему просто не использовать push_back + move?
3) Спросить почему pop_back не возвращает элемент. И какие были бы проблемы если бы возвращал?
4) Спросить когда предпочтительнее vector, а когда list. И почему в ситуаяциях, когда ожидаются частые вставки в середину, vector все же может быть предпочтительнее чем list.

@John Prick · 15.08.2015, 18:57

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

Это про идиому erase-remove?

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

@Kastaneda · 15.08.2015, 20:37

Почему vector контейнер "by default"? В той же Java это List, почему в С++ не list?

@hoggy · 15.08.2015, 20:49

Сообщение от John Prick

Из не так давно читанной мной книжки: "Как по-настоящему удалить элементы из вектора".

имеется ввиду что-то вроде: свапнуть старый контейнер, с резервом на новый, без резерва?

Добавлено через 1 минуту

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

Почему vector контейнер "by default"? В той же Java это List, почему в С++ не list?

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

разные контейнеры под разную задачу.

Добавлено через 1 минуту

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

Там есть pitfall

что это?

@Kastaneda · 15.08.2015, 20:59

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

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

Поэтому "by default" в ковычках.

@hoggy · 15.08.2015, 21:11

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

Поэтому "by default" в ковычках.

Не по теме:

хе-хе, какой вы хитрый.
хотели на понт взять... :p

Tulosba · 15.08.2015, 22:05

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

Спрашиваешь только про std::vector и все, что к нему относится? Понял?

Не понял. Это просто такая фантастическая история (и мы увидим аналогичные про другие компоненты из std), или блатной кандидат, который только один контейнер освоил?

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

Что спрашивать-то с вами будем?

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

- Что такое std::vector;
- В какую часть контейнера элементы вставляются максимально эффективно;
- В чем особенность внутренней реализации по сравнению с другими контейнерами;
- Чем отличается reserve() от resize(), capacity() от size();
- Какие требования предъявляются к типу объектов, хранимых в контейнере;
- Как эти требования изменились при переходе к C++11;
- Для какого типа в библиотеке реализована специализация контейнера;
- Чем отличается at() от operator[].

Добавлено через 10 минут

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

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

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

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

В той же Java это List, почему в С++ не list?

ТС хотел тему вектором ограничить, а тут вон аж другой ЯП нарисовался. Нехорошо

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

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

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

@hoggy · 15.08.2015, 22:11

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

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

вот так вы и ответите на собеседование?

Tulosba · 15.08.2015, 22:16

Не по теме:

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

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

слона-то я и не приметил :(

Добавлено через 3 минуты

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

вот так вы и ответите на собеседование?

Это по-крайней мере даст понять, что кандидат просмотрел хотя бы не только "C++ за 24 часа". Что уже многое значит.

@hoggy · 15.08.2015, 22:29

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

Это по-крайней мере даст понять, что кандидат просмотрел хотя бы не только "C++ за 24 часа". Что уже многое значит.

Не по теме:

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

я сначала думал:
это типа тест на внимательность. наверняка есть какой то подвох.

но мы как то так разговорились.
и я объяснил принцип type erasure на примере shared_ptr,
и что примерно под капотом make_shared,
что оно так лихо за одну аллокацию подсовывает и объект, и счетчики.

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

после этого, я решил вернуться к разглядыванию кода интрузивного указателя.
но мой собеседующий (а ныне - мой босс), сказал:
в этом нет нужды.
итак понятно, какие книги ты читал.

а к чему я про все это - важно не количество книг, а объем знаний.

@ct0r · 15.08.2015, 22:38 **[ТС]**

Сообщение от John Prick

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

Понятно. То есть по сути имелось в виду то же, что и в #4.

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

что это?

Это переводится как "сложность или опасность, неочевидная на первый взгляд". При прямолинейном алгоритме push_back (типа выделяем память, копируем/перемещаем туда элементы, добавляем в конец переданный) можно попасть на v.push_back(v.front()); и обломаться.

Voivoid неявно упомянул exception safety, чем навел на вопрос:
В каком случае при перераспределении памяти будет копирование элементов, а в каком - перемещение? И что будет, если конструктор копирования класса недоступен?

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

Не понял. Это просто такая фантастическая история (и мы увидим аналогичные про другие компоненты из std), или блатной кандидат, который только один контейнер освоил?

Это вечер пятницы

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

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

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

Tulosba · 15.08.2015, 23:00

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

важно не количество книг, а объем знаний.

Основной источник знаний - книга, так что это взаимосвязано.

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

можно попасть на v.push_back(v.front()); и обломаться.

Если освобождать старую память в конце всех действий, то облома быть не должно. Тут невольно вспоминается инфа про различие в memcpy/memmove.

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

Это вечер пятницы

Удался

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

вызвать функцию-член, не требующую предусловий

В принципе, это вытекает из неспецифического состояния.

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

типа clear()

Тогда уж сразу деструктор

@hoggy · 15.08.2015, 23:04

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

Это переводится как "сложность или опасность, неочевидная на первый взгляд". При прямолинейном алгоритме push_back (типа выделяем память, копируем/перемещаем туда элементы, добавляем в конец переданный) можно попасть на v.push_back(v.front()); и обломаться.

не уловил.

как здесь можно обломаться?

не вижу никакой проблемы.

между:

C++
1
v.push_back(v.front());

и

C++
1
v.push_back(10);

нет никакой разницы.

Tulosba · 15.08.2015, 23:13

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

не вижу никакой проблемы.

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

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	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 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

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

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

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,988 Записей в блоге: 32
	14.08.2015, 19:26
	Ээээ... Я конечно ничего в этом не понимаю, но если бы понимал - дал бы просто одну задачку: написать свой вектор, лучше (в определенном смысле разумеется) Степановского стд-шного. А лучше 2-3 варианта своих векторов, которые будут лучше стд-шного в разных смыслах 4

@John Prick 2393 / 1913 / 763 Регистрация: 27.07.2012 Сообщений: 5,557
	15.08.2015, 00:43
	Из не так давно читанной мной книжки: "Как по-настоящему удалить элементы из вектора". 1

@Kastaneda 5232 / 3205 / 362 Регистрация: 12.12.2009 Сообщений: 8,143 Записей в блоге: 2
	15.08.2015, 20:37
	Почему vector контейнер "by default"? В той же Java это List, почему в С++ не list? 0