C++迭代器模式与算法

C++迭代器模式与算法

迭代器是STL中连接容器和算法的桥梁。通过统一的迭代器接口，算法可以独立于容器实现。理解迭代器的分类和用法对于高效使用STL至关重要。

迭代器分为输入、输出、前向、双向和随机访问五种类别。

#include
#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 tmp(*this); ++ptr_; return tmp; }
Iterator& operator--() { --ptr_; return *this; }
Iterator operator--(int) { Iterator tmp(*this); --ptr_; return tmp; }

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_; }
};

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

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

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

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

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

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

反向迭代器从后向前遍历。

void reverse_iterator_demo() {
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 << "\nReverse: ";
for (auto it = vec.rbegin(); it != vec.rend(); ++it)
std::cout << *it << " ";
std::cout << "\n";
}

流迭代器操作输入输出流。

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

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

std::ostream_iterator out(std::cout, " ");
std::copy(nums.begin(), nums.end(), out);
std::cout << "\n";
}

插入迭代器自动插入元素。

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

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

std::list lst;
std::copy(source.begin(), source.end(), std::front_inserter(lst));

std::set set;
std::copy(source.begin(), source.end(), std::inserter(set, set.end()));

std::cout << "dest: ";
for (int n : dest) std::cout << n << " ";
std::cout << "\nlst: ";
for (int n : lst) std::cout << n << " ";
std::cout << "\n";
}

迭代器适配器修改行为。

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

std::transform(data.begin(), data.end(), std::back_inserter(dest),
[](int n) { return n * 2; });

auto it = std::find(data.begin(), data.end(), 3);
auto dist = std::distance(data.begin(), it);
std::cout << "Found 3 at distance: " << dist << "\n";

std::advance(it, 2);
std::cout << "After advance: " << *it << "\n";
}

自定义迭代器实现范围。

class Range {
int start_, end_, step_;
public:
class Iterator {
int current_, step_;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = int;
using difference_type = int;

Iterator(int cur, int step) : current_(cur), step_(step) {}
int operator*() const { return current_; }
Iterator& operator++() { current_ += step_; return *this; }
bool operator!=(const Iterator& other) const { return current_ != other.current_; }
};

Range(int end) : start_(0), end_(end), step_(1) {}
Range(int start, int end, int step = 1) : start_(start), end_(end), step_(step) {}

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

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

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

迭代器类别标签用于算法优化。

template
void advance_impl(Iterator& it, int n, std::random_access_iterator_tag) {
it += n;
std::cout << "Random access advance\n";
}

template
void advance_impl(Iterator& it, int n, std::bidirectional_iterator_tag) {
for (int i = 0; i < n; ++i) ++it;
std::cout << "Bidirectional advance\n";
}

void iterator_category_demo() {
std::vector vec = {1, 2, 3};
auto vit = vec.begin();
advance_impl(vit, 2, std::random_access_iterator_tag{});

std::list lst = {1, 2, 3};
auto lit = lst.begin();
advance_impl(lit, 2, std::bidirectional_iterator_tag{});
}

迭代器是C++泛型编程的基石，理解迭代器有助于编写通用高效的算法。