Форум программистов, компьютерный форум CyberForum.ru

Задачи на собеседовании - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.56
Postoronnii
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 15
01.07.2014, 21:54     Задачи на собеседовании #1
Ходил на собеседование, мне дали 3 задачки, попросили решить любую на выбор, я не решил. Теперь хочу в них разобраться. Есть какие-нибудь идеи, как решить их?

1. Develop an application that checks if —++ std::map container
implementation complies with the standard.
It is enough to check methods insert, erase and find. Use zero return
code if test passes, or non-zero
value to indicate test failure.

Functions templates:

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
 int main()
  {
       if (test_insert()) {
           ...
           return 1;
       }
       if (test_erase()) {
           ...
           return 2;
       }
       if (test_find()) {
           ...
           return 3;
       }
  }
 
  int test_insert()
  {
       ...
       return rc;
  }
 
  int test_erase()
  {
       ...
       return rc;
  }
 
  int test_find()
  {
       ...
       return rc;
  }

2. Write a program to measure performance of standard containers
std::list and std::vector.
An application should measure:
a) Performance of a fixed size container construction and
initialization
b) Performance of a variable size container construction and
initialization
c) Performance of an element search algorithm
d) One or more scenarios of your choice

An application code should be easily adaptable for use with other
containers.

Measurement precision is one microsecond.

3. Develop an algorithm to measure memory consumption of an std::map
container of arbitrary
size and template arguments. As a proof, calculate and print on the
screen memory consumption
(in megabytes) of std::map<int, int> container with 1.000.000 of
unique records.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2014, 21:54     Задачи на собеседовании
Посмотрите здесь:

задачи по C++ C++
C++ Задачи C++
C++ задачи с++
C++ Задачи
Задачи в VS C++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
02.07.2014, 00:05     Задачи на собеседовании #2
Цитата Сообщение от Postoronnii Посмотреть сообщение
1.
Как я понял надо было проверить, соответствует ли поведение тому, что описано в стандарте (по крайней мере то, что можно проверить; ну например проверяем map::erase(inexistentKey) == 0), но это довольно много проверок придётся сделать.

Добавлено через 6 минут
Цитата Сообщение от Postoronnii Посмотреть сообщение
3.
Странная задача; насколько я понимаю, для этого надо знать, как реализован std::map, что бы знать, сколько занимает служебная информация (а это вроде нигде не оговорено).
Renji
1532 / 980 / 238
Регистрация: 05.06.2014
Сообщений: 2,950
02.07.2014, 00:11     Задачи на собеседовании #3
3. Develop an algorithm to measure memory consumption of an std::map
container of arbitrary
Передать std::map свой аллокатор, заставить аллокатор считать сколько там у него памяти попросили. Иных способов в голову не приходит.
Postoronnii
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 15
02.07.2014, 00:14  [ТС]     Задачи на собеседовании #4
А как это реализовать?
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
02.07.2014, 00:20     Задачи на собеседовании #5
Цитата Сообщение от Renji Посмотреть сообщение
Передать std::map свой аллокатор
так там же что нибудь вроде typename allocator_traits<T>::template rebind<some_map_node>::type ...

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

Не по теме:

Я бы вообще офигел от таких вопросов, если честно)

Renji
1532 / 980 / 238
Регистрация: 05.06.2014
Сообщений: 2,950
02.07.2014, 00:22     Задачи на собеседовании #6
Цитата Сообщение от Postoronnii Посмотреть сообщение
А как это реализовать?
Четвертым аргументом std::map передать свою версию аллокатора в которой реализованы все положенные функции. Внутри этих функций и ставить счетчик памяти.
Цитата Сообщение от gray_fox Посмотреть сообщение
так там же что нибудь вроде typename allocator_traits<T>::template rebind<some_map_node>::type ...
Я не знаю что там по умолчанию, но если уж в шаблон передан пользовательский аллокатор, то и работать шаблон должен через пользовательский аллокатор.
Postoronnii
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 15
02.07.2014, 00:22  [ТС]     Задачи на собеседовании #7
Цитата Сообщение от gray_fox Посмотреть сообщение
Не по теме:
Я бы вообще офигел от таких вопросов, если честно)
Так при чем, я на позицию QA, туда устраивался
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
02.07.2014, 00:26     Задачи на собеседовании #8
Цитата Сообщение от Renji Посмотреть сообщение
Я не знаю что там по умолчанию, но если уж в шаблон передан пользовательский аллокатор, то и работать шаблон должен через пользовательский аллокатор.
Да, не додумал, действительно будет работать...
Postoronnii
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 15
02.07.2014, 00:35  [ТС]     Задачи на собеседовании #9
Цитата Сообщение от Renji Посмотреть сообщение
Четвертым аргументом std::map передать свою версию аллокатора в которой реализованы все положенные функции. Внутри этих функций и ставить счетчик памяти.
А как это в коде выглядит? Не могу собрать(
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
02.07.2014, 00:59     Задачи на собеседовании #10
Цитата Сообщение от Postoronnii Посмотреть сообщение
А как это в коде выглядит? Не могу собрать(
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// ...Пишешь свой аллокатор
template<typename T>
struct my_allocator {
 
   // ...
 
   pointer allocate( size_type n, std::allocator<void>::const_pointer hint = 0 ) {
      // тут считаешь n
   }
 
};
 
// ...
 
 
// инстанциируешь
std::map<key_type, value_type, compare_type, my_allocator<std::pair<key_type const, value_type>> myMap;
Добавлено через 5 минут
Цитата Сообщение от gray_fox Посмотреть сообщение
// инстанциируешь
std::map<key_type, value_type, compare_type, my_allocator<std:air<key_type const, value_type>> myMap;
fix:
C++
1
std::map<key_type, value_type, compare_type, my_allocator<std::pair<key_type const, value_type> > > myMap;
Добавлено через 4 минуты
Т.е., если учитывать задание, то такой шаблон функции:
C++
1
2
3
4
5
6
template<typename Key, typename Value>
return_type test(std::size_size const size) {
   std::map<Key, Value, std::less<std::pair<Key, Value> >, my_allocator<std::pair<Key, Value > > > map;
   
   // заполняешь контейнер, измеряешь размер
}
Добавлено через 8 минут
Блин... должно быть std:air<Key const, Value>... но не суть...
Postoronnii
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 15
02.07.2014, 01:09  [ТС]     Задачи на собеседовании #11
Чет я ваще не так делаю, у меня ппц одни ошибки(
Цитата Сообщение от gray_fox Посмотреть сообщение
// заполняешь контейнер, измеряешь размер
как я понимаю, надо сначала аллокатор получить get_allocator()?

Добавлено через 6 минут
Огромное вам спасибо, но может вы мне рабочий код напишите, а то чет я по моему, нереально туплю
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
02.07.2014, 01:39     Задачи на собеседовании #12
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Postoronnii Посмотреть сообщение
Огромное вам спасибо, но может вы мне рабочий код напишите, а то чет я по моему, нереально туплю
Да я вроде что-то сам уже туплю) Вроде так:
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <functional>
#include <utility>
#include <memory>
#include <map>
 
 
std::size_t amount = 0;
 
 
template<typename T>
struct my_allocator : std::allocator<T> {
    
   template<typename U>
   struct rebind {
    
      using other = my_allocator<U>;
   };
 
   typename std::allocator<T>::pointer allocate(std::size_t const n, std::allocator<void>::const_pointer const hint = 0) {
      amount += n * sizeof (T);
      return std::allocator<T>::allocate(n, hint);
   }
};
 
 
int main() {
   std::map<int, int, std::less<int>, my_allocator<std::pair<int const, int> > > map;
 
   for (std::size_t i = 0; i != 10000; ++i) {
      map.insert(std::make_pair(i, i));
   }   
 
   std::cout << amount << std::endl;
}
http://ideone.com/cA6p3Q
Postoronnii
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 15
02.07.2014, 01:51  [ТС]     Задачи на собеседовании #13
Чет он мне такую ошибку выдает:

Код
1>------ Сборка начата: проект: Проект5, Конфигурация: Debug Win32 ------
1>  Исходный код.cpp
1>c:\program files (x86)\microsoft visual studio 12.0\vc\include\xmemory0(817): error C2664: "my_allocator<_Newfirst>::my_allocator(const my_allocator<_Newfirst> &) throw()": невозможно преобразовать аргумент 1 из "const std::_Wrap_alloc<my_allocator<_Newfirst>>" в "const my_allocator<_Newfirst> &"
1>          with
1>          [
1>              _Newfirst=std::_Container_proxy
1>          ]
1>          and
1>          [
1>              _Newfirst=std::_Tree_node<std::pair<const int,int>,void *>
1>          ]
1>          and
1>          [
1>              _Newfirst=std::_Container_proxy
1>          ]
1>          Причина: невозможно преобразовать "const std::_Wrap_alloc<my_allocator<_Newfirst>>" в "const my_allocator<_Newfirst>"
1>          with
1>          [
1>              _Newfirst=std::_Tree_node<std::pair<const int,int>,void *>
1>          ]
1>          and
1>          [
1>              _Newfirst=std::_Container_proxy
1>          ]
1>          Для выполнения данного преобразования нет доступного оператора преобразования, определенного пользователем, или вызов оператора невозможен
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(827): см. ссылку на создание экземпляров функции шаблон при компиляции "std::_Wrap_alloc<my_allocator<_Newfirst>>::_Wrap_alloc<std::_Wrap_alloc<my_allocator<std::_Tree_node<std::pair<const int,int>,void *>>>>(const _Other &) throw()"
1>          with
1>          [
1>              _Newfirst=std::_Container_proxy
1>  ,            _Other=std::_Wrap_alloc<my_allocator<std::_Tree_node<std::pair<const int,int>,void *>>>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(827): см. ссылку на создание экземпляров функции шаблон при компиляции "std::_Wrap_alloc<my_allocator<_Newfirst>>::_Wrap_alloc<std::_Wrap_alloc<my_allocator<std::_Tree_node<std::pair<const int,int>,void *>>>>(const _Other &) throw()"
1>          with
1>          [
1>              _Newfirst=std::_Container_proxy
1>  ,            _Other=std::_Wrap_alloc<my_allocator<std::_Tree_node<std::pair<const int,int>,void *>>>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(825): при компиляции функции-члена "void std::_Tree_alloc<false,std::_Tree_base_types<_Ty,_Alloc>>::_Free_proxy(void)" класса шаблон
1>          with
1>          [
1>              _Ty=std::pair<const int,int>
1>  ,            _Alloc=my_allocator<std::pair<const int,int>>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(804): см. ссылку на создание экземпляров функции шаблон при компиляции "void std::_Tree_alloc<false,std::_Tree_base_types<_Ty,_Alloc>>::_Free_proxy(void)"
1>          with
1>          [
1>              _Ty=std::pair<const int,int>
1>  ,            _Alloc=my_allocator<std::pair<const int,int>>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(879): см. ссылку на создание экземпляров класса шаблон при компиляции "std::_Tree_alloc<false,std::_Tree_base_types<_Ty,_Alloc>>"
1>          with
1>          [
1>              _Ty=std::pair<const int,int>
1>  ,            _Alloc=my_allocator<std::pair<const int,int>>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(991): см. ссылку на создание экземпляров класса шаблон при компиляции "std::_Tree_buy<std::pair<const int,int>,my_allocator<std::pair<const int,int>>>"
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(1024): см. ссылку на создание экземпляров класса шаблон при компиляции "std::_Tree_comp<false,_Traits>"
1>          with
1>          [
1>              _Traits=std::_Tmap_traits<int,int,std::less<int>,my_allocator<std::pair<const int,int>>,false>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 12.0\vc\include\map(70): см. ссылку на создание экземпляров класса шаблон при компиляции "std::_Tree<std::_Tmap_traits<_Kty,_Ty,_Pr,_Alloc,false>>"
1>          with
1>          [
1>              _Kty=int
1>  ,            _Ty=int
1>  ,            _Pr=std::less<int>
1>  ,            _Alloc=my_allocator<std::pair<const int,int>>
1>          ]
1>          c:\users\user\documents\visual studio 2013\projects\проект5\проект5\исходный код.cpp(28): см. ссылку на создание экземпляров класса шаблон при компиляции "std::map<int,int,std::less<int>,my_allocator<std::pair<const int,int>>>"
========== Сборка: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
02.07.2014, 01:55     Задачи на собеседовании #14
Postoronnii, Эмм, не знаю, что там с VS; возможно синитаксис; попробуй http://ideone.com/cA6p3Q
Postoronnii
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 15
02.07.2014, 11:31  [ТС]     Задачи на собеседовании #15
Цитата Сообщение от gray_fox Посмотреть сообщение
Postoronnii, Эмм, не знаю, что там с VS; возможно синитаксис; попробуй http://ideone.com/cA6p3Q
Добавлено через 9 часов 33 минуты
gray_fox, не могли бы вы рекомендовать мне какой компилятор стоит использовать?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.07.2014, 23:11     Задачи на собеседовании
Еще ссылки по теме:

3 задачи по С++ C++
C++ перегрузка оператора= (задание на собеседовании)
Задачи в с++ C++

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

Или воспользуйтесь поиском по форуму:
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
02.07.2014, 23:11     Задачи на собеседовании #16
Цитата Сообщение от Postoronnii Посмотреть сообщение
gray_fox, не могли бы вы рекомендовать мне какой компилятор стоит использовать?
Ничего оригинального предложить не могу: gcc, clang, тот, что в Visual Studio.
Yandex
Объявления
02.07.2014, 23:11     Задачи на собеседовании
Ответ Создать тему
Опции темы

Текущее время: 15:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru