stl — Аннотация над deque и вектором в C ++ (используя итераторы?)
Поэтому я пишу подпрограмму обхода графа, и я хотел бы иметь возможность превратить ее в обход либо в глубину, либо в ширину, выбрав политику обхода соседей FIFO или LIFO. На практике это означает, что мне нужно абстрагировать операции «постановка в очередь» и «снятие очереди» над std::deque а также std::vector (или стек).
Это можно сделать достаточно легко, если использовать несколько шаблонных функций, предназначенных для этих контейнеров. Однако мне интересно: есть ли канонический способ сделать это в STL? Похоже, я мог бы использовать back_insert_iterator для «enqueue», но я не нашел front_remove_iterator для «dequeue». Я что-то пропустил?
Решение
Это уже существует как std::stack а также std::queue, Досадно, что интерфейс не совсем идентичен между ними, но это можно исправить. Это также дает возможность исправить void pop() бородавка.
template <typename Traversal, typename T, typename Container>
struct GraphNeighbors;
template<typename T, typename Container=std::deque<T>>
struct GraphNeighbors<class FIFO, T, Container>
{
private:
std::queue<T, Container> nodes;
public:
T pop()
{
T elem = std::move(nodes.front());
nodes.pop();
return elem;
}
void push(const T & elem)
{
nodes.push(elem);
}
void push(T&& elem)
nodes.emplace(std::move(elem));
}
};
template<typename T, typename Container=std::deque<T>>
struct GraphNeighbors<class LIFO, T, Container>
{
private:
std::stack<T, Container> nodes;
public:
T pop()
{
T elem = std::move(nodes.top());
nodes.pop();
return elem;
}
void push(const T & elem)
{
nodes.push(elem);
}
void push(T&& elem)
nodes.emplace(std::move(elem));
}
};
Другие решения
Других решений пока нет …