C++ Polymorphic Iterators in Abstract Base Class with Custom Child Implementations

Question

I'm working on a C++ project where I have an abstract base class Store that represents a container of Bin objects. Each subclass of Store (e.g., DenseStore, SparseStore) uses a different internal data layout to store its non-empty bins. I want to provide bidirectional iteration over the non-empty bins in ascending or descending order, via standard C++ constructs like:

template<typename Allocator>
class Store {
public:
  using allocator_type = Allocator;

  virtual ~Store() = default;
  virtual void add(int index) = 0;
  virtual void add(int index, uint64_t count) = 0;
  virtual void add(const Bin& bin) = 0;
  virtual Store* copy() const = 0;
  virtual void clear() = 0;
  virtual bool is_empty() const = 0;
  virtual int get_max_index() const = 0;
  virtual int get_min_index() const = 0;
  virtual uint64_t get_total_count() const = 0;
  virtual void merge(const Store& other) = 0;

  // Iterators
  using const_iterator = ???;
  virtual const_iterator begin() const = 0;
  virtual const_iterator end() const = 0;

  using const_reverse_iterator = ???;
  virtual const_reverse_iterator rbegin() const = 0;
  virtual const_reverse_iterator rend() const = 0;
};

Is there a clean, idiomatic way to implement polymorphic, STL-style iteration in this case?

Using void as a placeholder for const_iterator.
Creating a base class like BinConstIterator, and returning std::unique_ptr<BinConstIterator> from begin() and end(). It works, but it’s ugly and not compatible with STL algorithms.

Alan Birtles · Accepted Answer · 2025-08-27 17:30:23Z

You can implement this by delegating the implementation of the iterator methods to virtual methods on the base class:

#include <cstdint>
#include <vector>
#include <list>
#include <variant>
#include <iostream>

struct Bin
{
    int value;
};

class Store {
public:
  virtual ~Store() = default;

  // Iterators
  class const_iterator;
  virtual const_iterator begin() const = 0;
  virtual const_iterator end() const = 0;

protected:
  virtual void increment(const_iterator&) const = 0;
  virtual const Bin& dereference(const_iterator&) const = 0;
};

class VectorStore : public Store {
public:
  VectorStore()
  :vector{{1},{2},{3},{4}}
  {
  }

  const_iterator begin() const override;
  const_iterator end() const override;

  using const_iterator_state = std::vector<Bin>::const_iterator;

protected:
  void increment(const_iterator&) const override;
  const Bin& dereference(const_iterator&) const override;

private:
  std::vector<Bin> vector;
};

class ListStore : public Store {
public:
  ListStore()
  :list{{2},{4},{6},{8}}
  {
  }

  const_iterator begin() const override;
  const_iterator end() const override;

  using const_iterator_state = std::list<Bin>::const_iterator;

protected:
  void increment(const_iterator&) const override;
  const Bin& dereference(const_iterator&) const override;

private:
  std::list<Bin> list;
};

class Store::const_iterator
{
public:
    bool operator == (const Store::const_iterator& other)
    {
        return store == other.store && state == other.state;
    }

    bool operator != (const Store::const_iterator& other)
    {
        return !(*this == other);
    }

    Store::const_iterator& operator++()
    {
        store->increment(*this);
        return *this;
    }

    const Bin& operator*()
    {
        return store->dereference(*this);
    }
    
    const Store* store;
    std::variant<VectorStore::const_iterator_state, ListStore::const_iterator_state> state;
};

Store::const_iterator VectorStore::begin() const {
    return {this, vector.begin()};
}

Store::const_iterator VectorStore::end() const {
    return {this, vector.end()};
}

void VectorStore::increment(const_iterator& it) const
{
    ++std::get<VectorStore::const_iterator_state>(it.state);
}

const Bin& VectorStore::dereference(const_iterator& it) const
{
    return *std::get<VectorStore::const_iterator_state>(it.state);
}

Store::const_iterator ListStore::begin() const {
    return {this, list.begin()};
}

Store::const_iterator ListStore::end() const {
    return {this, list.end()};
}

void ListStore::increment(const_iterator& it) const
{
    ++std::get<ListStore::const_iterator_state>(it.state);
}

const Bin& ListStore::dereference(const_iterator& it) const
{
    return *std::get<ListStore::const_iterator_state>(it.state);
}

int main()
{
    VectorStore vector;
    for (auto& bin : vector)
    {
        std::cout << bin.value << "\n";
    }

    ListStore list;
    for (auto& bin : list)
    {
        std::cout << bin.value << "\n";
    }
}

The iterator state is stored in a std::variant, this requires that you know all of your derived classes in advance. If you want to use arbitrary derived classes you could store the state in std::any instead, the implementation would largely be the same:

#include <cstdint>
#include <vector>
#include <list>
#include <any>
#include <iostream>

struct Bin
{
    int value;
};

class Store {
public:
  virtual ~Store() = default;

  // Iterators
  class const_iterator;
  virtual const_iterator begin() const = 0;
  virtual const_iterator end() const = 0;

protected:
  virtual void increment(std::any&) const = 0;
  virtual const Bin& dereference(const std::any&) const = 0;
  virtual bool equal(const std::any&, const std::any&) const = 0;

};

class Store::const_iterator
{
public:
    bool operator == (const Store::const_iterator& other)
    {
        return store == other.store && store->equal(state, other.state);
    }

    bool operator != (const Store::const_iterator& other)
    {
        return !(*this == other);
    }

    Store::const_iterator& operator++()
    {
        store->increment(state);
        return *this;
    }

    const Bin& operator*()
    {
        return store->dereference(state);
    }
    
    const Store* store;
    std::any state;
};

class VectorStore : public Store {
public:
  VectorStore()
  :vector{{1},{2},{3},{4}}
  {
  }

  const_iterator begin() const override;
  const_iterator end() const override;

  using const_iterator_state = std::vector<Bin>::const_iterator;

protected:
  void increment(std::any&) const override;
  const Bin& dereference(const std::any&) const override;
  bool equal(const std::any&, const std::any&) const override;

private:
  std::vector<Bin> vector;
};

Store::const_iterator VectorStore::begin() const {
    return {this, vector.begin()};
}

Store::const_iterator VectorStore::end() const {
    return {this, vector.end()};
}

void VectorStore::increment(std::any& state) const
{
    state = ++std::any_cast<VectorStore::const_iterator_state>(state);
}

const Bin& VectorStore::dereference(const std::any& state) const
{
    return *std::any_cast<VectorStore::const_iterator_state>(state);
}

bool VectorStore::equal(const std::any& lhs, const std::any& rhs) const
{
    return std::any_cast<VectorStore::const_iterator_state>(lhs) == std::any_cast<VectorStore::const_iterator_state>(rhs);
}

class ListStore : public Store {
public:
  ListStore()
  :list{{2},{4},{6},{8}}
  {
  }

  const_iterator begin() const override;
  const_iterator end() const override;

  using const_iterator_state = std::list<Bin>::const_iterator;

protected:
  void increment(std::any&) const override;
  const Bin& dereference(const std::any&) const override;
  bool equal(const std::any&, const std::any&) const override;

private:
  std::list<Bin> list;
};

Store::const_iterator ListStore::begin() const {
    return {this, list.begin()};
}

Store::const_iterator ListStore::end() const {
    return {this, list.end()};
}

void ListStore::increment(std::any& state) const
{
    state = ++std::any_cast<ListStore::const_iterator_state>(state);
}

const Bin& ListStore::dereference(const std::any& state) const
{
    return *std::any_cast<ListStore::const_iterator_state>(state);
}

bool ListStore::equal(const std::any& lhs, const std::any& rhs) const
{
    return std::any_cast<ListStore::const_iterator_state>(lhs) == std::any_cast<ListStore::const_iterator_state>(rhs);
}

int main()
{
    VectorStore vector;
    for (auto& bin : vector)
    {
        std::cout << bin.value << "\n";
    }

    ListStore list;
    for (auto& bin : list)
    {
        std::cout << bin.value << "\n";
    }
}

I've only implemented the minimum for a for loop, you'll probably also want to implement the other iterator operators. Note that you'll probably only want to implement the common subset of operators supported by all of your container's iterators, e.g. in my sample code you wouldn't want to enable random access iterators as they aren't implementable for std::list.

What is the intended virtue of using std::any over just having the iterators be std::function-like value types that have a virtual implementation?
I think you'd struggle to create an iterator with all the right semantics that way, feel free to post another answer if you manage to work it out

Collectives™ on Stack Overflow

C++ Polymorphic Iterators in Abstract Base Class with Custom Child Implementations

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related