Hello. Relatively recently, they helped me to deal with iterators, more precisely to understand their implementation, etc. (thanks to those who helped). Here we will create one more question (for he has exhausted his task).

The point is this ... I prescribed these iterators, it would seem, I understood how that what is more or less .. The result was the following class:

class Array { private: int n; int* arr; public: class Iterator { public: int *p; Iterator() { p = nullptr; } Iterator(int *pv) { p = pv; } int operator*() const { return *p; } /*Iterator operator++(int) { int* temp = p; return ++temp; }*/ Iterator& operator++() { ++p; return *this; } Iterator operator++(int) { return Iterator(p++); } Iterator& operator--() { --p; return *this; } Iterator operator--(int) { return Iterator(p--); } const int& operator[](const std::size_t&pv) { return p[pv]; } Iterator& operator+=(const std::size_t&pv) { p += pv; return *this; } int* base() const { return p; } Iterator operator=(const int a) { *p = a; return *this; } }; Iterator begin() { return Iterator(arr); } Iterator end() { return arr+n; } friend inline bool operator==(const Iterator&it1, const Iterator&it2) { return it1.base() == it2.base(); } friend inline bool operator!=(const Iterator&it1, const Iterator&it2) { return it1.base() != it2.base(); } friend inline bool operator <(const Iterator&it1, const Iterator&it2) { return it1.base() < it2.base(); } friend inline bool operator >(const Iterator&it1, const Iterator&it2) { return it1.base() > it2.base(); } friend inline bool operator <=(const Iterator&it1, const Iterator&it2) { return it1.base() <= it2.base(); } friend inline bool operator >=(const Iterator&it1, const Iterator&it2) { return it1.base() >= it2.base(); } friend Iterator operator+(const Iterator&it, std::size_t n) { return Array::Iterator(it.base() + n); } friend Iterator operator-(const Iterator&it, std::size_t n) { return Array::Iterator(it.base() - n); } ... }

Everything seems fine ... But now I tried to remake the sorting algorithms for these iterators. Well .. Take for example the simplest InsertionSort: Without iterators it was like this:

 void Array::InsertionSort() { int i, j, key; for (i = 1; i < length; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

After I added iterators, it turned out like this:

 void Array::InsertionSort() { int key; Iterator start = Array::begin(); Iterator end = Array::end(); Iterator temp; for (++start; start != end; start++) { key = *start; temp = start - 1; while (temp >= Array::begin() && *temp > key) { (temp+1) = *temp; --temp; } compares++; (temp+1) = key; } }

Did you understand the concept correctly or not? Is there any way to optimize this?

And yet ... I wanted to compare the element and change their places, so that there was something like this

 *it1 = *it2;

Such a record did not work, so after an hour of attempts I stopped at this overload:

 Iterator operator=(const int a) { *p = a; return *this; }

Perhaps there is a better option? And is it possible to overload as I wanted? ( *it1 = *it2 );

And what about sorting algorithms such as shaker or fast ... Same general bounds ... And you need to take by index .. How do iterators use in this case? - Maybe using overloaded [] or is it more optimal?

    3 answers 3

    To understand what and how to "correctly" with iterators, it is easiest to draw an analogy with pointers. Pointer can be dereferenced? Can.

     int* p; *p = 4; // присваивание ОК int x = *p; // чтение ОК const int* p; *p = 4; // присваивание НЕЛЬЗЯ int x = *p; // чтение ОК

    That is, the behavior iterator object should be generally indistinguishable from a regular pointer.

    And that means you need two operators to access the value:

     // этот оператор будет разрешать только чтение для константных итераторов // и, в случае, int как вы и сделали его можно заменить на // int operator*() const // без потери качества const int& operator*() const { return *p; } // этот оператор будет разрешать и чтение и запись для неконстантных итераторов int& operator*() { return *p; }

    And then the construction of the form

     Iterator it1; Iterator it2; *it1 = *it2;

    will work because iterators are not constant.

    This will also work like this:

     Iterator it1; const Iterator it2; *it1 = *it2;

    But this will not happen:

     const Iterator it1; const Iterator it2; *it1 = *it2;

    And if you replace iterators with regular pointers in this case, nothing will change.

    As for how to use iterators in the implementation of algorithms: imagine that instead of iterators you have pointers and write an algorithm with their help. Then change everything to iterators and, if the iterators are designed correctly, everything should continue to work.

      * it1 = * it2;

      Will not work. Because on the left, the assignment operator must be lvalue. Those. something that has an address in memory. A * p is a value, not an object. Therefore, this will not work. On the other hand, no one bothers to write the function swap (it1, it2). And enjoy it. No need to dwell on operator overloading. And I would try to overload the operator = for the iterators themselves. Then there will be order.

       // как-то так, но я не уверен на 100%. Iterator & operator =(Iterator /*const*/ & S) // const нас не устраивает { int *tmp = p; if (&S != this) { p = Sp; Sp = tmp; } return *this; }

      Now we can write

       it1 = it2; // поменять местами.

      Another question is that in this case another functional will break.

      • @ Another question is that at the same time another functionality will be broken. @ I agree ... I just need to use it1 = it2 record, it assigns pointers ... And I just thought that maybe some operation can be changed / reloaded to it was precisely * it1 = * it2 ... "It does not work. Because on the left, an assignment operator must have an lvalue. Ie something that has an address in memory. And * p is a value, not an object." In the sense of? I did not understand a little bit ... We can make such a record: int * value; * value = 5; - Programmer
      • one
        Mmmm Yes, right, * value = 5 in the case of the value - pointer can be written. Just as I understand the problem is that you have written <pre> int operator * () const </ pre> Ie you do it like this: <pre> int f (Iterator &); f (it1) = f (it2); </ pre> - gecube
      • ABOUT! Seems to found a way. We need to stir up something like this: <pre> typedef int * PINT; PINT & func (PINT & p) {return p;} // now we can do this: int * a, * b; func (a) = func (b); // assign a value to b </ pre> - gecube
      • Eh ... Well, this is not quite that, but thanks for the advice) And yet .. As for optimization ... Is it optimally implemented by me? In shaker-type sorts, pointers that change assignments will need something like Iterator left = Array :: begin (); right + = l-1; something like that? - Programmer

      If in addition to this method:

       int operator*() const { return *p; }

      add non-constant:

       int& operator*() { return *p; }

      then it will be possible to assign the new value to the dereferenced iterator.