0

Здравствуйте. Относительно недавно мне помогли разобраться с итераторами, точнее понять их реализацию и т.п. (за что спасибо тем, кто помогал). Вот создам ещё один вопрос (ибо тот именно свою задачу исчерпал).

Дело вот в чем... Прописал я эти итераторы, вроде бы понял как что к чему более менее.. Получился следующий класс:

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);
        }
...
}

Всё вроде отлично... Но теперь я попытался переделать алгоритмы сортировки под эти итераторы. Ну.. Возьмем к примеру самый простой InsertionSort: Без итераторов было так:

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;  
       }
 }

После того, как я приделал итераторы получилось так:

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;
       }
 }

Концепцию правильно понял, или не очень? Можно ли как-то это оптимизировать?

И ещё... Я хотел для сравнения элемента и сменой их мест, чтобы было что-то типо такого

*it1 = *it2;

Такая запись не получалась, поэтому я через час попыток остановился на такой перегрузке:

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

Быть может есть более оптимальный вариант? И можно ли перегрузить так, как хотел я? (*it1 = *it2);

И как быть алгоритмам сортировки таким, как шейкерная или быстрая... Та же вообще границы ... И нужно брать по индексу.. Как итераторы в таком случае использовать? - Может быть с помощью перегруженных [] или есть оптимальнее?

3 ответа 3

2

Чтобы понять, что и как "правильно" с итераторами, проще всего проводить аналогию с указателями. Указатель можно разыменовать? Можно.

int* p;
*p = 4; // присваивание ОК
int x = *p; // чтение ОК

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

То есть, объект итератора по поведению должен быть вообще неотличим от обычного указателя.

И значит вам надо два оператора доступа к значению:

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

И тогда конструкция вида

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

будет работать, потому что итераторы не константные.

Вот так тоже будет работать:

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

А вот так уже не будет:

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

И если вы замените в данном случае итераторы на обычные указатели, ничего не поменяется.

Что касается, как использовать итераторы в реализации алгоритмов: представьте, что вместо итераторов у вас указатели и напишите алгоритм с их помощью. Потом поменяйте все на итераторы и, если итераторы сконструированы правильно, все должно продолжать работать.

1

*it1 = *it2;

Не получится. Потому что слева, за оператором присваивания должно стоять lvalue. Т.е. нечто, что обладает адресом в памяти. А *p есть значение, а не объект. Поэтому так не получится. С другой стороны, никто не мешает написать функцию swap(it1, it2). И пользоваться ей. Не нужно зацикливаться на перегрузке операторов. И я бы попробовал перегрузить оператор = для самих итераторов. Тогда будет порядок.

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

Теперь мы можем написать

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

Другой вопрос, что при этом другой функционал поломается.

4
  • @Другой вопрос, что при этом другой функционал поломается.@ Согласен... Просто запись it1 = it2 мне тоже нужно использовать, она присваивает указатели... А я просто думал, что быть может можно какую-то операцию поменять\перегрузить, чтобы было именно *it1 = *it2... "Не получится. Потому что слева, за оператором присваивания должно стоять lvalue. Т.е. нечто, что обладает адресом в памяти. А *p есть значение, а не объект." Всмысле? Немножечко не понял... Мы ведь можем сделать такую запись: int* value; *value = 5;
    – Daniel
    19 мая 2011 в 10:44
  • 1
    М-м-м. Да, верно, *value = 5 в случае если value - указатель можно написать. Просто как я понимаю проблема в том, что у Вас написано <pre>int operator*() const</pre> Т.е. у Вас получается так: <pre>int f(Iterator &); f(it1) = f(it2);</pre>
    – gecube
    19 мая 2011 в 14:20
  • О! Кажется нашел способ. Нужно замутить что-то в духе: <pre>typedef int* PINT; PINT& func (PINT& p) {return p;} // теперь мы можем сделать так: int *a, *b; func(a)=func(b); // присвоить a значение b</pre>
    – gecube
    19 мая 2011 в 23:12
  • Эх... Ну это не совсем то, однако спасибо за совет) А ещё.. Насчёт оптимизации... Оптимально ли у меня это реализовано? В сортировках типа шейкерной, мне указатели, которые меняются присваивать нужно будет что-то вроде Iterator left = Array::begin(); right += l-1; что-то вроде того?
    – Daniel
    20 мая 2011 в 18:21
1

Если в дополнение к этому методу:

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

добавить неконстантный:

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

то разыменованному итератору вполне можно будет присваивать новое значение.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.