Конфликт итераторов

@maked0n · Регистрация: 27.03.2013

Author24 — интернет-сервис помощи студентам

Доброго времени суток. Пишу Timsort с использованием шаблонов и итераторов. Написал класс CTimsort, в нем все необходимые методы и их реализацию. Приведу небольшой кусок кода:

C++

#include <vector>
#include <iterator>
 
template<typename RandomAccessIterator, typename CCompare> class CTimsort
{
    static const int MIN_RUN_SIZE = 32;
    static const int MIN_GALLOP = 7;
    static const int INITIAL_TMP_STORAGE_LENGTH = 256; //maximum initial size of tmp array, which is used for merging
    RandomAccessIterator minGallop = 7;
 
    struct Run
    {
        RandomAccessIterator runBase;
        typename std::iterator_traits<RandomAccessIterator>::difference_type runLength;
        Run();
        Run(RandomAccessIterator b, typename std::iterator_traits<RandomAccessIterator>::difference_type l) : runBase(b), runLength(l) {}
    };
 
    //a stack for runs to be merged
    std::vector<Run> runs;
 
    /*
     *returns the run on the runPosition
     *runPosition - the position of the run in the stack
     */
    Run* GetRun(RandomAccessIterator runPosition)
    {
        Run* r = &runs.at(runPosition);
        return r;
    }
 
.............

Возникает ошибка на этапе компиляции:
no matching function for call to 'std::vector<CTimsort<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, std::less<int> >::Run, std::allocator<CTimsort<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, std::less<int> >::Run> >::at(__gnu_cxx::__normal_iterator<int*, std::vector<int> >&)'
В остальных местах кода, где используется std::vector<int>::at(), та же самая штуковина вылазит. Что я делаю не так?

@DrOffset · 06.10.2014, 23:21

Сообщение от maked0n

Что я делаю не так?

Метод at() у std::vector принимает индекс (size_t), а не итератор.

@maked0n · 06.10.2014, 23:28 **[ТС]**

А такой код будет правильно работать? Ведь runPosition, на сколько я понимаю, не будет "принадлежать" этому контейнеру.

C++

Run GetRun(RandomAccessIterator runPosition)
    {
        Run r = *(runPosition);
        return r;
    }

К тому же, тогда не работает такой код:

C++

1	*(runPosition).runLenght = 2;

@DrOffset · 06.10.2014, 23:39

Сообщение от maked0n

Ведь runPosition, на сколько я понимаю, не будет "принадлежать" этому контейнеру.

Нужно больше кода.
Если итератор получен у контейнера, он "принадлежит" ему так или иначе.

Сообщение от maked0n

К тому же, тогда не работает такой код:

Без контекста нельзя ни подтвердить ни опровергнуть это утверждение.

Добавлено через 1 минуту
PS. путаница с итераторами должна уйти, если начать воспринимать итератор как указатель на элемент.

@maked0n · 07.10.2014, 00:37 **[ТС]**

Вот весь "проблемный" код:

C++

#include <vector>
#include <iterator>
 
template<typename RandomAccessIterator, typename CCompare> class CTimsort
{
    static const int MIN_RUN_SIZE = 32;
    static const int MIN_GALLOP = 7;
    static const int INITIAL_TMP_STORAGE_LENGTH = 256; //maximum initial size of tmp array, which is used for merging
    RandomAccessIterator minGallop = 7;
 
    struct Run
    {
        RandomAccessIterator runBase;
        typename std::iterator_traits<RandomAccessIterator>::difference_type runLength;
        Run();
        Run(RandomAccessIterator b, typename std::iterator_traits<RandomAccessIterator>::difference_type l) : runBase(b), runLength(l) {}
    };
 
    std::vector<Run> runs;
 
    Run GetRun(RandomAccessIterator runPosition)
    {
        Run r = *(runPosition);
        return r;
    }
 
.....
 
void MergeCollapse(RandomAccessIterator firstElement, RandomAccessIterator lastElement, CCompare comp)
    {
        typename std::iterator_traits<RandomAccessIterator>::difference_type subtrahend = 1;
        while(runs.size() > 1)
        {
            if(std::distance(runs.end(), runs.begin()) > subtrahend &&
                    GetRun(runs.end() - subtrahend - 1).runLength <= GetRun(runs.end() - subtrahend).runLength +
                    GetRun(runs.end() - subtrahend + 1).runLength)
            {
                if(GetRun(runs.end() - subtrahend - 1).runLength < GetRun(runs.end() - subtrahend + 1).runLength)  --subtrahend;
                MergeAt(firstElement, lastElement, runs.end() - subtrahend, comp);
            }
            else if(GetRun(runs.end() - subtrahend).runLength <= GetRun(runs.end() - subtrahend + 1).runLength)
                MergeAt(firstElement, lastElement, runs.end() - subtrahend, comp);
            else break;
        }
    }
 
    void MergeForceCollapse(RandomAccessIterator firstElement, RandomAccessIterator lastElement, CCompare comp)
    {
        while(runs.size() > 1)
        {
            typename std::iterator_traits<RandomAccessIterator>::difference_type subtrahend = 1;
            if((runs.end() - subtrahend) > runs.begin() &&
                    GetRun(runs.end() - subtrahend - 1).runLength < GetRun(runs.end() - subtrahend + 1).runLength) --subtrahend;
            MergeAt(firstElement, lastElement, runs.end() - subtrahend, comp);
        }
    }

Я немного подправил код, ошибка поменялась:
no matching function for call to 'CTimsort<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, std::less<int> >::GetRun(__gnu_cxx::__normal_iterator<CTimsort<__gnu_cxx::__normal_iterator<int *, std::vector<int> >, std::less<int> >::Run*, std::vector<CTimsort<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, std::less<int> >::Run, std::allocator<CTimsort<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, std::less<int> >::Run> > >)'
Возникает при каждом использовании GetRun().

Также, в 23 строке следующая ошибка:
conversion from 'int' to non-scalar type 'CTimsort<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, std::less<int> >::Run' requested.

Ilot · 07.10.2014, 12:05

C++

1	Run r = *(runPosition);

Какие основания, что итератор указывает на объект Run? По хорошему вам следует описать для типа Run свой набор итераторов и оперировать ими.

@maked0n · 07.10.2014, 13:11 **[ТС]**

Сообщение от Ilot

Какие основания, что итератор указывает на объект Run?

Я считал, что такой вызов функции является основанием:

C++

1	GetRun(runs.end() - subtrahend - 1)

Я не прав?

Сообщение от Ilot

По хорошему вам следует описать для типа Run свой набор итераторов и оперировать ими.

Не потеряется ли в таком случае смысл в использовании RandomAccessIterator? И возможно ли тогда будет приводить RandomAccessIterator к какому-то RunIterator и наоборот при необходимости?

Ilot · 07.10.2014, 13:15

maked0n, если итератор используется классом Rum то почему вы его не инкапсулируете в этот класс?
Итератор предоставляется классом с которым он работает. Посмотрите реализацию любого итератора в контейнерах stl.

@DrOffset 18894 / 9851 / 2410 Регистрация: 30.01.2014 Сообщений: 17,295
	06.10.2014, 23:21	2
	Сообщение от maked0n Что я делаю не так? Метод at() у std::vector принимает индекс (size_t), а не итератор. 0

@DrOffset 18894 / 9851 / 2410 Регистрация: 30.01.2014 Сообщений: 17,295
	06.10.2014, 23:39	4
	Сообщение от maked0n Ведь runPosition, на сколько я понимаю, не будет "принадлежать" этому контейнеру. Нужно больше кода. Если итератор получен у контейнера, он "принадлежит" ему так или иначе. Сообщение от maked0n К тому же, тогда не работает такой код: Без контекста нельзя ни подтвердить ни опровергнуть это утверждение. Добавлено через 1 минуту PS. путаница с итераторами должна уйти, если начать воспринимать итератор как указатель на элемент. 0

Ilot $Эксперт по математике/физике$ 2048 / 1366 / 395 Регистрация: 16.05.2013 Сообщений: 3,506 Записей в блоге: 6
	07.10.2014, 13:15	8
	maked0n, если итератор используется классом Rum то почему вы его не инкапсулируете в этот класс? Итератор предоставляется классом с которым он работает. Посмотрите реализацию любого итератора в контейнерах stl. 0