Iterators in C++ are a fundamental part of the Standard Template Library (STL). They provide a uniform way to access elements of a collection, such as arrays, vectors, lists, and more. Custom iterators are essential when you create your own data structures and want them to work seamlessly with the standard algorithms provided by the STL. In this tutorial, we’ll explore how to implement custom iterators in C++.
1. Introduction to Iterators
Iterators are objects that allow a programmer to traverse through elements of a collection. They are designed to provide a way to access elements without exposing the underlying representation of the collection.
STL Iterator Example
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}Code language: C++ (cpp)In the above code, vec.begin() returns an iterator to the beginning of the vector, and vec.end() returns an iterator to one past the last element. The iterator is used to traverse and print each element.
2. Types of Iterators
The STL defines several types of iterators based on their capabilities:
- Input Iterator: Read-only access, single pass.
- Output Iterator: Write-only access, single pass.
- Forward Iterator: Read and write access, multiple passes, can move only forward.
- Bidirectional Iterator: Read and write access, multiple passes, can move both forward and backward.
- Random Access Iterator: Read and write access, multiple passes, can move freely (supports arithmetic operations like
+,-).
3. Requirements for Custom Iterators
To create a custom iterator, you need to follow certain conventions and implement specific functions. These conventions ensure that your iterator will be compatible with STL algorithms and containers.
Iterator Traits
Iterator traits are used to provide information about the iterator. They define types such as value_type, difference_type, pointer, reference, and iterator_category.
Basic Operations
A custom iterator must support the following operations:
- Dereferencing: Access the value pointed to by the iterator using the
*operator. - Increment: Move to the next element using the
++operator. - Equality/Inequality: Compare iterators using
==and!=operators.
4. Implementing a Custom Iterator
Let’s start with a basic custom iterator for a simple container.
Iterator Traits
Define the necessary traits for the iterator.
#include <iterator>
template <typename T>
class SimpleIterator {
public:
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
using iterator_category = std::forward_iterator_tag;
SimpleIterator(pointer ptr) : m_ptr(ptr) {}
reference operator*() const { return *m_ptr; }
pointer operator->() { return m_ptr; }
// Prefix increment
SimpleIterator& operator++() {
m_ptr++;
return *this;
}
// Postfix increment
SimpleIterator operator++(int) {
SimpleIterator tmp = *this;
++(*this);
return tmp;
}
friend bool operator==(const SimpleIterator& a, const SimpleIterator& b) {
return a.m_ptr == b.m_ptr;
}
friend bool operator!=(const SimpleIterator& a, const SimpleIterator& b) {
return a.m_ptr != b.m_ptr;
}
private:
pointer m_ptr;
};Code language: C++ (cpp)Basic Structure
Now, let’s create a simple container that uses this iterator.
template <typename T>
class SimpleContainer {
public:
using iterator = SimpleIterator<T>;
SimpleContainer(std::initializer_list<T> init) {
size = init.size();
data = new T[size];
std::copy(init.begin(), init.end(), data);
}
~SimpleContainer() {
delete[] data;
}
iterator begin() { return iterator(data); }
iterator end() { return iterator(data + size); }
private:
T* data;
size_t size;
};Code language: C++ (cpp)Iterator Operations
In the SimpleIterator class, we have defined basic iterator operations such as dereferencing, incrementing, and comparison. The SimpleContainer class uses this iterator.
5. Example: Custom Iterator for a Simple Container
Let’s put it all together with a complete example.
#include <iostream>
#include <algorithm>
int main() {
SimpleContainer<int> container = {1, 2, 3, 4, 5};
for (auto it = container.begin(); it != container.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
std::for_each(container.begin(), container.end(), [](int &n) { n *= 2; });
for (auto it = container.begin(); it != container.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}Code language: C++ (cpp)This example demonstrates how to create and use a custom iterator with a simple container.
6. Advanced Features
Input and Output Iterators
Input and output iterators have specific requirements. Let’s implement an input iterator.
template <typename T>
class InputIterator {
public:
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
using iterator_category = std::input_iterator_tag;
InputIterator(pointer ptr) : m_ptr(ptr) {}
reference operator*() const { return *m_ptr; }
pointer operator->() { return m_ptr; }
InputIterator& operator++() {
m_ptr++;
return *this;
}
InputIterator operator++(int) {
InputIterator tmp = *this;
++(*this);
return tmp;
}
friend bool operator==(const InputIterator& a, const InputIterator& b) {
return a.m_ptr == b.m_ptr;
}
friend bool operator!=(const InputIterator& a, const InputIterator& b) {
return a.m_ptr != b.m_ptr;
}
private:
pointer m_ptr;
};Code language: C++ (cpp)Forward, Bidirectional, and Random Access Iterators
Bidirectional and random access iterators build on top of forward iterators by adding more functionality.
Bidirectional Iterator
template <typename T>
class BidirectionalIterator {
public:
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
using iterator_category = std::bidirectional_iterator_tag;
BidirectionalIterator(pointer ptr) : m_ptr(ptr) {}
reference operator*() const { return *m_ptr; }
pointer operator->() { return m_ptr; }
BidirectionalIterator& operator++() {
m_ptr++;
return *this;
}
BidirectionalIterator operator++(int) {
BidirectionalIterator tmp = *this;
++(*this);
return tmp;
}
BidirectionalIterator& operator--() {
m_ptr--;
return *this;
}
BidirectionalIterator operator--(int) {
BidirectionalIterator tmp = *this;
--(*this);
return tmp;
}
friend bool operator==(const BidirectionalIterator& a, const BidirectionalIterator& b) {
return a.m_ptr == b.m_ptr;
}
friend bool operator!=(const BidirectionalIterator& a, const BidirectionalIterator& b) {
return a.m_ptr != b.m_ptr;
}
private:
pointer m_ptr;
};Code language: C++ (cpp)Random Access Iterator
template <typename T>
class RandomAccessIterator {
public:
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
RandomAccessIterator(pointer ptr) : m_ptr(ptr) {}
reference operator*() const { return *m_ptr; }
pointer operator->() { return m_ptr; }
RandomAccessIterator& operator++() {
m_ptr++;
return *this;
}
RandomAccessIterator operator++(int) {
RandomAccessIterator tmp = *this;
++(*this);
return tmp;
}
RandomAccessIterator& operator--() {
m_ptr--;
return *this;
}
RandomAccessIterator operator--(int) {
RandomAccessIterator tmp = *this;
--(*this);
return tmp;
}
RandomAccessIterator operator+(difference_type n) const {
return RandomAccessIterator(m_ptr + n);
}
RandomAccessIterator operator-(difference_type n) const {
return RandomAccessIterator(m_ptr - n);
}
difference_type operator-(const RandomAccessIterator& other
) const {
return m_ptr - other.m_ptr;
}
friend bool operator==(const RandomAccessIterator& a, const RandomAccessIterator& b) {
return a.m_ptr == b.m_ptr;
}
friend bool operator!=(const RandomAccessIterator& a, const RandomAccessIterator& b) {
return a.m_ptr != b.m_ptr;
}
private:
pointer m_ptr;
};Code language: C++ (cpp)7. Testing and Debugging Iterators
Testing iterators involves checking their behavior with STL algorithms and custom loops. Use unit tests to verify that your iterator behaves as expected in various scenarios.
Example Test
#include <cassert>
#include <algorithm>
#include <vector>
void test_simple_iterator() {
SimpleContainer<int> container = {1, 2, 3, 4, 5};
auto it = container.begin();
assert(*it == 1);
++it;
assert(*it == 2);
it++;
assert(*it == 3);
std::for_each(container.begin(), container.end(), [](int &n) { n *= 2; });
assert(*(container.begin()) == 2);
assert(*(++container.begin()) == 4);
}
int main() {
test_simple_iterator();
std::cout << "All tests passed!" << std::endl;
return 0;
}Code language: C++ (cpp)8. Best Practices
- Follow STL Conventions: Ensure your iterators follow the STL conventions for compatibility with standard algorithms.
- Iterator Traits: Define the necessary iterator traits for your custom iterator.
- Increment and Decrement: Implement both prefix and postfix increment and decrement operators where applicable.
- Equality and Inequality: Implement
operator==andoperator!=to compare iterators. - Testing: Thoroughly test your iterators with various STL algorithms and custom tests to ensure correctness.
9. Conclusion
Custom iterators are powerful tools for creating seamless and efficient traversal mechanisms for your custom data structures. By adhering to the conventions and implementing the necessary operations, you can create iterators that integrate smoothly with the C++ Standard Library. This tutorial covered the basics of creating custom iterators, from defining iterator traits to implementing various types of iterators. With practice and careful design, you can leverage custom iterators to enhance the usability and performance of your custom containers in C++.