Custom implementation to provide an immutable range of a vector without copying it

Question

Edit: A new and improved version can be found in this question, based on the feedback!

---

I needed to pass a const reference to part of a std::vector without copy.

Some research, particularly this SO question, suggested that it is not something supported by default, so I created my own code for it:

#include <iterator>
#include <vector>

template <typename T>
class ConstVectorSubrange{
public:
  ConstVectorSubrange(typename std::vector<T>::const_iterator start_, uint32 size_)
  : start(start_)
  , range_size(size_)
  { }

  ConstVectorSubrange(std::initializer_list<typename std::vector<T>::const_iterator> list)
  : start(*list.begin())
  , range_size(std::distance(*list.begin(), *(list.end()-1)))
  { }

  const T& operator[](std::size_t index) const{
    assert(index < range_size);
    return *(start + index);
  }
  const T& back(void) const{
    return *(cend()-1);
  }
  std::size_t size(void) const{
    return range_size;
  }
  const typename std::vector<T>::const_iterator cbegin(void) const{
    return start;
  }
  const typename std::vector<T>::const_iterator cend(void) const{
    return (start + range_size);
  }

private:
  const typename std::vector<T>::const_iterator start;
  const uint32 range_size;
};

An example of using this would be a member function where not the whole array is visible, although copies are to be avoided:

#include <vector>

class BigData{
  std::vector<int> big_array = vector<int>(10000);
public:

  ConstVectorSubrange get_last_five_thousand_elements(){
    return{(big_array.cend()-5000), big_array.cend()};
  }

};

How can this code be improved?

Especially considering the iterators might be invalidated after the creation of this object, is there a way to make it safer?

Answer 1

You are implementing std::span

What you are trying to implement is basically C++20's std::span. It might be worthwhile to look at how it is implemented, and copy its interface if possible, so if you ever want to change the codebase using your class to use std::span, it will be easy.

I'll also use std::span as a reference and point out differences between it and your class below.

Use std::size_t for sizes consistently

Use std::size_t instead of uint32 for range_size. It is the proper type to store sizes. Another possible alternative is to use std::vector<T>::size_type, so you match exactly what std::vector uses to store sizes.

Don't use an initializer list for begin/end pairs

The constructor that takes an initializer list does not make sense. If you want a constructor that takes a begin and end iterator pair, just make that explicit:

ConstVectorSubrange(typename std::vector<T>::const_iterator start, typename std::vector<T>::const_iterator end)
  : start(start)
  , range_size(end - start)
{ }

With an initializer list, you can pass any number of iterators to the constructor, including an empty initializer list.

Add begin() and end() member functions

You only implemented cbegin() and cend(), but this is not enough to make range-for work. Add begin() and end() member functions. Note that these should also be const functions of course.

You can even consider removing cbegin() and cend(); they don't offer any advantage over begin() and end() for your class. Note that std::span also doesn't implement cbegin() and cend().

Be consistent manipulating iterators

You used std::distance() to calculate the distance between the start and end iterator passed to the second constructor, but then used arithmetic operators to advance the iterators to a given index or to the end. I would either use arithmetic operators everywhere, or use std::distance and std::next everywhere to manipulate the iterators. The latter is preferred if you want to make your class more generic and have it work for other container types as well.

Missing member functions

Intertestingly there is a back() function, but no front()? Also consider implementing all the member functions of std::vector where possible, like at(), data(), empty() and rbegin()/rend(). This ensures your subrange can be used as a drop-in replacement for a std::vector as much as possible.

It might also be interesting to add the extra member functions std::span adds, like first(), last() and subspan().

Making T deducible

A big problem with your class is that the compiler isn't able to deduce T from the arguments passed to the constructors, due to the dependent type names being used. There are some ways to fix this. One is to provide deduction guides, but this requires C++17. Another way is not to make your class templated on the value type T, but rather on the iterator type. This will also greatly simplify your code, and at the same time make it work for other containers besides std::vector:

template<typename Iterator>
class ConstSubrange {
public:
    using T = std::remove_reference_t<std::iter_reference_t<Iterator>>;

    ConstSubrange(Iterator start, std::size_t size)
    : start(start), range_size(size) {}

    ConstSubrange(Iterator start, Iterator end)
    : start(start), size(std::distance(start, end)) {}

    const T& operator[](std::size_t index) const {
        return *std::next(start, index);
    }

    const Iterator begin(void) const {
        return start;
    }

    ...
private:
    const Iterator start;
    const std::size_t range_size;
};

Safety

Especially considering the iterators might be invalidated after the creation of this object, is there a way to make it safer?

Unfortunately, it's not possible to make a class like yours that provides a "view" on another container and have it protect you against invalidation; C++ just doesn't keep track of dependent lifetimes. Note that even a regular iterator doesn't provide this safety. Either you live with it, or make expensive copies of subranges, or use a programming language that uses garbage collection or has a borrow checker.

In a way your class is also too strict; it's perfectly fine to have it store regular iterators instead of const_iterators; this will allow you to modify a subrange of a vector.

Answer 2

You are asking how you can guard against invalid iterators; I assume you are most concerned about iterators that have become invalid after the vector had to re-allocate when it outgrew its capacity.

One solution is to store an index instead of an iterator; as long as the vector doesn't shrink the range will be valid, and its validity can be trivially checked by comparing to the vector's size.

This is only doable as long as your range class targets exclusively "indexable" containers like vectors (and not maps etc.). Downside: Because you only have an index you'll then also need an additional constructor parameter, a reference of the vector.