4
\$\begingroup\$

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?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Some C++ programmers will find the void arguments offensive. \$\endgroup\$ Nov 22 '21 at 5:24
  • \$\begingroup\$ Yes, you are right, and I think I'll remove them in the next version! Do you know why that is by the way? \$\endgroup\$ Nov 22 '21 at 6:12
  • \$\begingroup\$ They are not needed in C++. If they appeared in a header file that may be read by a C compiler, I think it would be fine. But they appear in the middle of templated code. No C compiler is going to read that. \$\endgroup\$ Nov 22 '21 at 6:18
6
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ Initializer list is there or a kind of syntactic sugar, aiming to cover {vec.begin(),vec.end()}; Is there anything else I can do it with that? I get that it doesn't make any sense, maybe I am missing something. \$\endgroup\$ Nov 21 '21 at 17:20
  • \$\begingroup\$ should I implement .begin() and .end() despite the class is supposed to have read-only access to the vector span it was constructed with? IN my case the strictness is for a reason, but for general usage, I'd understand that implementing begin() and end() would be better.. \$\endgroup\$ Nov 21 '21 at 17:22
  • 1
    \$\begingroup\$ instead of std::advance, I think std::next is appropriate, in case you were referring to the back() function. I checked this question on SO. \$\endgroup\$ Nov 21 '21 at 19:04
  • 2
    \$\begingroup\$ My suggestion to just use two iterator parameters also allows you to use {vec.begin(), vec.end()}. You should always implement begin() and end(), and make those functions const to ensure they also work with a const span, and having them return const iterators is also perfectly fine. The problem with deduction is that vector<T>::const_iterator is not a type but a type alias; the actual type of the iterator you pass in is something different (for libstdc++, it's a __gnu_cxx::__normal_iterator<T*, std::vector<T, std::allocator<T>>>). \$\endgroup\$
    – G. Sliepen
    Nov 21 '21 at 22:30
  • 1
    \$\begingroup\$ Template argument deduction is not bothered by aliases; it will deduce what you call a std::string just fine even though it's really a std::basic_string< ... >. The issue with not being able to deduce is because of a dependent type and it doesn't know the relationship between the Iterator type and T which is used as a template argument for the container and iterator. That's what deduction guides will tell it; e.g. "look at the Iterator's element type in this case". \$\endgroup\$
    – JDługosz
    Nov 24 '21 at 17:52
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.