Зодачка

[psilogic]

Специально для любителей шОблоноф и прочих C++ наворотов. :) Сразу пердупердяю: задачка с подвохом.

Дано.

В программе есть некоторое количество классов, которые являются элементами односвязных списков с internal storage (проще говоря, это когда указатель на следующий элемент является членом класса).

Классы имеют вид:

class MyClass...
{
   MyClass *nextListItem;

Причем, варьируется не только название класса, но и название поля "nextListItem".

Задача.

Написать универсальную функцию вставки в начало списка с применением template, inline и pointer-to-member операторов. На входе должны быть: вставляемый элемент; указатель на первый элемент; название поля, указывающего на следующий элемент и тип класса. Функция может быть глобальной или членом namespace или функцией какого-либо нового класса - важно, чтобы она была одна, но работала для всех тех классов. Функция должна работать примерно так же, как ниже представленный #define:

#define INSERT_TO_LIST(firstItemPtr, item, nextItemName) \
(item)->nextItemName= (firstItemPtr), (firstItemPtr)= (item)

Посчитать количество строк в полученной функции. Факультативно: перечислить и обосновать преимущества перед приведенным #define.

Comments

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

подписался на каменты.

[afa-at-work.livejournal.com]

гх.
а можно на рубях?
ну не люблю я статичную типизацию, да

[dii.livejournal.com]

namespace ops
{

	template <class T>
	struct node_traits
	{
		typedef void undefined_next_member_ptr ;
		static undefined_next_member_ptr next_ptr() ;
	};

#define DECLARE_NEXT_PTR(className, nextNodeName) \
	template <> struct ::ops::node_traits<className> \
	{ \
		static className * className::*next_ptr() \
		{ \
			static className * className::* const t = &className::nextNodeName ; \
			return t ; \
		} \
	} ;


	template <class T>
	void prepend(T * &first_item, T * new_item)
	{
		T * T::* const next_item_name = node_traits<T>::next_ptr() ;
		new_item->*next_item_name= first_item ;
		first_item = new_item ;
	}

} // ops


struct node
{
	node(node * next = 0, int val = 0): next_(next), val_(val) {}
	node * next_ ;
	int val_ ;
} ;
DECLARE_NEXT_PTR(node, next_)


int main(array<System::String ^> ^args)
{
	node n1(0, 111) ;
	node n2(0, 222) ;

	node * p1 = &n1 ;
	node * p2 = &n2 ;

	ops::prepend(p2, p1) ;

	return 0;
}

Писанины, конечно, побольше :)
Но есть и преимущества:
- не нужно каждый раз писать название указателя на следующий член;
- значительное повышение вашей незаменимости для работодателя :)

[psilogic.livejournal.com]

это откуда ужасть такая? :)))))

[dii.livejournal.com]

из головы только что придумал

[psilogic.livejournal.com]

вы там поосторожнее с мухоморами :)))

мм?

[snusmumrikkk.livejournal.com]

template
inline T* unshift(T* &list, T* item, T* T::*member)
{
	item->*member = list;
	return list = item;
}

Что я пропустил?

Re: мм?

[snusmumrikkk.livejournal.com]

Сорри, параметр шаблона — <class T>

Re: мм?

[psilogic.livejournal.com]

Практически идеально! А подвох "в уме" заметить, конечно, сложно. Дело в том, что по условию поле-указатель на следующий является private. Соответственно при попытке написать вызов этой функции (иначе как изнутри класса) компилятор ругнется матом :)

Re: мм?

[snusmumrikkk.livejournal.com]

У твоего макроса та же проблема по идее ;).
По-твоему ее можно решить? (не говори пока решение, если ты его знаешь)

Re: мм?

[psilogic.livejournal.com]

Да, у макроса та же ерунда. Единственный плюс: макрос хотя бы можно вызвать из функции класса MyClass. А эту функцию даже так не вызовешь. Совсем идеального решения я не знаю, неидеальных, но работающих приходит в голову много. Мне интересно, что ты предложишь.

Re: мм?

[snusmumrikkk.livejournal.com]

Гм, изнутри класса прекрасно вызывается. А извне и не должна, мне кажется, хотя бы чтоб не дискредитировать слово private. Я бы сильно расстроился, если б это было возможно (без изменения тела класса).

Re: мм?

[psilogic.livejournal.com]

Изнутри другой функции класса прекрасно вызывается, если ты сделаешь саму функцию unshift методом класса. А если оставишь ее внешней, то получится, что ты обращаешься из функции класса к внешней функции unshift которая уже в свою очередь пытается обратиться к приватному полю member класса. И компилятор ругается (возможно, не любой). А #define разворачивается непосредственно в операторы, которые исполняются как часть функции класса, что разрешено.

Да, тело класса, конечно, придется курочить так или иначе. Лично для себя я сделал так:

template <class Type>
class ListHelper
{
public:
    static inline void insert(Type *val, Type *&first, Type * Type::*next) 
    {
        val->*next = first;
	first = val;
    }
};

В самом классе MyClass приходится использовать friend:

class MyClass...
{
    friend class ListHelper<MyClass>>;
    MyClass *nextItem;

Ну и вызов так:

ListHelper<MyClass>::insert(item, first, &MyClass::nextItem);

Позитив этого подхода -
1. Сакральное поле nextItem по-прежнему закрыто от некорректного использования.
2. В ListHelper можно написать еще кучу функций для работы со списком, и под каждую новую функцию уже не надо будет писать "friend" и модифицировать MyClass.

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

на «динамических» языках не интересно, это кто угодно сделает.

алсо, чуть не забыл: руби — херня.

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

O_O

с похмелюги почитал — гойлова ещё сильней заболела…

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

кстати сказать, если это код из «продакшына» — то кого-то надо больно убить. ибо все «списковые» классы надо наследовать от одной базы, и там иметь итераторы да все функции добавления/удаления.

[afa-at-work.livejournal.com]

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

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

эй! ты весь холивар поломал! это я собирался сказать «не пишите на эрзацах, используйте православный smalltalk!» %-)

[afa-at-work.livejournal.com]

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

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

(тихо) ни хуя себе! ты чо, старый бородач? O_O

[snusmumrikkk.livejournal.com]

Необязательно от одной базы. Посмотрите на std::vector и std::list. У них даже методы добавления не симметричны. Вы уже хотите убить Степанова?

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

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

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

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

[http://technorati.com/people/technorati/ketmar (from livejournal.com)]

вдогон: массив != списку, так что пример некорректный.

[psilogic.livejournal.com]

Нет, не из продакшена, это задачка. Задачка связана с реальными вещами, где наследовать от одной базы бесполезно. Прикинь, что будет, если элемент с internal storage лежит в нескольких списках. В wiki-статье говорится, что это невозможно, но это вполне возможно :)