Как я могу написать шаблон функции, который может принимать либо стек, либо очередь?

Question

Я реализую четыре алгоритма, которые полностью идентичны, за исключением того, какую структуру данных они используют - два используют priority_queue, один использует stack, а последний использует queue.Они относительно длинные, поэтому я хотел бы иметь только один шаблон функции, который принимает тип контейнера в качестве аргумента шаблона, а затем каждый алгоритм вызывает этот шаблон с соответствующим аргументом, например:

template <class Container>
void foo(/* args */)
{
    Container dataStructure;
    // Algorithm goes here
}

void queueBased(/* args */)
{
    foo<queue<Item> >(/* args */);
}

void stackBased(/* args */)
{
    foo<stack<Item> >(/* args */);
}

Мне удалось сделать это только с реализациями на основе priority_queue и stack, но я не могу сделать то же самое для алгоритма на основе queue, потому что он использует другое имя для доступа к переднему элементу(front( ) вместо top( )).Я знаю, что мог бы специализировать шаблон для этого случая, но тогда у меня был бы большой участок дублированного кода (чего я и стараюсь избегать).

Какой лучший способ сделать это?Моим первым инстинктом было создание класса-обертки для очереди, который добавляет операцию top( ), эквивалентную stack, но я читал, что подклассы классов STL - нет-нет.Как я тогда получу это поведение?

Answer 1

Вы можете написать функцию, не являющуюся членом top, перегруженную для типа адаптера контейнера:

template <typename T>
T& top(std::stack<T>& s) { return s.top(); }

template <typename T>
T& top(std::queue<T>& q) { return q.front(); }

// etc.

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

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

Answer 2

Вы можете использовать частичную специализацию, чтобы выбрать правильный метод:

template<class Container>
struct foo_detail {
  static typename Container::value_type& top(Container &c) { return c.top(); }
  static typename Container::value_type const& top(Container const &c) { return c.top(); }
};
template<class T, class Underlying>
struct foo_detail<std::queue<T, Underlying> > {
  typedef std::queue<T, Underlying> Container;
  static typename Container::value_type& top(Container &c) { return c.front(); }
  static typename Container::value_type const& top(Container const &c) { return c.front(); }
};

template<class Container>
void foo(/* args */)
{
    Container dataStructure;
    // Use foo_detail<Container>::top(dataStructure) instead of dataStructure.top().
    // Yes, I know it's ugly.  :(
}

Answer 3

Вы можете создать оболочку вокруг std::queue без использования наследования;на самом деле наследование было бы неправильным инструментом, потому что вы пытаетесь украсить a queue вместо уточнения или расширения queue.Вот одна из возможных реализаций:

template <typename QueueType>
class QueueWrapper {
public:
    explicit QueueWrapper(const QueueType& q) : queue(q) {
        // Handled in initializer list
    }

    typedef typename QueueType::value_type value_type;

    value_type& top() {
        return queue.front();
    }
    const value_type& top() const {
        return queue.front();
    }

    void pop() {
        queue.pop();
    }
private:
    QueueType queue;
};

Надеюсь, это поможет!

Answer 4

queue, priority_queue и stack - все адаптеры контейнера;они являются обертками вокруг основного контейнера (по умолчанию deque для queue и stack и vector для priority_queue).

С vector, deque и list(«настоящие» контейнерные классы) разделяют большинство их методов, вы можете вырезать посредника и использовать эти классы.

И помните, что наследование public не очень хорошая идеядля контейнеров STL; личное наследование в порядке (и, вероятно, то, что вы хотите).

Answer 5

front() и top() относятся к определенным типам контейнеров, но все контейнеры STL поддерживают *begin().