Тестовое задание C++, функтор для сортировки
Для поиска талантливых программистов написал тестовое задание C++. Вкратце, сложность задачи состоит в передачи дополнительных данных в функцию сравнения, которая используется сортировкой из стандартной библиотеки.
Из википедии:
Функциональный объект (англ. function object), так же функтор, функционал и функционоид — распространённая в программировании конструкция, позволяющая использовать объект как функцию. Часто используется как callback, делегат, либо как замена лямбда-выражениям в нефункциональных языках программирования.
Данное тестовое задание не требует знания решения сходу, хотя опытный программист, думаю, запросто так и сделает. Разрешается использовать интернет. Я без подсказки на stackoverflow не мог найти красивое решение. Цель задания — понять, умеет ли соискатель читать код, находить решения поставленных задач.
Консольная программа на C++ состоит из одного файла main.cpp из 150 строк. Наполняем условную базу данных работников. Есть классы Person (человек), Job (место работы), Position (должность).
#include <string>
struct Person{
Person();
Person(const string& _lastName, const string& _firstName, int _age, int _job_id, int _position_id);
string lastName;
string firstName;
int age;
int job_id;
int position_id;
};
struct Job{
Job();
Job(const string& _name, int _id);
string name;
int id;
};
struct Position{
Position();
Position(const string& _name, int _id);
string name;
int id;
};
Класс PersonsList хранит список людей в std::vector, а места работы и должности в map-ах, которые индексируются по id. Класс Person ссылается на Job и Position по их id.
#include <vector>
#include <map>
class PersonsList{
public:
void addPerson(const Person& person);
void addPosition(const Position& position);
void addJob(const Job& job);
void print();
void sortByName();
void sortByAge();
void sortByJob();
private:
std::vector<Person> persons;
std::map<int,Job> jobsMap;
std::map<int,Position> positionsMap;
};
В программе реализована функция сортировки по именам с помощью статической функции сравнения и std::stable_sort.
#include <algorithm>
bool compareByName(const Person& person1, const Person& person2){
if(person1.lastName==person2.lastName){
return person1.firstName<person2.firstName;
}
return person1.lastName<person2.lastName;
}
void PersonsList::sortByName(){
stable_sort(persons.begin(),persons.end(),compareByName);
}
В main’е идет наполнение базы данных, сортировки и вывод результатов в консоль.
#include <iostream>
int main()
{
PersonsList list;
Job google("Google",1);
Job microsoft("Microsoft",2);
Job hp("Hewlett-Packard",3);
list.addJob(google);
list.addJob(microsoft);
list.addJob(hp);
Position junior("Junior developer",1);
Position senior("Senior developer",2);
Position manager("Manager",3);
list.addPosition(junior);
list.addPosition(senior);
list.addPosition(manager);
list.addPerson(Person("Ivanov","Ivan",21,google.id,junior.id));
list.addPerson(Person("Sidorov","Nikolay",28,google.id,senior.id));
list.addPerson(Person("Ivanov","Maxim",28,google.id,manager.id));
list.addPerson(Person("Volkova","Katerina",22,microsoft.id,junior.id));
list.addPerson(Person("Demidov","Vitaly",35,microsoft.id,manager.id));
list.addPerson(Person("Bodrov","Boris",40,hp.id,senior.id));
list.sortByName();
cout<<"Sorted by name:"<<endl;
list.print();
cout<<endl;
list.sortByAge();
cout<<"Sorted by age:"<<endl;
list.print();
cout<<endl;
list.sortByJob();
cout<<"Sorted by job:"<<endl;
list.print();
return 0;
}
В исходникках, которые я привел выше, я упустил реализацию множества функций. Для интересующихся, полный исходник:
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct Person{
Person():lastName("noname"),firstName(""),age(0),job_id(0),position_id(0){}
Person(const string& _lastName, const string& _firstName, int _age, int _job_id, int _position_id)
:lastName(_lastName),
firstName(_firstName),
age(_age),
job_id(_job_id),
position_id(_position_id)
{}
string lastName;
string firstName;
int age;
int job_id;
int position_id;
};
struct Job{
Job():name("invalid job"),id(-1){}
Job(const string& _name, int _id):name(_name),id(_id){}
string name;
int id;
};
struct Position{
Position():name("invalid position"),id(-1){}
Position(const string& _name, int _id):name(_name),id(_id){}
string name;
int id;
};
bool compareByName(const Person& person1, const Person& person2){
if(person1.lastName==person2.lastName){
return person1.firstName<person2.firstName;
}
return person1.lastName<person2.lastName;
}
class PersonsList{
public:
void addPerson(const Person& person){
persons.push_back(person);
}
void addPosition(const Position& position){
positionsMap[position.id]=position;
}
void addJob(const Job& job){
jobsMap[job.id]=job;
}
void print(){
for(int i=0;i<(int)persons.size();i++){
Person& person=persons[i];
Job& job=jobsMap[person.job_id];
Position& position=positionsMap[person.position_id];
cout << setfill (' ') << std::setw (15) << person.lastName;
cout << setfill (' ') << std::setw (10) << person.firstName;
cout << setfill (' ') << std::setw (5) << person.age << " years";
cout << setfill (' ') << std::setw (20) << job.name;
cout << setfill (' ') << std::setw (20) << position.name;
cout << endl;
}
}
void sortByName(){
stable_sort(persons.begin(),persons.end(),compareByName);
}
void sortByAge(){
// ================================================= TODO
// programmer also want to change something else, not only this fucntion
}
void sortByJob(){
// ================================================= TODO
}
private:
std::vector<Person> persons;
std::map<int,Job> jobsMap;
std::map<int,Position> positionsMap;
};
int main()
{
PersonsList list;
Job google("Google",1);
Job microsoft("Microsoft",2);
Job hp("Hewlett-Packard",3);
list.addJob(google);
list.addJob(microsoft);
list.addJob(hp);
Position junior("Junior developer",1);
Position senior("Senior developer",2);
Position manager("Manager",3);
list.addPosition(junior);
list.addPosition(senior);
list.addPosition(manager);
list.addPerson(Person("Ivanov","Ivan",21,google.id,junior.id));
list.addPerson(Person("Sidorov","Nikolay",28,google.id,senior.id));
list.addPerson(Person("Ivanov","Maxim",28,google.id,manager.id));
list.addPerson(Person("Volkova","Katerina",22,microsoft.id,junior.id));
list.addPerson(Person("Demidov","Vitaly",35,microsoft.id,manager.id));
list.addPerson(Person("Bodrov","Boris",40,hp.id,senior.id));
list.sortByName();
cout<<"Sorted by name:"<<endl;
list.print();
cout<<endl;
list.sortByAge();
cout<<"Sorted by age:"<<endl;
list.print();
cout<<endl;
list.sortByJob();
cout<<"Sorted by job:"<<endl;
list.print();
return 0;
}
Тестовое задание состоит в реализации сортировки по месту работы, причем не по id, а по названию. Сложность в том, что в std::stable_sort третим параметром передается функция, которая принимает только 2 элемента для сравнения. Поскольку указатель на класс не передается, то эта функция не может быть методом класса, а только статической. Разрешается менять код в любом месте.
Вариантов решения множество, и я не претендую на знание оптимального решения. Под спойлером мой вариант решения.
bool compareByJobName(const Person& person1, const Person& person2, PersonsList* list){
Job& job1=list->getJobById(person1.job_id);
Job& job2=list->getJobById(person2.job_id);
return job1<job2;
}
class sorter {
PersonsList* listPointer;
public:
sorter(PersonsList* _listPointer) : listPointer(_listPointer) {}
bool operator()(const Person& person1, const Person& person2) const {
return compareByJobName(person1, person2, listPointer );
}
};
void PersonsList::sortByJob(){
stable_sort(persons.begin(),persons.end(),sorter(this));
}
Автор: gogan419