Тестовое задание C++, функтор для сортировки

image
Для поиска талантливых программистов написал тестовое задание 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'е идет наполнение базы данных, сортировки и вывод результатов в консоль.
int 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 элемента для сравнения. Поскольку указатель на класс не передается, то эта функция не может быть методом класса, а только статической. Разрешается менять код в любом месте.

Вариантов решения множество, и я не претендую на знание оптимального решения. Под спойлером мой вариант решения.
Решение
Я использовал статическую функцию сравнения, которая принимает третьим параметром указатель на PersonsList. А чтобы передать этот параметр, завернул это все в дополнительный класс, который использовал как функцию.

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));
}

Поделиться публикацией

Комментарии 14

    +6
    Вряд ли такая задача подходит для поиска талантливых программистов. Надо посложнее все таки.
      +5
      С использованием boost вроде можно так:

      void PersonsList::compareByJobName( const Person& person1, const Person& person2 )
      {
          Job& job1=getJobById(person1.job_id);
          Job& job2=getJobById(person2.job_id);
          return job1<job2;
      }
      
      void PersonsList::sortByJob(){
          stable_sort(persons.begin(),persons.end(), boost::bind(&PersonsList::compareByJobName, this, _1, _2));
      }
      
        0
        upd:
          bool PersonsList::compareByJobName( const Person& person1, const Person& person2 )
        
          –1
          Спасибо, да, это решение у меня крутилось в голове. boost::bind использую часто, когда линкую сигналы и слоты Wt-шных объектов, код пишу под линуксом, там с бустом просто. Под windows же поднять буст и парвильно настроить — нетривиальная задача, не хотел завязывать на нем этот пример.
            0
            bool PersonsList::compareByJobName( const Person& person1, const Person& person2 )
            {
                Job& job1=getJobById(person1.job_id);
                Job& job2=getJobById(person2.job_id);
                return job1<job2;
            }
            
            void PersonsList::sortByJob(){
                using namespace std::placeholders;
                stable_sort(persons.begin(),persons.end(), std::bind(&PersonsList::compareByJobName, this, _1, _2));
            }
            


            Легко, вот пример на чистом C++ без сторонних библиотек :) Даже студия, вроде, уже научилась так делать.
              +3
              Под windows же поднять буст и парвильно настроить — нетривиальная задача

              Да ну, вы что. Для bind и остальной большей части буста, вообще ничего настраивать не нужно, только заинклудить bost/bind.hpp, это же header-only библиотеки.

              Что касается link-библиотек, под винду настраивается тривиально. Если не желаете сами собирать, то скачиваете готовые, собранные либы с www.boostpro.com/download/ Там даже msi-установщик готовый.
              +1
              В C++11 std::bind уже есть. Также можно и лямбдой.
              +9
              Я конечно не уверен, но, по моему, опыту любой программист работавший с С++ писал когда-то оператор скобок для сортировки. Ну или хотя бы читавший Страуструпа или любую другую книгу не «для чайников».
                +4
                очень странный пост:
                1. в языке и стандартной библиотеке есть — std::bind или лямбда который как раз и предназначены для таких целей;
                2. я бы лучше в Person хранил константную ссылку или шаред понинтер на константу на jobs и positions — и возвращал бы значение job и position обычным методом;
                3. string firstName;
                int job_id;
                странный какой-то конвеншн — меня бы насторожило, если бы мне настолько грязный код подсунули на интервью;
                4.
                bool compareByName(const Person& person1, const Person& person2){
                if(person1.lastName==person2.lastName){
                return person1.firstName<person2.firstName;
                }
                return person1.lastName<person2.lastName;
                }
                для подобного мусора лучше использовать std::tie
                return std::tie(person1.lastName, person1.firstName) < std::tie(person2...);

                5. compareByName — ф-ция называется compare — хотя возвращает true если меньше. правильно начать название с less.

                вообщем не позорьтесь и прячьте пост.
                  0
                  std::bind появился в c++11, также как и std::tie.
                  Less в названии больше подходит для метода Person::lessByName(const Person& other), когда понятно, кто меньше кого. Также, для строковых переменных слово «сравнить» понятнее, чем «больше» или «меньше».
                  По поводу ссылок — согласен. Просто это задание я взял из своего опыта, когда я загружал в память данные с SQL Базы для обработки, а там были id поля и ссылки по ним.
                  По конвеншину — согласен.
                  Пост пока прятать не буду, спасибо за комментарий.
                    0
                    — я лет 8мь назад ими пользовался только из буста, потом в с++0x, потом в с++11, уже кстати готовиться с++14 так что с++11 — это просто с++.
                    кстати на интервью до сих пор попадаются кандидаты, которые заявляют я с++ знаю, но stl — нет, хотя стандартная библиотека — это тоже часть языка. теперь также наверное будет и с с++11;
                    — compare значит сравнить, т.е. результат будет говорить — больше, меньше или равно. в вашем случае — он говорит только меньше.
                    представьте себе строчку — if (compareByName(...)) — как ее читать английским языком?

                    >Пост пока прятать не буду, спасибо за комментарий.
                    это конечно же вам решать. я посоветовал спрятать, что бы вы минусов не нахватались :)
                  0
                  Если не использовать Boost и C++11, решение тоже очень простое — в конструкторе функтора надо передать ссылку на jobsMap. Такой подход постоянно практикуется у Скотта Маерса в Effective STL.
                  Я набросал решение, но не стал проверять валидность job_id. Надо конечно делать через find, а не через operator[].
                  На всякий случай решение в статье я не смотрел :-))

                  class CompareByJobName: public std::binary_function<Person, Person, bool>{
                  	std::map<int, Job> &jobsMap;
                  	public:
                  	CompareByJobName(std::map<int, Job> &_jobsMap): jobMap(_jobMap){};
                  	inline bool operator()(const Person& person1, const Person& person2){
                  		if(person1.job_id==person2.job_id){
                  			if(person1.lastName==person2.lastName){
                  				return person1.firstName<person2.firstName;
                  			}else return    person1.lastName<person2.lastName;
                  		}
                  		return jobsMap[person1.job_id] < jobsMap[person2.job_id] ;
                  	}
                  }
                  
                  std::stable_sort(persons.begin(),persons.end(),CompareByJobName(jobsMap) );
                  
                    +1
                    Особоенность stable_sort как раз в том, что он не меняет порядок элементов, которые равны по ключу сортировки.
                    Если я отсортировал по имени, а затем по месту работы, то в пределах одной работы останется сортировка по имени.
                    Если я не ошибась, стандартная библиотека использует merge sort для стабильной сортировки. Если же использовать std::sort, то используется merge sort для структур, и quick sort (не стабильный, но быстрее) для простых типов.
                      0
                      Спасибо, Вы правы.

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

                  Самое читаемое