Russian Qt Forum

Qt => Кладовая готовых решений => Тема начата: __Heaven__ от Ноябрь 03, 2015, 11:03



Название: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 03, 2015, 11:03
Привет, друзья!
В этой теме я представлю шаблон итератора, который пробегается по элементам контейнера из начала в конец.
Идея принадлежит Пантеру (http://www.prog.org.ru/index.php?action=profile;u=4067), с его же немалой помощью я её реализовал.
Ниже представлен код шаблона:
Код
C++ (Qt)
namespace Impl{
 
template<class ContainerIterator>
class Iterator
{
   using ValueType = typename std::iterator_traits<ContainerIterator>::value_type;
public:
   Iterator(const ContainerIterator& begin, const ContainerIterator& end)
       : begin_(begin),
         end_(end)
       {}
 
   bool atEnd() const{
       return begin_ == end_;
   }
 
   bool hasNext() const{
       return begin_ != end_;
   }
 
   ValueType& operator++(){
       return next();
   }
 
   ValueType operator++() const{
       return next();
   }
 
   ValueType& next(){
       return *(++begin_);
   }
 
   ValueType next() const{
       return *(++begin_);
   }
 
   ValueType& operator*(){
       return *begin_;
   }
 
   ValueType operator*() const{
       return *begin_;
   }
 
private:
   ContainerIterator begin_;
   ContainerIterator end_;
};
 
}
template<class Container>
class Iterator: public Impl::Iterator<typename Container::iterator>{
public:
   explicit Iterator(Container& container)
       : Impl::Iterator<typename Container::iterator>(container.begin(), container.end())
   {
 
   }
 
};
 
template<class Container>
class ConstIterator: public Impl::Iterator<typename Container::const_iterator>{
public:
   explicit ConstIterator(const Container& container)
       : Impl::Iterator<typename Container::const_iterator>(container.begin(), container.end())
   {
 
   }
 
};
 
template<class Container>
auto makeIterator(Container& container) -> Iterator<Container>{
   return Iterator<Container>(container);
}
 
template<class Container>
auto makeIterator(const Container& container) -> ConstIterator<Container>{
   return ConstIterator<Container>(container);
}
 
template<class Container>
auto makeConstIterator(const Container& container) -> ConstIterator<Container>{
   return ConstIterator<Container>(container);
}
 
 
Далее показан пример его использования:
Код
C++ (Qt)
QVector<double> xNodes; // x coordinates array
QVector<double> yNodes; // y coordinates array
QVector<double> zNodes; // z coordinates array
QMatrix3x3 rotMatrix; // rotation matrix
/*......*/
for (auto itX = makeIterator(xNodes), itY = makeIterator(yNodes), itZ = makeIterator(zNodes);
   itX.hasNext() && itY.hasNext() && itZ.hasNext();
   ++itX, ++itY, ++itZ){
   rotateVertex(rotMatrix, *itX, *itY, *itZ);
}
 


Название: Re: Универсальный итератор
Отправлено: Пантер от Ноябрь 03, 2015, 11:07
Для создания константного итератора нужно назвать makeConstIterator. Это я не доглядел.


Название: Re: Универсальный итератор
Отправлено: m_ax от Ноябрь 03, 2015, 11:15
Цитировать
Код
C++ (Qt)
for (auto itX = makeIterator(xNodes), itY = makeIterator(yNodes), itZ = makeIterator(zNodes);
   itX.hasNext() && itY.hasNext() && itZ.hasNext();
   ++itX, ++itY, ++itZ){
   rotateVertex(rotMatrix, *itX, *itY, *itZ);
}
 
А чем это отличается от:
Код
C++ (Qt)
for (auto itX = xNodes.begin(), itY = yNodes.begin(), itZ = zNodes.begin();  itX !=xNodes.end(); ++itX, ++itY, ++itZ)
{
   rotateVertex(rotMatrix, *itX, *itY, *itZ);
}
 


Название: Re: Универсальный итератор
Отправлено: Пантер от Ноябрь 03, 2015, 11:17
m_ax, а если разные размеры у векторов?


Название: Re: Универсальный итератор
Отправлено: m_ax от Ноябрь 03, 2015, 11:20
Цитировать
m_ax, а если разные размеры у векторов?
Ну пусть будут разные  :)

Код
C++ (Qt)
for (auto itX = xNodes.begin(), itY = yNodes.begin(), itZ = zNodes.begin();  itX !=xNodes.end() && itY != yNodes.end() && itZ != zNodes.end(); ++itX, ++itY, ++itZ)
{
   rotateVertex(rotMatrix, *itX, *itY, *itZ);
}
 


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 03, 2015, 11:25
Для создания константного итератора нужно назвать makeConstIterator.
Добавил


Название: Re: Универсальный итератор
Отправлено: Пантер от Ноябрь 03, 2015, 11:26
m_ax, у ТС короче и как-то красивее получается. Решение не претендует на универсальность и замену основного подхода. Скорее, как одно из решений для упрощения. Плюс, человек поучился работе с шаблонами. :)


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 03, 2015, 11:28
m_ax, а это хорошо, что у нас end() вызывается на каждой итерации?


Название: Re: Универсальный итератор
Отправлено: Пантер от Ноябрь 03, 2015, 11:29
Вызов end() скорее всего компиль соптимизячит и сделает один раз. Но многие советуют все же делать так (auto it = v.begin(), end = v.end(); it != end; ++it)


Название: Re: Универсальный итератор
Отправлено: Igors от Ноябрь 03, 2015, 11:33
Код
C++ (Qt)
size_t limit = qMin(qMin(xNodes.size(), yNodes.size()), zNodes.size());
for (size_t i = 0; i < limit; ++i)
   rotateVertex(rotMatrix, xNodes[i], yNodes[i], zNodes[i]);
А если "учится" то давно пора x, y, z иметь как структуру с операторами, а не держать их отдельно в сопливых массивах.


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 03, 2015, 11:34
Код
C++ (Qt)
for (auto itX = xNodes.begin(), itY = yNodes.begin(), itZ = zNodes.begin(), xEnd = xNodes.end(), yEnd = yNodes.end(), zEnd = zNodes.end();  itX != xEnd && itY != yEnd  && itZ != zEnd; ++itX, ++itY, ++itZ)
{
   rotateVertex(rotMatrix, *itX, *itY, *itZ);
}
Изначально был такой вариант


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 03, 2015, 11:36
Игорь, а у меня формат стороннего файла на входе именно по координатам. Я решил не заниматься перетасовками из векторов в структуру и обратно


Название: Re: Универсальный итератор
Отправлено: m_ax от Ноябрь 03, 2015, 11:47
Цитировать
m_ax, а это хорошо, что у нас end() вызывается на каждой итерации?
Я очень сомневаюсь, что это может привести хоть сколь-нибудь заметному эффекту, даже без оптимизации)

Кстатии, если посмотреть на стандартные алгоритмы такие как, например, copy, transform и т.д. которым на вход передаётся две  последовательности, то у всех у них размер определяется первой, т.е.:
Код
C++ (Qt)
std::copy(v.begin(), v.end(), res.begin()); // res.end() не передаём
 
 
И я думаю это правильно. Но это так.. мысли вслух)  


Название: Re: Универсальный итератор
Отправлено: Igors от Ноябрь 03, 2015, 11:56
Игорь, а у меня формат стороннего файла на входе именно по координатам. Я решил не заниматься перетасовками из векторов в структуру и обратно
Не надо прикрываться спецификой задачи. Позиция/координата как единая структура - сущность фундаментальная, какая бы задача ни была. Написав свой класс "координата" Вы научились бы куда большему чем дают эти игры с "синтаксическим сахаром". Кстати основания "велосипедить" имеются - QVector3D сделан просто ужасно


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 03, 2015, 12:25
Кстатии, если посмотреть на стандартные алгоритмы такие как, например, copy, transform и т.д. которым на вход передаётся две  последовательности, то у всех у них размер определяется первой
m_ax, в этом что-то есть.... Но в этом варианте явно видно, кто управляет концом цикла. В моём же случае без дополнительного кода не ясно, кто должен завершать цикл.

Игорь, я умею писать классы с методами и написание класса "координата" меня бы ничему новому не научило бы. Не вижу смысла создавать какие-то структуры, которые будут вносить дополнительные расходы в плане кода. Думаю, что если и появится необходимость в таком классе, то внесение изменений не будет нести катастрофичный характер.
QVector3D для большей гибкости вы можете заменить на QGenericMatrix либо найти другой уже написанный вариант этого класса. Не думаю, что такая задача осталась без внимания.


Название: Re: Универсальный итератор
Отправлено: Igors от Ноябрь 03, 2015, 13:17
Игорь, я умею писать классы с методами и написание класса "координата" меня бы ничему новому не научило бы. Не вижу смысла создавать какие-то структуры, которые будут вносить дополнительные расходы в плане кода. Думаю, что если и появится необходимость в таком классе, то внесение изменений не будет нести катастрофичный характер.
QVector3D для большей гибкости вы можете заменить на QGenericMatrix либо найти другой уже написанный вариант этого класса. Не думаю, что такая задача осталась без внимания.
Конечно можно и готовое взять. Более того, так чаще всего и приходится поступать, все с нуля писать - не подход. Но вот беда - все это "использование готового" очень поверхностно и понимания не дает. Человек как бы скользит от одного готового решения к другому, что дает иллюзию прогресса. И вот он уже весьма уверенно заявляет "я умею", "не вижу смысла" :) Ну в самом деле, что такого уж хитрого в классе "вектор"? Просто "класс с методами". Может с точки зрения "чистого программирования" это и так, но на практике означает - человек с 3D работал мало, или вообще только чего-то слышал.


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 03, 2015, 13:38
Игорь, я не понимаю, к чему вы клоните. У вас какие-то рассуждения без полезных выводов.


Название: Re: Универсальный итератор
Отправлено: Racheengel от Ноябрь 03, 2015, 15:46
оффтоп: о, новый срачок пошел :)


Название: Re: Универсальный итератор
Отправлено: Igors от Ноябрь 04, 2015, 09:20
Игорь, я не понимаю, к чему вы клоните. У вас какие-то рассуждения без полезных выводов.
Я к тому что надо идти от жизни, от задачи. А у Вас погоня за "модой", пример использования явно надуман. Какой вообще смысл совместного использования контейнеров разной длины? Хз, а "хвосты" - что это, если не юзаете, то зачем храните? Ладно, пусть это гипотетический случай, но чего же в цикле 3 раза парить hasNext если эту проверку можно сделать один раз, и даже код короче?

Я понимаю что цели чисто учебные, типа освоить "traits" (который я, кстати, так и не знаю), и "приводить" контейнер к жаба-стилю (next, hasNext). Но все-таки полный отрыв от практики выглядит плохо.

оффтоп: о, новый срачок пошел :)
Напомнило анекдот про мух  :)


Название: Re: Универсальный итератор
Отправлено: Old от Ноябрь 04, 2015, 09:58
Но все-таки полный отрыв от практики выглядит плохо.
Где вы видите отрыв от практики? Да еще и полный? :)
Человек сделал итератор, он может пробегаться по любым коллекциям. Что в этом плохого? Итераторы нужно уметь писать.
То что он в примере использует какие-то три контейнер чисел ни о чем не говорит. С таким же успехом там мог быть один контейнер пар или два контейнера строк или ...
Какие то у вас не состоятельные претензии. :)


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 04, 2015, 11:00
Пример использования не надуман. Этот пример, как я уже упоминал, есть часть моего проекта.
Я честно не вижу здесь погоней за модой. Код получился обобщённый и его с лёгкостью можно использовать в любом проекте не внося каких-либо изменений.
Вы утверждаете, что написав класс я научился бы чему-то больше... А вы не заметили, что я привёл 3 класса?
А на случай нелюбви к джава стилю предусмотрены привычные методы, которые не несут доп расходов


Название: Re: Универсальный итератор
Отправлено: Racheengel от Ноябрь 04, 2015, 11:46
Какой вообще смысл совместного использования контейнеров разной длины?

Вполне реалистичная задача. Например, мне не так давно нужно было сделать сравнение двух векторов разной длины - найти в них общие последовательности по определенному критерию. Перепробовал несколько вариантов, и с итераторами, и без, в итоге наиболее эффективным оказался поиск с задействованием SSE-интринзиков (но то уже детали).


Название: Re: Универсальный итератор
Отправлено: Igors от Ноябрь 05, 2015, 06:52
Вы утверждаете, что написав класс я научился бы чему-то больше... А вы не заметили, что я привёл 3 класса?
Да, утверждаю, и дело не в количестве классов.
Код
C++ (Qt)
rotateVertex(rotMatrix, *itX, *itY, *itZ);
Это как-то "еще терпимо", но уже кандидат на снос. Нужно стремиться к этому
Код
C++ (Qt)
rotateVertex(rotMatrix, &pos);
Где pos - нормальная структура. Часто говорят "С с структурами", мол, это примитивно написано, не используются современные средства и все такое. При этом, однако, забывают что если те самые структуры спроектированы плохо, то никакие мега-средства не помогут. А у Вас зияет дыра в самом базовом классе (точнее его у Вас просто нет). И надо его создавать, а не латать какими-то итераторами.

Ну вот не работают так люди с вертексами, никто не бегает с иксом, игреком и зет всякий раз. Вы упираетесь, дескать, "а в моей задаче так надо" - на здоровье, Ваше право. Но это совершенно бесперспективно, как для проекта, так и для творческого роста  :)


Название: Re: Универсальный итератор
Отправлено: Igors от Ноябрь 05, 2015, 07:08
Да, вот еще
Код получился обобщённый и его с лёгкостью можно использовать в любом проекте не внося каких-либо изменений.
Заниматься "общими" вещами очень приятно :) Но вот когда доходит до конкретного использования - хммм... ну как-то не видно "особых выгод", а то и просто хуже чем написать это место без затей. Как в Вашем примере - почему бы не вычислить число итераций цикла один раз? (и не гонять воздух hasNext). Хорошо, задачи разные бывают, приведите др пример где эта обобщенная конструкция оказывается очень даже к месту. Словом - убедите.


Название: Re: Универсальный итератор
Отправлено: Пантер от Ноябрь 05, 2015, 09:47
Да, вот еще
Код получился обобщённый и его с лёгкостью можно использовать в любом проекте не внося каких-либо изменений.
Заниматься "общими" вещами очень приятно :) Но вот когда доходит до конкретного использования - хммм... ну как-то не видно "особых выгод", а то и просто хуже чем написать это место без затей. Как в Вашем примере - почему бы не вычислить число итераций цикла один раз? (и не гонять воздух hasNext). Хорошо, задачи разные бывают, приведите др пример где эта обобщенная конструкция оказывается очень даже к месту. Словом - убедите.
А зачем человеку тебя убеждать? О_о Он сделал итератор и поделился им с общественностью. Тебе не подошло решение? Так и проходи мимо. Кому-нибудь решение понравится и он его заюзает.


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 05, 2015, 10:03
не гонять воздух hasNext
А где тут воздух гоняется? Если сравнивать с #9 (http://www.prog.org.ru/index.php?topic=29495.msg216749#msg216749), то чем это хуже i < limit?


Название: Re: Универсальный итератор
Отправлено: m_ax от Ноябрь 05, 2015, 11:29
От себя пара маленьких замечаний:

1) Для stl совместимости, лучше наследоваться от std::iterator, где указать iterator_category и т.д.
2) Для универсальности можно было бы сделать его Random Access итератором..
3) Хорошо бы иметь возможность пробегаться и по обычным C-массивам.

 :)



Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 05, 2015, 12:15
m_ax, спасибо. Посмотрю.


Название: Re: Универсальный итератор
Отправлено: Igors от Ноябрь 06, 2015, 06:53
Кому-нибудь решение понравится и он его заюзает.
Ну пока в это совершенно не верится. Привлекаем чужой класс (уже отсев 90%), но в рез-те получаем бОльший размер кода, заметно хуже читаемого, и заметно медленнее на выполнении. Может я не понял как юзать? Но простого ясного примера почему-то не находится. Ну так и может и вся затея была мертворожденной?

От себя пара маленьких замечаний:

1) Для stl совместимости, лучше наследоваться от std::iterator, где указать iterator_category и т.д.
2) Для универсальности можно было бы сделать его Random Access итератором..
3) Хорошо бы иметь возможность пробегаться и по обычным C-массивам.
Ага-ага, и вот уже пестуется очередной класс-упырь о который будут ломать ноги. Общность - так уж общность! А кому оно надо и зачем - неважно. Осталось только повтыкать его везде в код :'(

А где тут воздух гоняется? Если сравнивать с #9 (http://www.prog.org.ru/index.php?topic=29495.msg216749#msg216749), то чем это хуже i < limit?
Тем что i < limit зовется один раз, да и сравнение чисел пошустрее


Название: Re: Универсальный итератор
Отправлено: Old от Ноябрь 06, 2015, 07:13
Еще одна тема переросла в "охоту на ведьму", имя которой итератор. :)
Жалкое зрелище.


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 10, 2015, 10:51
2) Для универсальности можно было бы сделать его Random Access итератором..
Не совсем понятно, что должно быть реализовано для
X a;
b = a; (ну, тут наверное, просто копировать все поля)
a == b
a != b
a < b
a > b
a <= b
a >= b
Также не понятно, как должны выполняться операции типа a += n. Операторами ++ приходить к результату получается?


Название: Re: Универсальный итератор
Отправлено: m_ax от Ноябрь 10, 2015, 12:47
Цитировать
Не совсем понятно, что должно быть реализовано для
Ну помимо перечисленного должно быть и operator+=(size_t n) и operator-=(size_t n).

Цитировать
Операторами ++ приходить к результату получается?
Нет, для тех контейнеров, которые random access использовать их средства, адя тех которые не поддерживают это, то да, остаётся ++)
Но это уже всё есть в стандартной библиотеке http://en.cppreference.com/w/cpp/iterator (http://en.cppreference.com/w/cpp/iterator). В частности есть специализации таких функций как
advance
distance
next
prev
Они умеют работать и с C масивами и с обычными контейнерами.

Я не совсем понимаю, как вы ваш универсальный итератор будет работать с стандартными алгоритмами? Например с std::sort? 


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 10, 2015, 13:16
Под словом универсальность я больше подразумевал то, что этот шаблон позволяет пробежаться по элементам любого контейнера. А так да, его не применишь его к алгоритмам. С названием темы я всё-таки ошибся.
Про operator+=(size_t n) более менее понятно. Вроде как должно появиться в классе поле current_, которое будет смещаться.


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 10, 2015, 13:36
Хотя, можно прикрутить методы begin(), end() и подавать в sort. Вроде


Название: Re: Универсальный итератор
Отправлено: m_ax от Ноябрь 10, 2015, 13:37
Цитировать
Под словом универсальность я больше подразумевал то, что этот шаблон позволяет пробежаться по элементам любого контейнера.
За исключением C массивов)

Цитировать
Вроде как должно появиться в классе поле current_, которое будет смещаться.
Нет, не надо никакого доп. поля, просто:
Код
C++ (Qt)
operator+=(size_t n)
{
    return std::advance(current_, n);
}
 
Причём, advance знает к какой категории (std::iterator_traits<decltype(begin_)>::iterator_category) относитчя begin_ и будет подсовывать свою соответствующую специализацию.

Кстатии, с вашим итератором std::iterator_traits работать не сможет.. Поэтому я и писал выше, что для stl совместимости лучше наследоваться от std::iterator.


Название: Re: Универсальный итератор
Отправлено: __Heaven__ от Ноябрь 10, 2015, 13:58
Спасибо. Посижу ещё почитаю  :)