[c++]: Определение защищённой функции класса возвращающей указатель

Olenenok

Определение защищённой функции класса возвращающей указатель на структуру определённую в области protected:
Объвление функции:

template <class T>

class CFoo

{

protected:

   template <class U> struct SGoo

   {

      ...

   }

   ............

   SGoo<T>* c_MyFunction(...);

   ............

};

Определение функции:

template <class T>

SGoo<T>* CFoo<T>::c_MyFunction(...) { ... }

  

Или

template <class T>

CFoo<T>::SGoo<T>* CFoo<T>::c_MyFunction(...) {...}

  

И никакой из вариантов не компилируется, никто не знает что делать?

maggi14

ну что за привычка пошла - писать "не компилируется", но не писать текст ошибки

zya369

template <class T>

class CFoo

{

protected:

        template <class U> struct SGoo

        {

        };

        SGoo<T>* c_MyFunction;

public:

        void qq

        {

                std::cout << this->c_MyFunction << std::endl;

        }

};

template <class T>

CFoo<T>::SGoo<T>* CFoo<T>::c_MyFunction {return 0;}

int main

{

        CFoo<int> qqq;

        qqq.qq;

        return 0;

}

все компилится - gcc 3.2.2
ЗЫ у тебя нет ";" после class SGoo{}

Olenenok

, использую VSC 7.xxxx, сообщение об ошибке такое:

d:\documents and settings\хозяин\мои документы\visual studio projects\dynamic array\listarrayimplementation.h(11) : warning C4346: 'CListArray<T>::SFrame<T>' : dependent name is not a type
prefix with 'typename' to indicate a type
d:\documents and settings\хозяин\мои документы\visual studio projects\dynamic array\listarrayimplementation.h(11) : error C2143: syntax error : missing ';' before '*'

kokoc88

А ты читать сообщения об ошибках не пробовал? Вот эту часть, например:
syntax error : missing ';' before '*'
А вообще судя по названию .h заголовка ты изобретаешь велосипед. Может лучше использовать стандартные классы для создания array of lists?

Olenenok

А вообще судя по названию .h заголовка ты изобретаешь велосипед. Может лучше использовать стандартные классы для создания array of lists?

Не, это критично по скорости. vector медленен: 1 элемент массивы - 1 элемент списка.

kokoc88

Я сомневаюсь, что ты так сходу напишешь template контейнер, который будет работать быстрее известной стандартной библиотеки.
Вектор медленный? Для какой задачи он медленный? Для частого удаления элементов из середины - медленный. Для доступа по индексу - самый быстрый.

Olenenok

Вектор медленный? Для какой задачи он медленный? Для частого удаления элементов из середины - медленный. Для доступа по индексу - самый быстрый.

Какова трудоёмкость?

kokoc88

VS такое не скомпилирует, я могу привести код но он уж больно похож на хак. Я сто раз сомневаюсь, что это и вся реализация в целом будет работать быстрее правильной комбинации стандартных теплейтов...

template <class TCObj> class CTemplClass

{

	template <class TSObj> struct SInner

	{

		TSObj m_Obj;

		SInner: m_Obj(5) {}

	};

	SInner<TCObj> m_sInner;

protected:

	SInner<TCObj> * GetInner;

public:

	TCObj GetTCObj;

};

template <class TCObj> TCObj CTemplClass<TCObj>::GetTCObj

{

	return GetInner->m_Obj;

}

template <class TCObj> typename CTemplClass<TCObj>::SInner<TCObj>* CTemplClass<TCObj>::GetInner

{

	return &m_sInner;

}

int main(int argc, _TCHAR* argv[])

{

	CTemplClass<int> cIntClass;

	std::cout << cIntClass.GetTCObj << std::endl;

	return 0;

}

kokoc88

Какая трудоёмкость?.. Может, ты опишешь поставленную тебе задачу, а я скажу, какие лучше контейнеры использовать?

Olenenok

Какая трудоёмкость?.. Может, ты опишешь поставленную тебе задачу, а я скажу, какие лучше контейнеры использовать?

Задача: быстро загонять в динамический массив содержимое по указателю (read (pBuffer, nBytes. Иметь доступ сравнимый по скорости к обычному

T array[N];  

kokoc88

И вектор тебя не устраивает чем?..

Olenenok

А ну сужу по его push_back. Что-то оно мне не нравиться - типа списка получается.

ppplva

Почитай документацию, что ли. Вектор - это далеко не "типа списка".

kokoc88

Нет, доступ в векторе не типа списка, а как раз сравним с обычным массивом. И ещё там явно не дискретный прирост, то есть наращивание не n*n.

Olenenok

Как загнать в vector<T> массив T array[1000], только не push_back - вызов функции в цикле меня явно не устраивает!

kamputer

Не понимаем элементарных структур данных и алгоритмов, зато умеем городить шаблоны.

kamputer

>И ещё там явно не дискретный прирост, то есть наращивание не n*n.
Должно быть что-то типа умножения размера на константу (типа 2 чтобы асимптотическая трудоёмкость вставки была O(1)

kokoc88

Ты как создаёшь массив T array[1000]? Вот вместо создания этого массива создавай и заполняй вектор.

Olenenok

Ты как создаёшь массив T array[1000]? Вот вместо создания этого массива создавай и заполняй вектор.

Так не пойдёт, я получаю по сети куски не больше определённого размера, но обычно длины 1024. Их мне и нужно запихивать в массив. А окончательную длину я всегда точно знать не могу.

kokoc88

Ну и делай алгоритм: получаешь кусок, запихиваешь в вектор. Если тебе важно хранить именно динамические буфферы, кладёшь в вектор T*, в чём проблема-то? Зачем писать свой темплейт класс, который (я уверен) будет работать медленнее вектора?

ppplva

Получаешь данные по сети, и не можешь позволить себе 1 вызов функции на каждые 1024 байта ? Так не бывает

Olyalyau

Должно быть что-то типа умножения размера на константу (типа 2 чтобы асимптотическая трудоёмкость вставки была O(1)

Асимптотическая трудоёмкость вставки в конец вектора в задаче вставки туда неограниченного числа
элементов -- O(n*n так как при realloc'е (а лучше ничего сделать нельзя, не налагая требований на операционку и существование только одного вектора в программе) вектор будет, в худшем случае,
копироваться во вновь отведённую память полностью.
Байда про амортизированное постоянное время "O(n)+" верна только для программ, которые не наращивают
вектор постоянно, а крутятся в районе некоторого значения size -- добавляют, удаляют, добавляют, удаляют и т.д. И то, желательно, предварительно зарезервировав под вектор место с запасом.
По-настоящему что-то лучшее O(n*n) для вставки в конец одновременно с чем-то не хуже O(1) при индексации обеспечивает вектор векторов. Через него, обычно реализован дек. (На самом деле для вставки в конец там тоже O(n*n но мультипликативная константа настолько мала, что в реальных программах вектор векторов ведёт себя в этом плане вполне прилично).

kokoc88

Речь шла о последовательной вставке N элементов в вектор. И это ну никак не квадрат.

kamputer

Асимптотическая трудоёмкость вставки в конец вектора в задаче вставки туда неограниченного числа
элементов -- O(n*n так как при realloc'е (а лучше ничего сделать нельзя, не налагая требований на операционку и существование только одного вектора в программе) вектор будет, в худшем случае,
копироваться во вновь отведённую память полностью.
Байда про амортизированное постоянное время "O(n)+" верна только для программ, которые не наращивают
вектор постоянно, а крутятся в районе некоторого значения size -- добавляют, удаляют, добавляют, удаляют и т.д. И то, желательно, предварительно зарезервировав под вектор место с запасом.

Гы-гы. Ну давай вместе посчитаем. Пусть в пустой вектор последовательно в конец вставляется N элементов. Для краткости будем считать, что N = 2^n. И пусть размер вектора при реаллокации увеличивается вдвое.
Таким образом, потребуется n реаллокаций (или n-1 ? Да похуй, лень аккуратно разбирать). При реаллокации номер k нужно скопировать 2^k уже добавленных элементов в новую область памяти.
Получаем: общее число операций равно чему-то типа N + сумма{k=1,...,n}(2^k) *, что очевидно имеет порядок O(N). Значит, на один элемент асимптотическая трудоёмкость составляет O(1).

Olenenok

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

evgen5555

Сначала напиши работающую программу

Dasar

Все-таки O(N*log_k(N - где k - во сколько раз увеличивается массив при реаллокации.

Olenenok

Сначала напиши работающую программу

Я не один пишу, а класс-таки написал и скорость приличная - проигрыш вектору при доступе к элементам порядка 15-25%, но это учитывая, что массив состоит из набора кадров и приходится переходить на другой кадр. Сейчас буду оптимизировать добавление, думаю, здесь выигрыш будет больше 25%...
При добавлении 100Мб такая картина:
Мой класс - 0 клоков
Вектор - 406 клоков.

kamputer

>Все-таки O(N*log_k(N - где k - во сколько раз увеличивается массив при реаллокации
Чота не пойму никак, как это получилось, поясни

Dasar

да, похоже что гоню

kokoc88

Мой класс - 0 клоков
Вектор - 406 клоков

Что это за бред?
PS Блин, и где те времена, когда я переписывал все стандартные вещи наивно думая, что у меня они будут работать быстрее?..

kokoc88

И 1024 раза в цикле добавлять в вектор нельзя.

Тебе не предлагали побайтно переносить данные в вектор. Тебе предлагали хранить буферы в векторе.

Olenenok

Тебе не предлагали побайтно переносить данные в вектор. Тебе предлагали хранить буферы в векторе.

Попробовал, скорость доступа становится ниже раза в 2 и уступает моему классу. Добавление происходит примерно со скоростью моего класса.
P.S. Это вопрос с историей. Я всё равно написал бы этот класс, мне интересно.
P.P.S. 0 и 406 - неудивительно, vector всё реаллокейтит и реаллокейтит (интересно, каково ему перетаскивать 50Мб буфера а мой планомерно добавляет кадры к списку. Правда, при рандомном доступе мой безбожно проиграет, но ,по логике задачи, его и не будет.

kokoc88

Вектор реалокейтит по-умному. См. выше оценки O(N). Если тебе не критичен рандомный доступ, а критично добавление в конец, так сразу и надо писать в задаче. И использовать не vector, а list.
Чисто для интереса, покажи свой класс что ли...

Olenenok

Куда?

kokoc88

Что куда? Класс что ли? Да куда угодно...

Olyalyau

Речь шла о последовательной вставке N элементов в вектор. И это ну никак не квадрат.

Дык, это я ночью писал
Конечно, все вхождения O(n*n) надо заменить на O(n а O(n)+ на O(1)+.

tipnote

покажи, плз, код (с std::vector с которым ты сравнивал код со своим классом.

kokoc88

В общем, там было примерно следующее: одновременное размещение N кадров размером 4096 uint в его темплейт классе versus размещение 4096*N uint внутри vector<uint>, причём работа с последовательным доступом к вектору была через [] (без итератора). Тайминги корректной программы с использованием вектора получились примерно следующие:
ClistArray размещение кадров+заполнение всех данных числами -- 531
ClistArray последовательный доступ -- 141
ClistArray случайный доступ (меняем 10000 uint) -- 17547
vector reserve+insert(NULL) -- 0
vector размещение "кадров" и заполнение данными -- 188
vector линейный последовательный доступ -- 141
vector случайный доступ (меняем 10000 uint) -- 31
Да, последовательная вставка в авторский темплейт класс не производилась. Но алгоритм там while (my_size < required_size) add_one_frame.

ppplva

лол

tipnote

хех
я тут просто попутно обнаружил, что можно сделать такую вставку:
void setFrame(unsigned int size, const byte* frame)
{
vector_of_bytes.insert(vector_of_bytes.endframe,frame+size);
}
честно говоря, всю жизнь думал, что работать должно только с обычными итераторами.
Так бы без этого треда и не узнал бы =)

Olenenok

лол

Это к чему?

okunek

Тайминги пробовал смотреть?

ppplva

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

Olenenok

,

, при линейном доступе скорость одинаковая. Рандомный доступ для моей задачи в принципе не нужен.
У меня была такая методика:
(1) Мой массив и вектор объявлялись пустыми
(2) Затем они увеличивались в размерах до 100Мб блоками по 1Кб.
Мой заполнялся в 2 раза быстрее. Вы знали, какую методику применил ? К тому же мой класс будет работать равномерно, не будет жрать ресурсы при реаллокейтах.

ppplva

ClistArray размещение кадров+заполнение всех данных числами -- 531
vector размещение "кадров" и заполнение данными -- 188

Вы знали, какую методику применил ?

И не сомневался.
А если гипотетический push_front применить, то твой класс не в 2 раза порвет вектор, а, наверное, в 20. Просто не надо ругать стандартные классы, если не умеешь ими пользоваться.

kokoc88

Затем они увеличивались в размерах до 100Мб блоками по 1Кб.

Конкретно в коде, который ты мне дал, твои кадры занимали 4кб, а вектор заполнялся интами в нереальном размере. Ты со своим объектом вёл работу как со списком буфферов по 4кб, а с вектором как с массивом интов через operator[] (тогда уж сразу бы брал int* и работал с ним). Я просто переделал вектор интов в вектор буферов (векторов). Кстати, я в STL всё-таки профан.
Кстати, у меня ещё прога падает на дебаге. Впрочем, она не падает на релизе.

Dasar

>Впрочем, она не падает на релизе.
Это всего лишь обозначает, что в release она просто портит память.

kokoc88

См. смайлик. Речь шла о его проге.

tipnote

>вектором как с массивом интов через operator[] (тогда уж сразу бы брал int* и работал с ним)?
в смысле, делал так?

void setFrameByIterations(unsigned int size, const int* frame)

{

   unsigned int old_size = array_of_frames.size;

   unsigned int new_size = old_size + size;

   array_of_frames.resize( new_size);

   for(unsigned int index = old_size; index < new_size; index++)

      array_of_frames[index] = frame[index - old_size];

}  

kokoc88

Нет, я говорил о конструкции вида int * pInts = &myVector[0];

tipnote

Да нет. Я спрашивал, как он делал.
>Нет, я говорил о конструкции вида int * pInts = &myVector[0];
эгм. разве это корректно?
В смысле, потом по этому указателю ходить.

ppplva

До первого реаллока
Как впрочем, и по итератору.

tipnote

Это понятно.
Нам разве гарантируют, что вектор хранит свои внутренние данные в виде последовательного (относительно порядка элементов) и непрерывного (относительно области памяти) массива?
Короче. Если бы разработчики вектора хотели дать такую возможность - они бы просто определили оператор приведения к соответствующему массиву.

kokoc88

Гарантируют.

ppplva

Я тоже так думал, но сейчас не могу найти явного подтверждения.
Думаю, во всех нормальных реализациях STL это верно.

ppplva

Гарантируется сложность доступа, но из нее ничего не следует. Например, можно хранить элементы в обратном порядке

tipnote

Вот и я не могу найти.
Но даже если и так - решение все равно не попадает под предусмотренное использование данных вектора.
Поэтому лучше так не делать.

kokoc88

Говорят, что инфа по этому поводу есть в стандарте. И в самом деле, если бы это было не так, то в STL'е не было бы возможности создавать примитивные буферы.

sasha79

И в самом деле, если бы это было не так, то в STL'е не было бы возможности создавать примитивные буферы.

Что ты имеешь ввиду?

kamputer

The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size.

Стандарт, п. 23.2.4.1

sasha79

О!
Дай, плз, ссылочку на стандарт или сам стандарт.