CODEWITHSUNDEEP
c++templatesvectoriteratorconst-correctness
FredFrugal
FredFrugal

Reputation: 75

How do I implement a Vector with const correctness that forbids a normal iterator of such Vector to change the value at the address of the iterator

Background:

I am writing my own vector.h for fun (please don't judge). I am trying to remain const correct so I have implemented both a const .begin() function and non const .begin() functions for my Vector::iterator class. My CMakeLists.txt file is requiring C++23

The Issue:

In my UnitTest I am unfortunately able to declare a const vector then declare a non const iterator and successfully change the value of the const Vector using the iterator. This is obviously not the point of a const Vector.

Please If you have time look through my implementation to see what I am overlooking. Full code found on my github here. Snippets below:

My code:

Test that has unwanted behavior

TEST(testConstBegin) {
    const Vector<int> c_myVec = {0,1,2,4};
    Vector<int>::iterator it = c_myVec.begin(); // NOTE not const.
    
    // c_myVec[0] = 4;            // fails as expected
    *it = 4;                      // should fail but does not. THIS IS WHY I WROTE THIS QUESTION.
    CHECK_EQUAL(c_myVec[0], 0);   // This line should never run.
}

iterator assigment ctor

   template <typename T>
    typename Vector<T>::iterator::iterator_reference
    Vector<T>::iterator::operator=(
           typename Vector<T>::iterator::const_iterator_reference other) {
        if (this != &other) 
            iter_ = other.iter_;
        
        return *this;
    }

const .begin()

 template <typename T>
    typename Vector<T>::const_iterator 
    Vector<T>::cBegin() const {
        return typename Vector<T>::iterator::const_iterator(array_);
    }
    
    // issue #001
    template <typename T>
    typename Vector<T>::const_iterator 
    Vector<T>::begin() const {
        return typename Vector<T>::iterator::const_iterator(array_);
    }

.begin()

   template <typename T>
    typename Vector<T>::iterator
    Vector<T>::begin() {
        return iterator(array_);
    }

const operator*()

   // const operator*
    template <typename T>
    typename Vector<T>::iterator::const_reference
    Vector<T>::iterator::operator*() const {
        return *iter_;
    }

non const operator*()

   // operator*
    template <typename T>
    typename Vector<T>::iterator::reference
    Vector<T>::iterator::operator*() {
        return *iter_;
    }

stl_vector.h implementation


      /**
       *  Returns a read-only (constant) iterator that points to the
       *  first element in the %vector.  Iteration is done in ordinary
       *  element order.
       */
      const_iterator
      begin() const _GLIBCXX_NOEXCEPT
      { return const_iterator(this->_M_impl._M_start); }

stl_vector.h behavior I am trying to create

testVectorFillCtor.cpp:32:50: error: conversion from ‘__normal_iterator<const int*,[...]>’ to non-scalar type ‘__normal_iterator<int*,[...]>’ requested
   32 |     std::vector<int>::iterator it = c_myVec.begin();
      |                                     ~~~~~~~~~~~~~^~

Upvotes: 2

Views: 167

Answers (1)

alfC
alfC

Reputation: 16320

Implementing a container is not easy, but if you do, I absolutely respect that your goal is to be const correct. In fact, don't do this kind of thing if you are not going to do it 100% "const-correct".

The original defect I see in your code is this one here,

https://github.com/PIesPnuema/stl_implementation_practice/blob/main/include/vector.h#L38

        typedef const iterator           const_iterator;

const_iterator needs to be implemented as a different class than iterator, so it can return const references when dereferenced.

In any case, a const_iterator has nothing to do with the iterator being const. Think about it, can a const_itertor be mutated (e.g., by increment)? Probably yes, so it is definitely not the same as iterator const. This is the same difference as between double const* and double* const. (This is the kind of confusion one doesn't have by using EastConst).

In other words, const_iterator and iterator are basically independent types. For the case of a vector, they can be defined simply as double const* and double* respectively; but that will hide the general complexity of implementing iterators. So, I will assume that we want iterators to be classes.

I have implemented vector-like containers; unfortunately, there is no other way.

You can save some code duplication by having a single common basic_iterator<Ref> base parameterized in T& and T const&, but that is a different story.

This is the smallest code I came up with to illustrate this point:

#include<cassert>

class Vec {
    double value_ = 5;

public:
    struct iterator {
        double* ptr_;
        auto operator*() const -> double& {return *ptr_;}
    };

    struct const_iterator {
        double const* ptr_;
        // ... perhaps allow implicit conversion from iterator to const_iterator and other shenanigans here
        auto operator*() const -> double const& {return *ptr_;}
    };

    auto begin()       ->       iterator {return {&value_};}
    auto begin() const -> const_iterator {return {&value_};}
};

int main() {
    Vec const v;

    assert( *v.begin() == 5 );
//    *v.begin() = 6;  // double const& is not assignable, compilation error
}

https://godbolt.org/z/vGT8j3WrG

For a complete example, look at my container array library, follow the white rabbit from this line, https://gitlab.com/correaa/boost-multi/-/blob/master/include/multi/array_ref.hpp#L1267

To avoid some code duplication, you can use some template tricks:

class Vec {
    double value_ = 5;

    template<template<typename> class Modifier>
    struct iterator_base {
        Modifier<double>::type* ptr_;
        auto operator*() const -> auto& {return *ptr_;}
    };

public:
    using       iterator = iterator_base<std::type_identity>;
    using const_iterator = iterator_base<std::add_const    >;

    auto begin()       ->       iterator {return {&value_};}
    auto begin() const -> const_iterator {return {&value_};}
};

https://godbolt.org/z/81GK69G7W

If you want to completely eliminate code duplication and automatically convert from iterator to cons_iterator, you can do this, although it is unclear if it is a real gain.

class Vec {
    std::unique_ptr<double> base_ = std::make_unique<double>(5.0);

    template<template<typename> class ConstQ>
    class iterator_base {
        ConstQ<double>::type* ptr_;
        friend class iterator_base<std::add_const>;

    public:
        explicit iterator_base(ConstQ<double>::type* ptr) : ptr_{ptr} {}
        iterator_base(iterator_base<std::type_identity> const& other) : ptr_{other.ptr_} {}
        auto operator*() const -> auto& {return *ptr_;}
    };

public:
    using       iterator = iterator_base<std::type_identity>;
    using const_iterator = iterator_base<std::add_const    >;

private:
    auto begin_aux() const {return iterator(base_.get());}

public:
    auto begin()       ->       iterator {return begin_aux();}
    auto begin() const -> const_iterator {return begin_aux();}
};

https://godbolt.org/z/PEqqdTefe

One can eliminate the spurious base class and the strange constructor by using the questionable technique of inheritance-for-extension; one has to be careful later when implementing mutation members on the iterators classes. Note the constness doesn't escape from the design if one is careful in the implementation:

    class const_iterator {
        const_iterator(double* ptr) : ptr_{ptr} {}
        double* ptr_;
        friend class Vec;

    public:
        auto operator*() const -> double const& {return *ptr_;}
    };
    struct iterator : const_iterator {
        auto operator*() const -> double      & {return *ptr_;}
    };

https://godbolt.org/z/Ye1fj5faE

Upvotes: 10

Related Questions