Using iterators to modify array elements in c++

Question

The problem arise when I am trying to write an insert function that is suppose to move all elements in the array up at the specified location given by the iterator and then insert a new value into the array at the position given by the iterator.

The code is getting errors in the insert function with the following error:

no match for 'operator[]' (operand types are 'std::basic_string [1000]' and 'std::basic_string')

I am new to using iterators, and I think that it is not possible to access array elements with pointers as indices. So I am not sure if there is another way to do this, or do I need to overload the [] operator to make it work some how?

template <class T>
class Vector {
    public:
        typedef T* iterator;
        Vector () {  }

        T& operator[](unsigned int i) {
           return items[i];
        }
          // T& operator[](iterator i) {
           //return items[*i];
        //}

        iterator begin () {
            return &items[0];
        }
        iterator end () { 
            return &items[used];
        }
        int size () { return used; }

        iterator insert (iterator position, const T& item) { 

            for(Vector<T>::iterator i=&items[998]; i>=position; i--)
            {
                items[*(i+1)]=items[*i];
            }
            items[*position]= item;

            return position;
        }
    private:
        T items[1000];
        int used=0;
};

T items[1000]; is an C-Array not a Vector<T> so Vector<T>::iterator i=&items[998]; is ill formed. — Richard Critten
– Richard Critten, Commented Sep 13, 2018 at 8:51
The previous comment in mind, in insert(): i is of type T*. *i as well as *(i + 1) has type T& (a reference to a T). So, the items[*(i + 1)] does not make sense. (If I got it right *(i + 1) = *i; would instead.) — Scheff's Cat
– Scheff's Cat, Commented Sep 13, 2018 at 8:56
@RichardCritten Sorry, it's Vector not std::vector. I believe, OP tries to rebuild it for educational purpose. — Scheff's Cat
– Scheff's Cat, Commented Sep 13, 2018 at 9:01
@Scheff you are right - I need to read slower and more accurately. — Richard Critten
– Richard Critten, Commented Sep 13, 2018 at 9:02
An iterator is not an index, and cannot be used as an index. An iterator is used as if it was a pointer. In your case it is a pointer. Use it as a pointer: *position = item;. — n. m. could be an AI
– n. m. could be an AI, Commented Sep 13, 2018 at 9:10

Michael Veksler · Accepted Answer · 2018-09-13 09:15:53Z

This code is problematic in the sense that it creates 1000 elements of type T, even if logically it is empty. Also, if there are more than 1000 insertions, then the upper elements are discarded.

As for the compilation issues, I have tries to compile the code with Vector<int> and it compiles fine, but crashes. For the same reason it crashes with Vector<int> it does not compile with Vector<std::string>. The Issue is with the type of *i, which is , i.e., std::string in the case of Vector<std::string>. Either use iterator all the way, or use indexes, but don't mix. Using iterators:

        for(Vector<T>::iterator i=&items[998]; i>=position; i--)
        {
            *(i+1)=*i;
        }

Edit :

[Just noticed an answer by Scheff that figured this out, after completing this edit]

The above invokes undefined behavior for v.insert(v.begin(), value) since i iterates before items. To avoid that, the iteration should stop before it falls off items:

        for(Vector<T>::iterator i=&items[999]; i > position; i--)
        {
            *i = *(i-1);
        }

Also, note that the line following the loop should also be fixed:

        items[*position]= item; // <--- BUG: also mixing indexes and iterators

Or using indexes:

        for(int i= 998; begin() + i>=position; i--)
        {
            items[i+1]=items[i];
        }

Scheff's Cat · Accepted Answer · 2018-09-13 09:20:01Z

In addition to the answer of Michael Veksler, I tried to get it working (and hence needed a bit longer).

So, with his first proposed fix and additionally

items[*position]= item;

changed to

*position = item;

the following test compiles and runs:

#include <iostream>

int main()
{
  Vector<double> vec;
  vec.insert(vec.begin(), 1.0);
  vec.insert(vec.begin(), 2.0);
  vec.insert(vec.begin(), 3.0);
  std::cout << "vec.size(): " << vec.size() << '\n';
  for (int i = 0; i < vec.size(); ++i) {
    std::cout << "vec[" << i << "]: " << vec[i] << '\n';
  }
  return 0;
}

Output:

vec.size(): 0

Oops!

The update of used is missing in insert() as well:

++used;

And, now it looks better:

vec.size(): 3
vec[0]: 3
vec[1]: 2
vec[2]: 1

The complete MCVE:

#include <iostream>

template <class T>
class Vector {
    public:
        typedef T* iterator;
        Vector () {  }

        T& operator[](unsigned int i) {
           return items[i];
        }
          // T& operator[](iterator i) {
           //return items[*i];
        //}

        iterator begin () {
            return &items[0];
        }
        iterator end () { 
            return &items[used];
        }
        int size () { return used; }

        iterator insert (iterator position, const T& item) { 

            for(Vector<T>::iterator i=&items[998]; i>=position; i--)
            {
                *(i+1) = *i;
            }
            *position = item;
            ++used;
            return position;
        }
    private:
        T items[1000];
        int used=0;
};

int main()
{
  Vector<double> vec;
  vec.insert(vec.begin(), 1.0);
  vec.insert(vec.begin(), 2.0);
  vec.insert(vec.begin(), 3.0);
  std::cout << "vec.size(): " << vec.size() << '\n';
  for (int i = 0; i < vec.size(); ++i) {
    std::cout << "vec[" << i << "]: " << vec[i] << '\n';
  }
  return 0;
}

Live Demo on coliru

Brandon4bz · Accepted Answer · 2018-09-13 09:12:26Z

So you can think of an iterator in this context as essentially a glorified pointer to the elements in the array, as you defined in your typedef at the beginning of your class.

When you're trying to access the elements in your array in your insert function, you are essentially dereferencing these pointers to yield the elements themselves and THEN using those elements as indices for your array, hence producing the error that the index is of the wrong type.

So for example suppose you had a Vector<std::string>. Inside the for loop in the insert function, you have this line:

items[*(i+1)]=items[*i];

Because i is an iterator as you defined, i has the type std::string * and hence *i has the type std::string. When you then write items[*i] you are trying to use the std::string as an index for your array which you can't do.

Instead, you should use a line similar to the following:

*(i + 1) = *i

There are also a couple of logical errors in your code, but I'll leave you to find those later on.

Hope this helps!

Caleth · Accepted Answer · 2018-09-13 09:12:52Z

0

Have a look at how std::move_backward can be implemented

template< class BidirIt1, class BidirIt2 >
BidirIt2 move_backward(BidirIt1 first, BidirIt1 last, BidirIt2 d_last)
{
    while (first != last) {
        *(--d_last) = std::move(*(--last));
    }
    return d_last;
}

You don't need to move any of the elements past end, and we can rewrite your insert to be similar

iterator insert (iterator position, const T& item) { 
    for(iterator i = end(), d = end() + 1; i != position; )
    {
        *(--d) = std::move(*(--i));
    }

    *position = item;
    ++used;

    return position;
}

Note that this is undefined if you try to insert into a full Vector

answered Sep 13, 2018 at 9:12

Caleth

66.1k2 gold badges53 silver badges101 bronze badges

Collectives™ on Stack Overflow

Using iterators to modify array elements in c++

4 Answers 4

Edit :

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Edit :

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related