Функтор Priority_queue использует C++

Я наткнулся на какое-то странное использование priority_queue, я хотел бы получить какое-то правильное объяснение того, почему правдоподобно/действительно использовать что-то подобное в объявлении priority_queue:

typedef priority_queue<RandomContainer, **vector<RandomContainer>**, FunctorName> NewQueueName;

Допустим, у нас есть некоторая структура с именем SPerson:

struct SPerson
{ 
   int age; 
   string name; 
   string surname; 
};

и некоторый функтор, который будет полезен для сортировки всех элементов очереди по нашему вкусу:

struct TheWayILike
{ 
   bool operator()(const SPerson &name1, const SPerson &name2) 
   { 
      if(name1.name > name2.name) return true; 
      if(name1.name < name2.name) return false; 

      return false; 
    } 
};

Теперь мы можем объявить нашу priority_queue, которая будет основана на элементах структуры и будет упорядочена функтором TheWayILike.

priority_queue<SPerson, TheWayILike>

или короче, используя typedef и одно имя, например:

 typedef priority_queue<SPerson, TheyWayILike> newNameForPQ;

но как-то это неправильно, и я должен добавить следующую строку: вектор

Вопрос:

С какой стати мне нужно сжимать мои настраиваемые типы данных в вектор?

Почему это должен быть вектор и почему я все равно должен его использовать?

Почему мне нужно заполнить мои данные в векторе? Я не читал об этом в официальной документации priority_queue, поэтому я хотел бы получить какое-нибудь понятное объяснение для программиста-новичка.

Ваше здоровье!


c++ functor
person Jamie Randall    schedule 17.10.2014    source источник
comment
Container — это только параметр шаблона. Он сообщает priority_queue, что использовать внутри, вам не нужно предоставлять экземпляр этого контейнера! Другими словами, создайте свою очередь следующим образом: priority_queue<SPerson, vector<SPerson>, TheWayILike> myPQ и поместите в нее свои элементы SPerson: myPQ.push(a); myPQ.push(b); ...   -  person Daniel L    schedule 18.10.2014

Ответы (1)


arrow_upward
3
arrow_downward

Вы не должны. Но посмотрите на объявление шаблона класса priority_queue:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Вы не можете предоставить собственный аргумент типа компаратора, если вы также не предоставите базовый контейнер для хранения данных. Автор строки выше решил, что vector был лучшим выбором. Также можно использовать любой другой контейнер, который соответствует требованиям, например. deque, но vector оказывается лучшим для большинства приложений, поэтому он используется по умолчанию.

person Columbo    schedule 17.10.2014
comment
В частности, контейнер должен выполнять определенный API и поддерживать итераторы произвольного доступа, что и vector, и deque поддерживают. - person aruisdante; 17.10.2014
comment
Таким образом, в основном я не могу использовать ТОЛЬКО базовую структуру в качестве контейнера, который будет использоваться в priority_queue, но мне нужно переназначить/скопировать все данные из структуры в вектор, дек или любой другой контейнер перед использованием priority_queue? Это правильно ? - person Jamie Randall; 18.10.2014
comment
Если вы хотите использовать тип priority_queue строки выше, да. Если вы можете использовать свою собственную специализацию priority_queue и ваш контейнер соответствует требованиям, вы можете просто позволить ему использовать ваш тип контейнера и переместить объект контейнера в класс priority_queue. - person Columbo; 18.10.2014
comment
@JamieRandall: Вы говорите так, как будто выполняется куча дополнительной работы, потому что вы используете настраиваемый тип с настраиваемым компаратором. Нет. Единственное, что вам нужно сделать по-другому, это то, как вы объявляете priority_queue (параметры шаблона, которые вы предоставляете). После этого вся остальная работа выполняется priority_queue, и это точно такой же объем работы, который выполняется для любого другого типа с любым другим компаратором. - person Benjamin Lindley; 18.10.2014