バックグラウンド
これは純粋に教育目的のためです。背景全体を読みたくない場合は、下部の質問にスキップできます。
Queue インターフェイス (抽象クラス) と、配列のサイズ変更とリンク リストに基づく 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)orを使用できqueue.begin()ますqueue.end()。
私はランタイム ポリモーフィズムを使用しているため、クライアント イテレータ クラスを追加しIQueue、Pimpl イディオムを使用して、派生キュー クラスで実際の実装固有のイテレータをインスタンス化し、オブジェクトのスライスの問題を回避する必要がありました。したがって、拡張コードは次のようになります。
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;
};
派生クラスの 1 つは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));
}
};
イテレータが機能することをテストするために、次の 2 つの関数があります。
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 イテレーターを正常にテストできます。
- LinkedListQueue と ResizingArrayQueue の両方がある種のコンパイル時インターフェースに準拠していること (enqueue、dequeue、isEmpty、size メソッドが存在し、begin / end メソッドが存在し、両方のクラスに有効な反復子クラスが含まれている)?
考えられる解決策
1) の場合、テンプレート引数をコンテナー全体に変更するだけで、プログラムは正常にコンパイルされて実行されるようです。しかし、これは begin() / end() / enqueue() メソッドの存在をチェックしません。
2）インターネットで見つけたものから、関連するソリューションには、タイプの特徴/ SFINAE /または概念（コンテナの概念、フォワードイテレータの概念）が含まれるようです。Boost Concepts ライブラリを使用すると、クラスに注釈を付けてコンテナの概念に準拠させることができるようですが、教育目的で自己完結型のソリューション (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);
}