C++：多态容器/迭代器与编译时概念/特征
C++: Polymorphic container / iterator vs compile time concept / traits
背景
这纯粹是为了教育目的。如果你不想看完整的背景，可以跳到底部的问题。
我已经编写了一个 Queue 接口（抽象 class），以及 2 个基于调整数组和链表大小的派生实现。
template <typename T>
class IQueue {
public:
virtual void enqueue(T item) = 0;
virtual T dequeue() = 0;
virtual bool isEmpty() = 0;
virtual int size() = 0;
}
template <typename T>
class LinkedListQueue : public IQueue<T> {...}
template <typename T>
class ResizingArrayQueue : public IQueue<T> {...}
我希望能够使用符合 STL 的迭代器遍历队列的元素（我知道队列不应该是可迭代的），所以我可以使用 for (auto e: c) 或 queue.begin() / queue.end().
因为我使用 运行-time 多态性，所以我不得不添加一个客户端迭代器 class 到 IQueue 并使用 Pimpl 习惯用法在派生队列中实例化实际实现特定的迭代器classes，以避免对象切片问题。
所以增强代码看起来像：
template <typename T>
class IQueue {
public:
virtual void enqueue(T item) = 0;
virtual T dequeue() = 0;
virtual bool isEmpty() = 0;
virtual int size() = 0;
public:
class IteratorImpl {
public:
virtual void increment () = 0;
virtual bool operator== (const IteratorImpl& other) const = 0;
virtual bool operator!= (const IteratorImpl& other) const = 0;
virtual T& operator* () const = 0;
virtual T& operator-> () const = 0;
virtual void swap (IteratorImpl& other) = 0;
virtual IteratorImpl* clone() = 0;
};
public:
class ClientIterator : public std::iterator<std::forward_iterator_tag, T> {
std::unique_ptr<IteratorImpl> impl;
public:
ClientIterator(const ClientIterator& other) : impl(other.impl->clone()) {}
ClientIterator(std::unique_ptr<IteratorImpl> it) : impl(std::move(it)) {}
void swap(ClientIterator& other) noexcept {
impl->swap(*(other.impl));
}
ClientIterator& operator++ () {
impl->increment();
return *this;
}
ClientIterator operator++ (int) {
ClientIterator tmp(*this);
impl->increment();
return tmp;
}
bool operator== (const ClientIterator& other) const {
return *impl == *other.impl;
}
bool operator!= (const ClientIterator& other) const {
return *impl != *other.impl;
}
T& operator* () const {
return **impl;
}
T& operator-> () const {
return **impl;
}
};
typedef ClientIterator iterator;
virtual iterator begin() = 0;
virtual iterator end() = 0;
};
并且派生的 classes 之一实现了 begin() / end() 方法和派生的 Iterator 实现：
template <typename T>
class LinkedListQueue : public IQueue<T> {
// ... queue implementation details.
public:
class LinkedListForwardIterator : public IQueue<T>::IteratorImpl {
// ... implementation that goes through linked list.
};
typename IQueue<T>::ClientIterator begin() {
std::unique_ptr<LinkedListForwardIterator> impl(new LinkedListForwardIterator(head));
return typename IQueue<T>::iterator(std::move(impl));
}
typename IQueue<T>::ClientIterator end() {
std::unique_ptr<LinkedListForwardIterator> impl(new LinkedListForwardIterator(nullptr));
return typename IQueue<T>::iterator(std::move(impl));
}
};
现在为了测试迭代器是否工作，我有以下两个函数：
template <typename T>
void testQueueImpl(std::shared_ptr<IQueue<T> > queue) {
queue->enqueue(1);
queue->enqueue(2);
queue->enqueue(3);
queue->enqueue(4);
queue->enqueue(5);
queue->enqueue(6);
std::cout << "Iterator behavior check 1st: ";
for (auto e: *queue) {
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << "Iterator behavior check 2nd: ";
for (auto it = queue->begin(); it != queue->end(); it++) {
std::cout << *it << " ";
}
}
void testQueue() {
auto queue = std::make_shared<LinkedListQueue<int> >();
testQueueImpl<int>(queue);
auto queue2 = std::make_shared<ResizingArrayQueue<int> >();
testQueueImpl<int>(queue2);
}
问题
如何摆脱 运行 时间多态性（删除 IQueue，删除迭代器 Pimpl 实现），并重写 testQueue() / testQueueImpl() 函数以便：
- 这些函数可以成功测试 Stack 实现和 Stack 迭代器，而无需基 class 指针。
- LinkedListQueue 和 ResizingArrayQueue 都遵循某种编译时接口（存在 enqueue、dequeue、isEmpty、size 方法，存在 begin / end 方法，两个 classes 都包含有效的迭代器 classes)?
可能的解决方案
对于 1) 看来我可以简单地将模板参数更改为整个容器，程序编译成功并且 运行s。但这不会检查 begin() / end() / enqueue() 方法是否存在。
对于2），从我在互联网上可以找到的内容来看，相关解决方案似乎涉及类型特征/ SFINAE /或概念（容器概念，前向迭代器概念）。似乎 Boost Concepts 库允许注释 class 以符合容器概念，但我对用于教育目的的自包含解决方案（除 STL 外没有外部库）感兴趣。
template <typename Container>
void testQueueImpl(Container queue) {
queue->enqueue(1);
queue->enqueue(2);
queue->enqueue(3);
queue->enqueue(4);
queue->enqueue(5);
queue->enqueue(6);
std::cout << "Size: " << queue->size() << std::endl;
std::cout << "Iterator behavior check 1st: ";
for (auto e: *queue) {
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << "Iterator behavior check 2nd: ";
for (auto it = queue->begin(); it != queue->end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl;
}
void testQueue() {
auto queue = std::make_shared<LinkedListQueue<int> >();
testQueueImpl<std::shared_ptr<LinkedListQueue<int> > >(queue);
auto queue2 = std::make_shared<ResizingArrayQueue<int> >();
testQueueImpl<std::shared_ptr<ResizingArrayQueue<int> > >(queue2);
}
这是一个最简单的可编译示例，说明您可能希望如何做到这一点。
请注意，目前此示例仅支持 const begin() 和 const end()。
添加更多方法和可变迭代器是 reader
的练习
编辑：提供了共享相同策略的编译时和运行时多态队列的工作示例类。
#include <iostream>
#include <list>
#include <vector>
#include <memory>
#include <typeinfo>
#include <typeindex>
/// COMPILE TIME Polymorphic queue of objects of type Element
template<typename Element, class Policy>
struct queue_concept
{
// Define interface
struct const_iterator;
void push_back(Element e);
const_iterator begin() const;
const_iterator end() const;
// Implementation
private:
Policy _policy;
};
// implement class methods an inner classes
template<typename Element, class Policy>
struct queue_concept<Element, Policy>::const_iterator
{
using iterator_type = typename Policy::container_type::const_iterator;
const_iterator(iterator_type iter = iterator_type {})
: _iter { std::move(iter) }
{}
const Element& operator*() const {
return *_iter;
}
const_iterator& operator++() {
std::advance(_iter, 1);
}
bool operator!=(const const_iterator& other) const {
return _iter != other._iter;
}
iterator_type _iter;
};
template<typename Element, class Policy>
void queue_concept<Element, Policy>::push_back(Element e)
{
_policy._data.push_back(std::move(e));
}
template<typename Element, class Policy>
typename queue_concept<Element, Policy>::const_iterator queue_concept<Element, Policy>::begin() const
{
return const_iterator { _policy._data.begin() };
}
template<typename Element, class Policy>
typename queue_concept<Element, Policy>::const_iterator queue_concept<Element, Policy>::end() const
{
return const_iterator { _policy._data.end() };
}
/// RUNTIME Polymorphic queue of objects of type Element
template<typename Element>
struct IQueue
{
struct const_iterator
{
struct Concept {
// virtual base class so make destructor virtual...
virtual ~Concept() = default;
virtual const Element& get_element() const = 0;
virtual void increment(std::size_t distance) = 0;
bool equal_to(const Concept& rhs)
{
if (this->get_type() == rhs.get_type()) {
return unsafe_is_equal(rhs);
}
return false;
}
virtual bool unsafe_is_equal(const Concept& rhs) const = 0;
virtual std::type_index get_type() const = 0;
// provide copy support
virtual std::unique_ptr<Concept> clone() const = 0;
};
template<class Iter>
struct Model : public Concept {
Model(Iter iter) : _iter { std::move(iter) }
{}
const Element& get_element() const override {
return *_iter;
}
void increment(std::size_t distance) override {
std::advance(_iter, distance);
}
bool unsafe_is_equal(const Concept& rhs) const override {
auto _rhs = static_cast<const Model&>(rhs);
return _iter == _rhs._iter;
}
std::type_index get_type() const override {
return std::type_index(typeid(*this));
}
std::unique_ptr<Concept> clone() const override {
return std::unique_ptr<Concept> { new Model(*this) };
}
private:
Iter _iter;
};
// constructor
template<class Iter>
const_iterator(Iter iter)
: _impl { new Model<Iter> { std::move(iter) } }
{}
// default constructor - constructs an invalid iterator
const_iterator()
{}
// provide copy support since impl is a unique_ptr
const_iterator(const const_iterator& other)
: _impl { other._impl ? other._impl->clone() : std::unique_ptr<Concept>{} }
{}
const_iterator& operator=(const_iterator& other)
{
auto p = other._impl ? other._impl->clone() : std::unique_ptr<Concept>{};
std::swap(_impl, p);
}
// since we provided copy support we must provide move support
const_iterator(const_iterator&& rhs) = default;
const_iterator& operator=(const_iterator&& rhs) = default;
const Element& operator*() const {
return _impl->get_element();
}
const_iterator& operator++() {
_impl->increment(1);
return *this;
}
bool operator!=(const const_iterator& rhs) const
{
return !(_impl->equal_to(*(rhs._impl)));
}
private:
std::unique_ptr<Concept> _impl;
};
virtual void push_back(Element e) = 0;
virtual const_iterator begin() const = 0;
virtual const_iterator end() const = 0;
};
template<class Element, class Policy>
struct QueueImpl : public IQueue<Element>
{
void push_back(Element e) override {
_policy._data.push_back(std::move(e));
}
typename IQueue<Element>::const_iterator begin() const override {
return typename IQueue<Element>::const_iterator { std::begin(_policy._data) };
}
typename IQueue<Element>::const_iterator end() const override {
return typename IQueue<Element>::const_iterator { std::end(_policy._data) };
}
Policy _policy;
};
template<class Element>
struct ResizingArrayPolicy
{
using container_type = std::vector<Element>;
container_type _data;
};
template<class Element>
struct LinkedListPolicy
{
using container_type = std::list<Element>;
container_type _data;
};
template<class Element>
std::unique_ptr<IQueue<Element>> make_poly_resizing_array_queue()
{
return std::unique_ptr<IQueue<Element>> { new QueueImpl<Element, ResizingArrayPolicy<Element>> };
}
template<class Element>
std::unique_ptr<IQueue<Element>> make_poly_linked_list_queue()
{
return std::unique_ptr<IQueue<Element>> { new QueueImpl<Element, LinkedListPolicy<Element>>{} };
}
template<class Element>
queue_concept<Element, ResizingArrayPolicy<Element>> make_static_resizing_array_queue()
{
return queue_concept<Element, ResizingArrayPolicy<Element>>{};
}
template<class Element>
queue_concept<Element, LinkedListPolicy<Element>> make_static_linked_list_queue()
{
return queue_concept<Element, LinkedListPolicy<Element>>{};
}
using namespace std;
int main()
{
// create the queues
auto pq1 = make_poly_resizing_array_queue<int>();
auto pq2 = make_poly_linked_list_queue<int>();
// put data in them
pq1->push_back(10);
pq1->push_back(20);
pq2->push_back(30);
pq2->push_back(40);
// prove that iterators are assignable and moveable
IQueue<int>::const_iterator it;
it = pq1->begin();
cout << *it << endl; // should print 10
auto i2 = pq2->begin();
it = move(i2);
cout << *it << endl; // should print 30
// prove that queues are polymorphic
auto queues = vector<unique_ptr<IQueue<int>>>{};
queues.push_back(move(pq1));
queues.push_back(move(pq2));
// print the vector of queues
for(const auto& queue_ptr : queues) {
for(const auto& item : *queue_ptr) {
cout << item << endl;
}
cout << endl;
}
// now the static versions
auto q1 = make_static_resizing_array_queue<int>();
auto q2 = make_static_linked_list_queue<int>();
q1.push_back(10);
q1.push_back(20);
q2.push_back(30);
q2.push_back(40);
cout << "static queues\n";
for(const auto& item : q1) {
cout << item << endl;
}
cout << endl;
for(const auto& item : q2) {
cout << item << endl;
}
return 0;
}
问题不清楚您是否真的需要运行时多态性（例如什么？）
一种方法可能类似于 C++ 容器使用的方法：有一个 class 来管理对象的 allocation/deallocation 和 construction/destruction。
template <typename T, class Allocator>
class Queue
{
Allocator myAllocator;
public:
void enqueue(T item)
{
myAllocator.push(item);
}
// other operations.
};
然后有类似的东西
template <class T, template <typename ...> class Container, class ... Args>
class BasicAllocator
{
Container<T, Args...> M_list;
public:
void push(T element)
{
M_list.push_back(element);
}
auto begin() -> decltype( std::begin(M_list) )
{ return std::begin(M_list); }
auto end() -> decltype( std::end(M_list) )
{ return std::end(M_list); }
};
template<class T>
using LinkedListAllocator = BasicAllocator<T, std::list>;
template<class T>
using LinkedListQueue = Queue<T, LinkedListAllocator<T>>;
实施 dequeue 可能有点棘手。
Live example
背景
这纯粹是为了教育目的。如果你不想看完整的背景，可以跳到底部的问题。
我已经编写了一个 Queue 接口（抽象 class），以及 2 个基于调整数组和链表大小的派生实现。
template <typename T>
class IQueue {
public:
virtual void enqueue(T item) = 0;
virtual T dequeue() = 0;
virtual bool isEmpty() = 0;
virtual int size() = 0;
}
template <typename T>
class LinkedListQueue : public IQueue<T> {...}
template <typename T>
class ResizingArrayQueue : public IQueue<T> {...}
我希望能够使用符合 STL 的迭代器遍历队列的元素（我知道队列不应该是可迭代的），所以我可以使用 for (auto e: c) 或 queue.begin() / queue.end().
因为我使用 运行-time 多态性，所以我不得不添加一个客户端迭代器 class 到 IQueue 并使用 Pimpl 习惯用法在派生队列中实例化实际实现特定的迭代器classes，以避免对象切片问题。
所以增强代码看起来像：
template <typename T>
class IQueue {
public:
virtual void enqueue(T item) = 0;
virtual T dequeue() = 0;
virtual bool isEmpty() = 0;
virtual int size() = 0;
public:
class IteratorImpl {
public:
virtual void increment () = 0;
virtual bool operator== (const IteratorImpl& other) const = 0;
virtual bool operator!= (const IteratorImpl& other) const = 0;
virtual T& operator* () const = 0;
virtual T& operator-> () const = 0;
virtual void swap (IteratorImpl& other) = 0;
virtual IteratorImpl* clone() = 0;
};
public:
class ClientIterator : public std::iterator<std::forward_iterator_tag, T> {
std::unique_ptr<IteratorImpl> impl;
public:
ClientIterator(const ClientIterator& other) : impl(other.impl->clone()) {}
ClientIterator(std::unique_ptr<IteratorImpl> it) : impl(std::move(it)) {}
void swap(ClientIterator& other) noexcept {
impl->swap(*(other.impl));
}
ClientIterator& operator++ () {
impl->increment();
return *this;
}
ClientIterator operator++ (int) {
ClientIterator tmp(*this);
impl->increment();
return tmp;
}
bool operator== (const ClientIterator& other) const {
return *impl == *other.impl;
}
bool operator!= (const ClientIterator& other) const {
return *impl != *other.impl;
}
T& operator* () const {
return **impl;
}
T& operator-> () const {
return **impl;
}
};
typedef ClientIterator iterator;
virtual iterator begin() = 0;
virtual iterator end() = 0;
};
并且派生的 classes 之一实现了 begin() / end() 方法和派生的 Iterator 实现：
template <typename T>
class LinkedListQueue : public IQueue<T> {
// ... queue implementation details.
public:
class LinkedListForwardIterator : public IQueue<T>::IteratorImpl {
// ... implementation that goes through linked list.
};
typename IQueue<T>::ClientIterator begin() {
std::unique_ptr<LinkedListForwardIterator> impl(new LinkedListForwardIterator(head));
return typename IQueue<T>::iterator(std::move(impl));
}
typename IQueue<T>::ClientIterator end() {
std::unique_ptr<LinkedListForwardIterator> impl(new LinkedListForwardIterator(nullptr));
return typename IQueue<T>::iterator(std::move(impl));
}
};
现在为了测试迭代器是否工作，我有以下两个函数：
template <typename T>
void testQueueImpl(std::shared_ptr<IQueue<T> > queue) {
queue->enqueue(1);
queue->enqueue(2);
queue->enqueue(3);
queue->enqueue(4);
queue->enqueue(5);
queue->enqueue(6);
std::cout << "Iterator behavior check 1st: ";
for (auto e: *queue) {
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << "Iterator behavior check 2nd: ";
for (auto it = queue->begin(); it != queue->end(); it++) {
std::cout << *it << " ";
}
}
void testQueue() {
auto queue = std::make_shared<LinkedListQueue<int> >();
testQueueImpl<int>(queue);
auto queue2 = std::make_shared<ResizingArrayQueue<int> >();
testQueueImpl<int>(queue2);
}
问题
如何摆脱 运行 时间多态性（删除 IQueue，删除迭代器 Pimpl 实现），并重写 testQueue() / testQueueImpl() 函数以便：
- 这些函数可以成功测试 Stack 实现和 Stack 迭代器，而无需基 class 指针。
- LinkedListQueue 和 ResizingArrayQueue 都遵循某种编译时接口（存在 enqueue、dequeue、isEmpty、size 方法，存在 begin / end 方法，两个 classes 都包含有效的迭代器 classes)?
可能的解决方案
对于 1) 看来我可以简单地将模板参数更改为整个容器，程序编译成功并且 运行s。但这不会检查 begin() / end() / enqueue() 方法是否存在。
对于2），从我在互联网上可以找到的内容来看，相关解决方案似乎涉及类型特征/ SFINAE /或概念（容器概念，前向迭代器概念）。似乎 Boost Concepts 库允许注释 class 以符合容器概念，但我对用于教育目的的自包含解决方案（除 STL 外没有外部库）感兴趣。
template <typename Container>
void testQueueImpl(Container queue) {
queue->enqueue(1);
queue->enqueue(2);
queue->enqueue(3);
queue->enqueue(4);
queue->enqueue(5);
queue->enqueue(6);
std::cout << "Size: " << queue->size() << std::endl;
std::cout << "Iterator behavior check 1st: ";
for (auto e: *queue) {
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << "Iterator behavior check 2nd: ";
for (auto it = queue->begin(); it != queue->end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl;
}
void testQueue() {
auto queue = std::make_shared<LinkedListQueue<int> >();
testQueueImpl<std::shared_ptr<LinkedListQueue<int> > >(queue);
auto queue2 = std::make_shared<ResizingArrayQueue<int> >();
testQueueImpl<std::shared_ptr<ResizingArrayQueue<int> > >(queue2);
}
这是一个最简单的可编译示例，说明您可能希望如何做到这一点。
请注意，目前此示例仅支持 const begin() 和 const end()。
添加更多方法和可变迭代器是 reader
的练习编辑：提供了共享相同策略的编译时和运行时多态队列的工作示例类。
#include <iostream>
#include <list>
#include <vector>
#include <memory>
#include <typeinfo>
#include <typeindex>
/// COMPILE TIME Polymorphic queue of objects of type Element
template<typename Element, class Policy>
struct queue_concept
{
// Define interface
struct const_iterator;
void push_back(Element e);
const_iterator begin() const;
const_iterator end() const;
// Implementation
private:
Policy _policy;
};
// implement class methods an inner classes
template<typename Element, class Policy>
struct queue_concept<Element, Policy>::const_iterator
{
using iterator_type = typename Policy::container_type::const_iterator;
const_iterator(iterator_type iter = iterator_type {})
: _iter { std::move(iter) }
{}
const Element& operator*() const {
return *_iter;
}
const_iterator& operator++() {
std::advance(_iter, 1);
}
bool operator!=(const const_iterator& other) const {
return _iter != other._iter;
}
iterator_type _iter;
};
template<typename Element, class Policy>
void queue_concept<Element, Policy>::push_back(Element e)
{
_policy._data.push_back(std::move(e));
}
template<typename Element, class Policy>
typename queue_concept<Element, Policy>::const_iterator queue_concept<Element, Policy>::begin() const
{
return const_iterator { _policy._data.begin() };
}
template<typename Element, class Policy>
typename queue_concept<Element, Policy>::const_iterator queue_concept<Element, Policy>::end() const
{
return const_iterator { _policy._data.end() };
}
/// RUNTIME Polymorphic queue of objects of type Element
template<typename Element>
struct IQueue
{
struct const_iterator
{
struct Concept {
// virtual base class so make destructor virtual...
virtual ~Concept() = default;
virtual const Element& get_element() const = 0;
virtual void increment(std::size_t distance) = 0;
bool equal_to(const Concept& rhs)
{
if (this->get_type() == rhs.get_type()) {
return unsafe_is_equal(rhs);
}
return false;
}
virtual bool unsafe_is_equal(const Concept& rhs) const = 0;
virtual std::type_index get_type() const = 0;
// provide copy support
virtual std::unique_ptr<Concept> clone() const = 0;
};
template<class Iter>
struct Model : public Concept {
Model(Iter iter) : _iter { std::move(iter) }
{}
const Element& get_element() const override {
return *_iter;
}
void increment(std::size_t distance) override {
std::advance(_iter, distance);
}
bool unsafe_is_equal(const Concept& rhs) const override {
auto _rhs = static_cast<const Model&>(rhs);
return _iter == _rhs._iter;
}
std::type_index get_type() const override {
return std::type_index(typeid(*this));
}
std::unique_ptr<Concept> clone() const override {
return std::unique_ptr<Concept> { new Model(*this) };
}
private:
Iter _iter;
};
// constructor
template<class Iter>
const_iterator(Iter iter)
: _impl { new Model<Iter> { std::move(iter) } }
{}
// default constructor - constructs an invalid iterator
const_iterator()
{}
// provide copy support since impl is a unique_ptr
const_iterator(const const_iterator& other)
: _impl { other._impl ? other._impl->clone() : std::unique_ptr<Concept>{} }
{}
const_iterator& operator=(const_iterator& other)
{
auto p = other._impl ? other._impl->clone() : std::unique_ptr<Concept>{};
std::swap(_impl, p);
}
// since we provided copy support we must provide move support
const_iterator(const_iterator&& rhs) = default;
const_iterator& operator=(const_iterator&& rhs) = default;
const Element& operator*() const {
return _impl->get_element();
}
const_iterator& operator++() {
_impl->increment(1);
return *this;
}
bool operator!=(const const_iterator& rhs) const
{
return !(_impl->equal_to(*(rhs._impl)));
}
private:
std::unique_ptr<Concept> _impl;
};
virtual void push_back(Element e) = 0;
virtual const_iterator begin() const = 0;
virtual const_iterator end() const = 0;
};
template<class Element, class Policy>
struct QueueImpl : public IQueue<Element>
{
void push_back(Element e) override {
_policy._data.push_back(std::move(e));
}
typename IQueue<Element>::const_iterator begin() const override {
return typename IQueue<Element>::const_iterator { std::begin(_policy._data) };
}
typename IQueue<Element>::const_iterator end() const override {
return typename IQueue<Element>::const_iterator { std::end(_policy._data) };
}
Policy _policy;
};
template<class Element>
struct ResizingArrayPolicy
{
using container_type = std::vector<Element>;
container_type _data;
};
template<class Element>
struct LinkedListPolicy
{
using container_type = std::list<Element>;
container_type _data;
};
template<class Element>
std::unique_ptr<IQueue<Element>> make_poly_resizing_array_queue()
{
return std::unique_ptr<IQueue<Element>> { new QueueImpl<Element, ResizingArrayPolicy<Element>> };
}
template<class Element>
std::unique_ptr<IQueue<Element>> make_poly_linked_list_queue()
{
return std::unique_ptr<IQueue<Element>> { new QueueImpl<Element, LinkedListPolicy<Element>>{} };
}
template<class Element>
queue_concept<Element, ResizingArrayPolicy<Element>> make_static_resizing_array_queue()
{
return queue_concept<Element, ResizingArrayPolicy<Element>>{};
}
template<class Element>
queue_concept<Element, LinkedListPolicy<Element>> make_static_linked_list_queue()
{
return queue_concept<Element, LinkedListPolicy<Element>>{};
}
using namespace std;
int main()
{
// create the queues
auto pq1 = make_poly_resizing_array_queue<int>();
auto pq2 = make_poly_linked_list_queue<int>();
// put data in them
pq1->push_back(10);
pq1->push_back(20);
pq2->push_back(30);
pq2->push_back(40);
// prove that iterators are assignable and moveable
IQueue<int>::const_iterator it;
it = pq1->begin();
cout << *it << endl; // should print 10
auto i2 = pq2->begin();
it = move(i2);
cout << *it << endl; // should print 30
// prove that queues are polymorphic
auto queues = vector<unique_ptr<IQueue<int>>>{};
queues.push_back(move(pq1));
queues.push_back(move(pq2));
// print the vector of queues
for(const auto& queue_ptr : queues) {
for(const auto& item : *queue_ptr) {
cout << item << endl;
}
cout << endl;
}
// now the static versions
auto q1 = make_static_resizing_array_queue<int>();
auto q2 = make_static_linked_list_queue<int>();
q1.push_back(10);
q1.push_back(20);
q2.push_back(30);
q2.push_back(40);
cout << "static queues\n";
for(const auto& item : q1) {
cout << item << endl;
}
cout << endl;
for(const auto& item : q2) {
cout << item << endl;
}
return 0;
}
问题不清楚您是否真的需要运行时多态性（例如什么？）
一种方法可能类似于 C++ 容器使用的方法：有一个 class 来管理对象的 allocation/deallocation 和 construction/destruction。
template <typename T, class Allocator>
class Queue
{
Allocator myAllocator;
public:
void enqueue(T item)
{
myAllocator.push(item);
}
// other operations.
};
然后有类似的东西
template <class T, template <typename ...> class Container, class ... Args>
class BasicAllocator
{
Container<T, Args...> M_list;
public:
void push(T element)
{
M_list.push_back(element);
}
auto begin() -> decltype( std::begin(M_list) )
{ return std::begin(M_list); }
auto end() -> decltype( std::end(M_list) )
{ return std::end(M_list); }
};
template<class T>
using LinkedListAllocator = BasicAllocator<T, std::list>;
template<class T>
using LinkedListQueue = Queue<T, LinkedListAllocator<T>>;
实施 dequeue 可能有点棘手。
Live example