problem with iterators

[NickName]

Hi all again!
Now i have a question about the array that keeps indices sorted.
I've thought about 2 ways to do it:

1) following TheDestroyer suggestion, have it to be always sorted and sort it each time insert an element.

2) keep it unsorted and sort it only when i call the begin() function for sortIterator.

The 1st way seems the best one to me, but i don't know how to solve this problem:
how can i keep the array sorted whenever i change a value?
For example, after 4 insert(value) calls my data array is:

[42, 12, 24, 10]

and my indices array should be:

[3, 1, 2, 0]

What happens if i change the value in position 1 in the data array?

vec[1]=9;

or

iterator[1]=9;

Now my data array is [42, 9, 24, 10]

but the "sorted" indices array is still the same [3, 1, 2, 0]

What should i do to sort it again, after a change in the data array?

Thanks

[JLBorges]

> how can i keep the array sorted whenever i change a value?

Intercept every change to a value and re-order the indices accordingly.
For example, for modification of a value through the subscript operator on the vector:

template< typename T > struct my_vector
{
    // ...

    void value( std::size_t pos, const T& new_value ) // change value at pos
    {
        if( buffer[pos] != new_value ) 
        {
            buffer[pos] = new_value ;

            // TODO: rearrange position pos in sorted_indices
            
        }
    }

    const T& value( std::size_t pos ) const { return buffer[pos] ; }

    struct reference
    {
        operator const T& () const { return vec.value(pos) ; }
        reference& operator= ( const T& v ) { vec.value(pos,v) ; return *this ; }

        private:
           my_vector<T>& vec ;
           std::size_t pos ;
           reference( my_vector<T>& v, std::size_t p ) : vec(v), pos(p) {}
           friend class my_vector<T> ;
    };

    const T& operator[] ( std::size_t pos ) const { return buffer[pos] ; }

    reference operator[] ( std::size_t pos ) { return reference( *this, pos ) ; }

    // ...

    private:
       T* buffer ;
       std::size_t sz ;
       std::size_t cap ;

       std::size_t* sorted_indices ;
};

Likewise, return a my_vector<T>::reference instead of a reference everywhere - my_vector<T>::front(), my_vector<T>::iterator::operator*() etc.

The semantics of modifying a value through the 'sortIterator' is messy to say the least; perhaps make the 'sortIterator' an iterator that iterates over non-modifiable values.

[NickName]

Thank you very much! It seems to work!
The only thing i had to fix was a warning about returning a temporary at line 32.

I added a pointer to reference in my_vector class,

    struct reference
    {
        operator const T& () const { return vec.value(pos) ; }
        reference& operator= ( const T& v ) { vec.value(pos,v) ; return *this ; }

        private:
           my_vector<T>& vec ;
           std::size_t pos ;
           reference( my_vector<T>& v, std::size_t p ) : vec(v), pos(p) {}
           friend class my_vector<T> ;
    };

    const T& operator[] ( std::size_t pos ) const { return buffer[pos] ; }

    reference operator[] ( std::size_t pos ) { //i changed this
   
        delete ref; 
        ref = new reference( *this, pos ) ;    

        return ref; 
    }

    // ...

    private:
       T* buffer ;
       std::size_t sz ;
       std::size_t cap ;

       std::size_t* sorted_indices ;
      
       reference* ref; // I added this pointer


};

And compiler doesn't complain anymore about that.
Is it a right change?

Thanks again!

[JLBorges]

> Is it a right change?

No, it would be disastrous for a whole lot of reasons.
For instance, consider the implications of: a_vec[4] = a_vec[12] ;


> a warning about returning a temporary at line 32.

No self rspecting compiler would generate a warning for this:
reference operator[] ( std::size_t pos ) { return reference( *this, pos ) ; }

Did you write
reference& operator[] ( std::size_t pos ) { return reference( *this, pos ) ; }
by mistake?

[NickName]

Oh yes. And the compiler was also telling me that: returning a reference to temporary...
Need to pay more attention...
Thanks again, you're saving the project!

[NickName]

Hi, im back again. When i think i'm done, a new problem comes out!

Now i can't figure out how to return a my_vector<T>::reference from inside my_vector<T>::iterator.
Inside the iterator class i only have a pointer to data array of my_vector, so i dont know how to call reference( my_vector<T>& v, std::size_t p ) : vec(v), pos(p) {}
since i don't have the *this, representing my_vector, nor pos, as it was for
reference operator[] ( std::size_t pos ) { return reference( *this, pos ) ; }

Is there a way to do this?

[JLBorges]

> Now i can't figure out how to return a my_vector<T>::reference from inside my_vector<T>::iterator.

Have a reference to my_vector<T> in the iterator. For example:

template< typename T > struct my_vector
{
    // ...

    void value( std::size_t pos, const T& new_value ) ; // change value at pos 
    const T& value( std::size_t pos ) const { return buffer[pos] ; }

    struct reference
    {
        operator const T& () const { return vec.value(pos) ; }
        reference& operator= ( const T& v ) { vec.value(pos,v) ; return *this ; }

        private:
           my_vector<T>& vec ;
           std::size_t pos ;
           reference( my_vector<T>& v, std::size_t p ) : vec(v), pos(p) {}
           friend class my_vector<T> ;
           friend class my_vector<T>::iterator ; // *** added ***
    };

    struct iterator
    {
        // typedefs ...

        iterator( my_vector<T>& v, std::size_t p ) : vec(v), pos(p) {}

        my_vector<T>::reference operator*() 
       { return my_vector<T>::reference(vec,pos) ; }

        // ....

        my_vector<T>::reference operator[] ( std::ptrdiff_t n )
        { return my_vector<T>::reference( vec, pos+n ) ; }

        // etc ...

        private:
           my_vector<T>& vec ;
           std::size_t pos ;
    };

    iterator begin() { return iterator(*this,0) ; }
    iterator end() { return iterator(*this,sz) ; }
    
    // ...
};

[NickName]

Neverending story's here!
Thank you for the code, but i have some more questions now.
Is the default constructor always needed for the iterator class?
In this case i don't know how to inizialize my_vector<T>& vec;
For example, i used to create iterator like this:

my_vector<T>::iterator start, end;
start = vec.begin();
end = vec.end();

Now i have to write:

my_vector<T>::iterator start = vec.begin();
my_vector<T>::iterator end = vec.end(); 

Is this behaviour correct or do i always have to guarantee the support to
my_vector<T>::iterator start, end;

Thanks!

[JLBorges]

> Is the default constructor always needed for the iterator class?

No. To be compatible with the standard library, an iterator must be copy- constructible, copy-assignable, and destructible; in addition iterator l-values must be swappable. However, my understanding is that for this particular project, use of standard library components is not allowed, and therefore standard conformance is not an issue.

If you want to make the iterator default-constructible and swappable, use a pointer instead of a reference.

template< typename T > struct my_vector
{
    // ...

    struct iterator
    {
        iterator( my_vector<T>* v = nullptr, std::size_t p = 0 ) : vec(v), pos(p) {}

        reference operator*()
        { assert(vec) ; return my_vector<T>::reference( *vec, pos) ; }

        // ....

        reference operator[] ( std::ptrdiff_t n )
        { assert(vec) ; return my_vector<T>::reference( *vec, pos+n ) ; }

        // etc ...

        private:
           my_vector<T>* vec ;
           std::size_t pos ;
    };

    iterator begin() { return iterator(this,0) ; }
    iterator end() { return iterator(this,sz) ; }

    // ...

};

[NickName]

Thanks! That's what i made, except for the assert(vec) that i've added now!

[NickName]

Houston, we've had a problem...testing my_vector with a struct!

struct data{
   int a;
   char b;
}

my_vector<data> vec;
//putting some data in vec

int tmp = vec[3].a; //compiler error! 

error: 'struct my_vector<data>::reference' has no member named 'a'

same error with iterator::operator* and iterator::operator[]

Should i change my_vector::reference

    struct reference
    {
        operator const T& () const {     //** changed
            data = vec.value(pos); 
            return data ; 
         } 
        reference& operator= ( const T& v ) { vec.value(pos,v) ; return *this ; } // *** what to do here?

        private:
           my_vector<T>& vec ;
           std::size_t pos ;
           T& data;                      //*** added ***
           reference( my_vector<T>& v, std::size_t p, T& d ) : vec(v), pos(p) , data(d){} // ***changed
           friend class my_vector<T> ;
           friend class my_vector<T>::iterator ;

    };

Also, do i need to return my_vector::reference even from iterator::operator-> ?

Thanks

[sandodog]

mmh..

I don't think your solution is a good one..
Because you are now returning a T& instead of a const T& and this doesn't change nothing. You still don't have any member in my_vector::reference...

[JLBorges]

> int tmp = vec[3].a; //compiler error!

Ah! You've finally come face to face with it; we can have 'smart' pointers, but not 'smart' references - the structure-to-member . operator can't be overloaded.


> Should i change my_vector::reference

That change does not really improve anything - it makes it worse by masking the object identity.

This is a work around:

//int tmp = vec[3].a; //compiler error!
int tmp = static_cast<const T&>(vec[3]).a;

> do i need to return my_vector::reference even from iterator::operator-> ?

No, you need to return a const T*

[NickName]

Ok thanks again!
Returning const T* from iterator::operator-> will prevent from changing any member of the struct, right?

[JLBorges]

> Returning const T* from iterator::operator-> will prevent from changing any member of the struct, right?

Right. We wouldn't wan an item in a sorted sequence to be modified while we are in in the middle of iterating through the sequence.