Last active
November 16, 2023 17:58
-
-
Save pabloariasal/12dd5fa54d136e0507ef928a4f9f5206 to your computer and use it in GitHub Desktop.
Example implementation of a C++ Iterator Facade using CRTP
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <array> | |
#include <cassert> | |
#include <catch2/catch_test_macros.hpp> | |
#include <cstddef> | |
#include <iterator> | |
#include <memory> | |
#include <type_traits> | |
// Facade for input and bidirectional iterator, but can be expanded to any type | |
// of iterator | |
template <typename Derived, typename Value, typename Category, | |
typename Reference = Value&, typename Distance = std::ptrdiff_t> | |
class IteratorFacade { | |
public: | |
using value_type = std::remove_const_t<Value>; | |
using reference = Reference; | |
using pointer = Value*; | |
using difference_type = Distance; | |
using iterator_category = Category; | |
// input iterator | |
reference operator*() const { return asDerived().dereference(); } | |
pointer operator->() const { return &asDerived().dereference(); } | |
Derived& operator++() { | |
asDerived().increment(); | |
return asDerived(); | |
} | |
Derived operator++(int) { | |
Derived result(asDerived()); | |
asDerived().increment(); | |
return result; | |
} | |
// Barton-Nackman Trick | |
friend bool operator==(const Derived& lhs, const Derived& rhs) { | |
return lhs.equals(rhs); | |
} | |
friend bool operator!=(const Derived& lhs, const Derived& rhs) { | |
return !(lhs == rhs); | |
} | |
// bidirectional iterator | |
Derived& operator--() { | |
asDerived().decrement(); | |
return asDerived(); | |
} | |
Derived operator--(int) { | |
Derived result(asDerived()); | |
asDerived().decrement(); | |
return result; | |
} | |
private: | |
Derived& asDerived() { return *static_cast<Derived*>(this); } | |
const Derived& asDerived() const { | |
return *static_cast<const Derived*>(this); | |
} | |
}; | |
// Example: Input iterator (implements only partially the interface) | |
struct ListNode { | |
int value; | |
ListNode* next = nullptr; | |
~ListNode() { delete next; } | |
}; | |
class ListNodeIterator | |
: public IteratorFacade<ListNodeIterator, int, std::input_iterator_tag> { | |
public: | |
ListNodeIterator(ListNode* node) : node_{node} {} | |
int& dereference() const { return node_->value; } | |
void increment() { node_ = node_->next; } | |
bool equals(const ListNodeIterator& other) const { | |
return node_ == other.node_; | |
} | |
private: | |
ListNode* node_; | |
}; | |
ListNodeIterator begin(ListNode* node) { return ListNodeIterator{node}; } | |
ListNodeIterator end(ListNode*) { return ListNodeIterator{nullptr}; } | |
std::unique_ptr<ListNode> createSingleListOfSize(int n) { | |
assert(n > 0); | |
auto node = std::unique_ptr<ListNode>(new ListNode{n, nullptr}); | |
ListNode* last = node.get(); | |
while (n > 1) { | |
last->next = new ListNode{--n, nullptr}; | |
last = last->next; | |
} | |
return node; | |
} | |
TEST_CASE("Input iterators", "[input_iterator]") { | |
auto node = createSingleListOfSize(7); | |
REQUIRE(std::distance(begin(node.get()), end(node.get())) == 7); | |
auto b = begin(node.get()); | |
REQUIRE(*(b++) == 7); | |
REQUIRE(*(++b) == 5); | |
REQUIRE(*b == 5); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Compiler explorer link here