C++迭代器设计模式

C++迭代器设计模式

迭代器是STL的核心组件之一，它提供了统一的方式来遍历不同类型的容器。迭代器模式将容器的遍历逻辑与容器本身分离，使算法可以独立于容器实现。

迭代器的基本概念包括五种类型：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。

#include
#include
#include
#include
#include

template
class SimpleVector {
T* data_;
size_t size_;
size_t capacity_;

public:
class Iterator {
T* ptr_;

public:
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;

explicit Iterator(T* ptr) : ptr_(ptr) {}

reference operator*() const { return *ptr_; }
pointer operator->() const { return ptr_; }

Iterator& operator++() {
++ptr_;
return *this;
}

Iterator operator++(int) {
Iterator temp = *this;
++ptr_;
return temp;
}

Iterator& operator--() {
--ptr_;
return *this;
}

Iterator operator--(int) {
Iterator temp = *this;
--ptr_;
return temp;
}

Iterator& operator+=(difference_type n) {
ptr_ += n;
return *this;
}

Iterator& operator-=(difference_type n) {
ptr_ -= n;
return *this;
}

Iterator operator+(difference_type n) const {
return Iterator(ptr_ + n);
}

Iterator operator-(difference_type n) const {
return Iterator(ptr_ - n);
}

difference_type operator-(const Iterator& other) const {
return ptr_ - other.ptr_;
}

reference operator[](difference_type n) const {
return ptr_[n];
}

bool operator==(const Iterator& other) const {
return ptr_ == other.ptr_;
}

bool operator!=(const Iterator& other) const {
return ptr_ != other.ptr_;
}

bool operator<(const Iterator& other) const {
return ptr_ < other.ptr_;
}

bool operator>(const Iterator& other) const {
return ptr_ > other.ptr_;
}

bool operator<=(const Iterator& other) const {
return ptr_ <= other.ptr_;
}

bool operator>=(const Iterator& other) const {
return ptr_ >= other.ptr_;
}
};

SimpleVector() : data_(nullptr), size_(0), capacity_(0) {}

explicit SimpleVector(size_t size)
: data_(new T[size]), size_(size), capacity_(size) {}

~SimpleVector() {
delete[] data_;
}

void push_back(const T& value) {
if (size_ == capacity_) {
size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;
T* new_data = new T[new_capacity];
for (size_t i = 0; i < size_; ++i) {
new_data[i] = data_[i];
}
delete[] data_;
data_ = new_data;
capacity_ = new_capacity;
}
data_[size_++] = value;
}

Iterator begin() { return Iterator(data_); }
Iterator end() { return Iterator(data_ + size_); }

size_t size() const { return size_; }
};

void random_access_iterator_example() {
SimpleVector vec;
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}

std::cout << "Forward iteration: ";
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";

std::cout << "Using algorithms: ";
std::sort(vec.begin(), vec.end(), std::greater());
for (const auto& val : vec) {
std::cout << val << " ";
}
std::cout << "\n";
}

双向迭代器支持前向和后向遍历。

template
class DoublyLinkedList {
struct Node {
T data;
Node* prev;
Node* next;

Node(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};

Node* head_;
Node* tail_;
size_t size_;

public:
class Iterator {
Node* node_;

public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;

explicit Iterator(Node* node) : node_(node) {}

reference operator*() const { return node_->data; }
pointer operator->() const { return &node_->data; }

Iterator& operator++() {
node_ = node_->next;
return *this;
}

Iterator operator++(int) {
Iterator temp = *this;
node_ = node_->next;
return temp;
}

Iterator& operator--() {
node_ = node_->prev;
return *this;
}

Iterator operator--(int) {
Iterator temp = *this;
node_ = node_->prev;
return temp;
}

bool operator==(const Iterator& other) const {
return node_ == other.node_;
}

bool operator!=(const Iterator& other) const {
return node_ != other.node_;
}
};

DoublyLinkedList() : head_(nullptr), tail_(nullptr), size_(0) {}

~DoublyLinkedList() {
Node* current = head_;
while (current) {
Node* next = current->next;
delete current;
current = next;
}
}

void push_back(const T& value) {
Node* new_node = new Node(value);
if (!tail_) {
head_ = tail_ = new_node;
} else {
tail_->next = new_node;
new_node->prev = tail_;
tail_ = new_node;
}
++size_;
}

Iterator begin() { return Iterator(head_); }
Iterator end() { return Iterator(nullptr); }

size_t size() const { return size_; }
};

void bidirectional_iterator_example() {
DoublyLinkedList list;
list.push_back("first");
list.push_back("second");
list.push_back("third");

std::cout << "List contents: ";
for (const auto& item : list) {
std::cout << item << " ";
}
std::cout << "\n";
}

反向迭代器允许从后向前遍历容器。

void reverse_iterator_example() {
std::vector vec = {1, 2, 3, 4, 5};

std::cout << "Forward: ";
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";

std::cout << "Reverse: ";
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";
}

迭代器适配器可以修改迭代器的行为。

void iterator_adapters() {
std::vector source = {1, 2, 3, 4, 5};
std::vector dest;

std::copy(source.begin(), source.end(), std::back_inserter(dest));

std::cout << "Copied: ";
for (int val : dest) {
std::cout << val << " ";
}
std::cout << "\n";

std::vector dest2(5);
std::copy(source.begin(), source.end(), dest2.begin());

std::cout << "Copied to preallocated: ";
for (int val : dest2) {
std::cout << val << " ";
}
std::cout << "\n";
}

流迭代器允许将流作为容器使用。

#include

void stream_iterator_example() {
std::istringstream iss("10 20 30 40 50");
std::vector numbers;

std::copy(std::istream_iterator(iss),
std::istream_iterator(),
std::back_inserter(numbers));

std::cout << "Read from stream: ";
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << "\n";

std::ostringstream oss;
std::copy(numbers.begin(), numbers.end(),
std::ostream_iterator(oss, " "));

std::cout << "Written to stream: " << oss.str() << "\n";
}

自定义迭代器可以实现特殊的遍历逻辑。

template
class Range {
T begin_;
T end_;
T step_;

public:
class Iterator {
T current_;
T step_;

public:
using iterator_category = std::forward_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = const T*;
using reference = const T&;

Iterator(T current, T step) : current_(current), step_(step) {}

reference operator*() const { return current_; }
pointer operator->() const { return ¤t_; }

Iterator& operator++() {
current_ += step_;
return *this;
}

Iterator operator++(int) {
Iterator temp = *this;
current_ += step_;
return temp;
}

bool operator==(const Iterator& other) const {
return current_ == other.current_;
}

bool operator!=(const Iterator& other) const {
return current_ != other.current_;
}
};

Range(T begin, T end, T step = 1)
: begin_(begin), end_(end), step_(step) {}

Iterator begin() const { return Iterator(begin_, step_); }
Iterator end() const { return Iterator(end_, step_); }
};

void custom_iterator_example() {
std::cout << "Range 0 to 10: ";
for (int i : Range(0, 10)) {
std::cout << i << " ";
}
std::cout << "\n";

std::cout << "Range 0 to 20 step 2: ";
for (int i : Range(0, 20, 2)) {
std::cout << i << " ";
}
std::cout << "\n";
}

迭代器特性允许算法查询迭代器的属性。

template
void print_iterator_category(Iterator) {
using category = typename std::iterator_traits::iterator_category;

if (std::is_same::value) {
std::cout << "Random access iterator\n";
} else if (std::is_same::value) {
std::cout << "Bidirectional iterator\n";
} else if (std::is_same::value) {
std::cout << "Forward iterator\n";
}
}

void iterator_traits_example() {
std::vector vec;
std::list lst;

print_iterator_category(vec.begin());
print_iterator_category(lst.begin());
}

迭代器模式是STL设计的核心，理解迭代器的类型和用法对于高效使用STL至关重要。