Определение метода вне объявления шаблонного класса

[Mayor]

линковка шаблона

Код:

#ifndef intrusive_list__HHHH
#define intrusive_list__HHHH
struct link_err {
	string s;
	link_err(const char* pc):s(pc){}
};
struct slink { //base class for intrusive single linked list
	slink* next;
	slink(slink* p=0):next(p) {}
};
template<class T> class intrusive_list {
	T *head;
	T *last;
	unsigned int s;
//	size_t s;
	public:
	class iterator {
		T* p;
		public:
		iterator(T* pp):p(pp) {}
		iterator& operator++(int ) { p=static_cast<T*>(p->next); return *this; }
		T& operator*() { return *p; }
		bool operator==(const iterator& i) { return p==i.p; }
		bool operator!=(const iterator& i) { return p!=i.p; }
	};
	intrusive_list():head(0),last(0),s(0) {}
	iterator begin() { return iterator(head); }
	iterator end() { return iterator(0); }
	void push_front(T& t) ; 
	void push_back(T& t) ; 
	iterator& erase(iterator& i) {
		if (!s) throw link_err("empty error");
		s--;
		if (!s)  { 
			head=last=0;
			return 0;
		}
		if ( head == i.p ) {
			head=i.p->next;
			i.p->next=0;
			i++;
			return i;
		}
	}
};


template<class T> void intrusive_list<T>::push_front(T& t) { 
	s++;
	t.next=head;
	if(! last) last=&t;
	head=&t;
	return;
}
template<class T> void intrusive_list<T>::push_back(T& t) { 
	s++;
	if(! last)  head=last=&t;
	else {
		last->next=&t;
		last=&t;
	}
	return;
}
#endif

как вынести erase за пределы объявления класса? (чтобы получилось как push_front,push_back)

как вынести определения push_front,push_back,erase в отдельный translation unit?

[Алексей++]

почему то не удаётся тип   intrusive_list<T>::iterator& , возвращаемый из функции

вынести за пределы шаблона. У меня скомпилировалось таким кандибобером

Код:

template<class T> class intrusive_list {
	T *head;
	T *last;
	unsigned int s;
	public:
	class iterator
	{
		T* p;
		public:
		iterator(T* pp):p(pp) {}
		iterator& operator++(int ) { p=static_cast<T*>(p->next); return *this; }
		T& operator*() { return *p; }
		bool operator==(const iterator& i) { return p==i.p; }
		bool operator!=(const iterator& i) { return p!=i.p; }
	};

	intrusive_list():head(0),last(0),s(0) {}
	iterator begin() { return iterator(head); }
	iterator end() { return iterator(0); }
	void push_front(T& t) ; 
	void push_back(T& t) ; 

	iterator& erase(iterator& i)
	{
		erase(i,this);
		return i;
	}

  //костыль
	static void erase(iterator& i,intrusive_list* pThis);
};


template<class T>
void intrusive_list<T>::erase(class intrusive_list<T>::iterator& i,intrusive_list<T>* pThis)
{
	//this == pThis
}

[Mayor]

таже ситуация, причем я до того докомпилился, что у меня g++ перестал size_t узнавать

а по второму вопросу: как их потом в отдельный файл исходников вынести?

у меня если erase оставить внутри объявления класса, линкер начинает ругаться, что отсутсвуют функции push

[Алексей++]

у меня компилится нормально. А в разные файлы разнести не получится - где то об этом уже говорили

[Mayor]

у меня компилится нормально. А в разные файлы разнести не получится - где то об этом уже говорили

странно порыл документацию, вроде бы разносить по файлам можно через keyword export

только у меня на g++ 4.3.2  : export unsupported and ignored

может какие другие компиляторы его поддерживают?

или его из стандарта уже вынесли?

[Алексей++]

не усложняй опять, скомпилируй поначалу в одном хоть файле. А если что то не компилируется:
1) копию проекта
2) удаляй всё лишнее из кода и выявляй причину нестыковки
3) добивайся положительного результата в культяпке
4) применяешь полученные опытным путём данные к исходному полному проекту

[Вад]

Метод тыка практикуете?
Насколько мне известно, компилирование определения шаблона в отдельный модуль в стандарт ещё только собирались вносить (Степанов, один из авторов STL, об этом в одном интервью говорил).

А насчёт определения метода вне объявления шаблонного класса - в стандарте ж всё есть

3 When a member function, a member class, a static data member or a member template of a class template is
defined outside of the class template definition, the member definition is defined as a template definition in
which the template-parameters are those of the class template. The names of the template parameters used
in the definition of the member may be different from the template parameter names used in the class template
definition. The template argument list following the class template name in the member definition
shall name the parameters in the same order as the one used in the template parameter list of the member.

Код:

template<class T1, class T2> struct A {
void f1();
void f2();
};
template<class T2, class T1> void A<T2,T1>::f1() { } // OK
template<class T2, class T1> void A<T1,T2>::f2() { } // error

[Алексей++]

Вад, ну метод Н.Т. ещё никто не отменял, иногда помогает )

А с типом функции void проблем и не возникло - не получается с функцией типа iterator&

[Mayor]

Метод тыка практикуете?
Насколько мне известно, компилирование определения шаблона в отдельный модуль в стандарт ещё только собирались вносить (Степанов, один из авторов STL, об этом в одном интервью говорил).

А насчёт определения метода вне объявления шаблонного класса - в стандарте ж всё есть

дак мы же вроде шаблон метода с 1 параметром типа использовали и обзывали его так же как в определении шаблона

и еще с этой erase дизайнерская непонятка вышла, чтобы новую тему не создавать с вышеприведенным кодом, спрошу здесь:

допустим erase удаляет последний объект списка, а итератор держит указатель на объект приватным,  как занулить ссылку на объект, чтобы итератор стал равным итератору возвращаемому в end() ?

единственное, что пришло в голову добавить в итератор unlink, но подсознание подсказывает мне, что че то в этом криво:

Код:

	class iterator {
		T* p;
		public:
		iterator(T* pp):p(pp) {}
		iterator& operator++(int ) { p=static_cast<T*>(p->next); return *this; }
		T& operator*() const { return *p; }
		operator T*() const  { return p; }
		iterator& unlink() { p->next=0;return *this;}
	};
	iterator end() { return iterator(0); }
	iterator& erase(iterator& i) {
		if (!s) throw link_err("empty error");
		s--;
		if (!s)  { 
			head=last=0;
			return i.unlink();
		}
		if ( head == i ) {
			//head=i.p->next;
			//i.p->next=0;
			i++;
			return i;
		}
		return i;
	}

думал создать статический член iterator, который можно вернуть в end(), дак это тоже потребует определения его в отдельном модуле ?
или в итераторах можно выносить указатель на объект из приватной части?

как вынести erase за пределы объявления класса? (чтобы получилось как push_front,push_back)

только что на рсдн подсказали:

Код:

template <class T>
    typename intrusive_list<T>::iterator& intrusive_list<T>::erase(iterator& i) {
        if (!s) throw link_err("empty error");
        s--;
        if (!s)  { 
            head=last=0;
            return 0;
        }
        if ( head == i.p ) {
            head=i.p->next;
            i.p->next=0;
            i++;
            return i;
        }
    }

зы типа недостаточно научно тыкали, оставалось то всего 1 словечко подобрать и вставить

[Антон (LogRus)]

а в сообщениях об ошибка всё русским языком писалось

Код:

iterator& intrusive_list<T>::erase(iterator& i)

poli_examp.cpp(63) : error C2143: syntax error : missing ';' before '&'
poli_examp.cpp(63) : error C2501: 'iterator' : missing storage-class or type specifiers

Код:

template <class T>
intrusive_list::iterator& intrusive_list<T>::erase(iterator& i)

poli_examp.cpp(65) : error C2955: 'intrusive_list' : use of class template requires template argument list
        poli_examp.cpp(43) : see declaration of 'intrusive_list'

Код:

template <class T>
intrusive_list<T>::iterator& intrusive_list<T>::erase(iterator& i)

poli_examp.cpp(65) : warning C4346: 'intrusive_list<T>::iterator' : dependent name is not a type
        prefix with 'typename' to indicate a type

но чтение сообщений это не круто

[Алексей++]

да, typename это великая вещь ) А я и не обратил внимания даже сначала

[Mayor]

Код:

template <class T>
intrusive_list<T>::iterator& intrusive_list<T>::erase(iterator& i)

poli_examp.cpp(65) : warning C4346: 'intrusive_list<T>::iterator' : dependent name is not a type
        prefix with 'typename' to indicate a type

но чтение сообщений это не круто

фигасе, а как ты подобное сообщение об ошибке вывел?

у меня упроно выдает:

Код:

echo g++ main.cpp
g++ main.cpp
grc -e  g++  -O2 -Wall -Wextra --pedantic  --std=c++0x `pkg-config --cflags ` -c -o main.o main.cpp
Must specify package names on the command line
In file included from main.cpp:11:
intrusive_list.h:55: error: expected constructor, destructor, or type conversion before ‘&’ token
make: *** [main.o] Ошибка 1

[Антон (LogRus)]

это студия так ругается, в прочем в сообщении gcc тоже можно разобраться.

Код:

template<class T>
iterator intrusive_list<T>::erase(iterator i)

main.cpp:55: error: expected constructor, destructor, or type conversion before "intrusive_list"

орёт, что не может понять ,что у тебя в качестве возвращаемого параметра (я бы тоже не понял )

уточняем пространство имён

Код:

template<class T>
intrusive_list::iterator intrusive_list<T>::erase(iterator i)

main.cpp:55: error: `template<class T> class intrusive_list' used without template parameters
main.cpp:55: error: expected constructor, destructor, or type conversion before "intrusive_list"

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

Код:

template<class T>
intrusive_list<T>::iterator intrusive_list<T>::erase(iterator i)

main.cpp:55: error: expected constructor, destructor, or type conversion before "intrusive_list"

вернулись к тому с чего начали - тут вспоминаем, что работая с типами зависящими от параметра шаблона необходимо указвать ключевое слово typename иначе компилятор считает, что мы указываем на объект, а не на тип

впрочем, если вы читали Вандервуда, проблема бы решалась раньше.

PS: кстати erase должен получать и возвращать итератор по значению в крайнем случае по константной ссылке
иначе в него нельзя передавать временные обекты
например

Код:

    intrusive_list<slink> l;
    .............
    l.erase(l.begin()); // тут будет ошибка компиляции - согласно стандарту, правда VS на эту часть стандарта забила болт.

[Mayor]

а что тогда делать с итератором после erase?

вместо l.erase(l.begin()); вроде принято l.pop_front()

[Антон (LogRus)]

что хочешь, то и делай.

Код:

it = l.erase(it);

вполне корректная запись, т.к. ты возвращаешь валидный итератор и it не инвалидируется, но инвалидируются все итераторы указывающие на удалённый элемент, что в прочем было и раньше.

общепринятая практика передавать итераторы по значению

вместо l.erase(l.begin()); вроде принято l.pop_front()

Бугага я пользователь класса, я знаю его открытый интерфейс, что хочу то и делаю

[Mayor]

ну как только пользователь класса попытается скомпилить erase(x.begin) он сразу поймет, что что-то не правильно использует

хм а не слишком ли производительность пострадает от передачи по значению?
или мне лучше пока об этом не думать, а то класс так не допишу?

[sss]

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

LogRus, может вспомнил  - https://forum.shelek.ru/index.php/topic,14331.0.html

[Антон (LogRus)]

sss, лениво читать в любом случае у меня универсальная отмаза - "Я был молодой и глупый"

Блин опять... Все действия с попытками представлять контейнеры с помощью шаблонов, в конце концов приводят к использованию в качестве элементов этих контейнеров указателей на объекты классов, порожденных от одного предка. Тогда вопрос - на хера эти шаблоны?

так это их неотъемлемое свойство интрузивных контейнеров, а у товарища Mayor, как раз интрузивный контейнер.

хм а не слишком ли производительность пострадает от передачи по значению?

ну что же давай посчитаем размер итератора? правильно 4.
размер указателя при передаче по ссылке (мы же знаем что ссылка это иллюзия и на самом деле это указатель) ? о блин опять 4.
даже не знаю, что быстрее передать 4 байта или другие 4 байта? сам как считаешь?

[Алексей++]

LogRus, я знаю, я знаю, я знаю!  Быстрее передать 4 ))

[sss]

LogRus,  а что такое интрузивный? У меня словарь подчеркивает и взамен предлагает: непозитивный, бурбулятивный, креативный . Интересно, откуда это слово - бурбулятивный 

[Алексей++]

а у меня в словаре -
intrusive  [In'trHsIv]  adj назойливый (назойлив).

)

[Антон (LogRus)]

интрузивный контейнер это такой контейнер элементы которого должны иметь представление о том как работает контейнер.
в нашем случае элементы контейнера унаследованы от slink

Код:

struct slink { //base class for intrusive single linked list
	slink* next;
	slink(slink* p=0):next(p) {}
};

разбирая конкретный - случай элементы которые мы помещаем в контейнер, имеют ссылку на следующий элемент и эта ссылка необходима для корректной работы самого контейнера

ну развить мысль можете сами
эту мысль можете продолжить в сторону интрузивных умных указателей (например boost::intrusive_ptr)

что касается вот этого

Может лучше заточенный под указатели контейнер?

собственно нет проблем у нас в коде есть пара мест, где так и делается, только контейнер опять же не самописный, а взятый из BOOST
http://www.boost.org/doc/libs/1_40_0/libs/ptr_container/doc/ptr_container.html

[Mayor]

ну что же давай посчитаем размер итератора? правильно 4.
размер указателя при передаче по ссылке (мы же знаем что ссылка это иллюзия и на самом деле это указатель) ? о блин опять 4.
даже не знаю, что быстрее передать 4 байта или другие 4 байта? сам как считаешь?

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

когда ссылка просто поместится на стек и модифицируется по мере выполнения функции

[Антон (LogRus)]

Mayor, ну при током подходе единственно правильным решением я вижу сравнить сгенерированный код.

[sss]

Mayor, итератор копируется в стек и все. Модифицируемый стек обратно не копируется. При передаче по ссылке неявно используется указатель. Вообще как этого не знать. Удивительно...

Код:

template<class T> iterator intrusive_list<T>::erase(iterator i)

template<class T> iterator intrusive_list<T>::erase(iterator& i)

template<class T> iterator intrusive_list<T>::erase(iterator* i)

Какой метод вызова ты используешь? Два последних не имеют разницы... В принципе.

[Mayor]

никакой из этих, завис на возвращении итератора по ссылке

Mayor, ну при током подходе единственно правильным решением я вижу сравнить сгенерированный код.

а как это обычно делается?
я только бяки в gdb умею ставить, листинг выводить и значения переменных печатать

[Serg79]

я только бяки в gdb умею ставить, листинг выводить и значения переменных печатать

Mayor, что бы бяки в gdb не ставить, читай документацию по нему.

[Антон (LogRus)]

а как это обычно делается?
я только бяки в gdb умею ставить, листинг выводить и значения переменных печатать

и это говорит человек который темой аля "как лучше измерять время выполнения" всю плешь проел

[Mayor]

дак мне с винды слезать не охота, а тренироваться кодить нравиться под линухом - поэтому работают под виртуал боксом - в котором rdtsc не работает, вернее работает, но очень неточно

[Антон (LogRus)]

Mayor, читай тут тему еще раз
привязался как банный лист, к своей одной инструкции(у которой еще и куча минусов)

используй gprof или time в конце концов, не парь людям мозг (слов не хватает)