C
Chris M. Thomasson
I was wondering if there are any "gotchas" wrt using member pointers to
implement a intrusive linked-list:
__________________________________________________________
#include <cstddef>
#include <cassert>
#include <iostream>
template<typename T>
struct slink
{
T* m_next;
};
template<typename T, slink<T> T::*T_link>
class sl_iter
{
T* m_cur;
public:
sl_iter(T* cur) : m_cur(cur) { }
T* operator ->()
{
assert(m_cur);
return m_cur;
}
T* get()
{
return m_cur;
}
bool end()
{
return (! m_cur) ? true : false;
}
sl_iter& operator ++()
{
m_cur = (m_cur) ? (m_cur->*T_link).m_next : NULL;
return *this;
}
};
template<typename T, slink<T> T::*T_link>
class slist
{
T* m_head;
public:
typedef sl_iter<T, T_link> sl_iter_type;
slist(T* head = NULL) : m_head(head) {}
public:
T* head()
{
return m_head;
}
void push(T* object)
{
(object->*T_link).m_next = m_head;
m_head = object;
}
T* pop()
{
T* head = m_head;
if (head) m_head = (head->*T_link).m_next;
return head;
}
};
struct foo
{
typedef slink<foo> slink_type;
unsigned m_id;
slink_type m_slink1;
slink_type m_slink2;
typedef slist<foo, &foo::m_slink1> slist1_type;
typedef slist<foo, &foo::m_slink2> slist2_type;
};
int
main()
{
{
foo f1, f2, f3;
f1.m_id = 1; f2.m_id = 2; f3.m_id = 3;
foo::slist1_type sl1;
foo::slist2_type sl2;
sl1.push(&f1);
sl1.push(&f2);
sl1.push(&f3);
sl2.push(&f3);
sl2.push(&f2);
sl2.push(&f1);
for (foo::slist1_type::sl_iter_type i(sl1.head());
! i.end();
++i)
{
std::cout << "("
<< i.get()
<< ")->foo("
<< i->m_id << ")"
<< std::endl;
}
for (foo::slist2_type::sl_iter_type i(sl2.head());
! i.end();
++i)
{
std::cout << "("
<< i.get()
<< ")->foo("
<< i->m_id << ")"
<< std::endl;
}
}
return 0;
}
__________________________________________________________
AFAICT, everything should be Kosher.
implement a intrusive linked-list:
__________________________________________________________
#include <cstddef>
#include <cassert>
#include <iostream>
template<typename T>
struct slink
{
T* m_next;
};
template<typename T, slink<T> T::*T_link>
class sl_iter
{
T* m_cur;
public:
sl_iter(T* cur) : m_cur(cur) { }
T* operator ->()
{
assert(m_cur);
return m_cur;
}
T* get()
{
return m_cur;
}
bool end()
{
return (! m_cur) ? true : false;
}
sl_iter& operator ++()
{
m_cur = (m_cur) ? (m_cur->*T_link).m_next : NULL;
return *this;
}
};
template<typename T, slink<T> T::*T_link>
class slist
{
T* m_head;
public:
typedef sl_iter<T, T_link> sl_iter_type;
slist(T* head = NULL) : m_head(head) {}
public:
T* head()
{
return m_head;
}
void push(T* object)
{
(object->*T_link).m_next = m_head;
m_head = object;
}
T* pop()
{
T* head = m_head;
if (head) m_head = (head->*T_link).m_next;
return head;
}
};
struct foo
{
typedef slink<foo> slink_type;
unsigned m_id;
slink_type m_slink1;
slink_type m_slink2;
typedef slist<foo, &foo::m_slink1> slist1_type;
typedef slist<foo, &foo::m_slink2> slist2_type;
};
int
main()
{
{
foo f1, f2, f3;
f1.m_id = 1; f2.m_id = 2; f3.m_id = 3;
foo::slist1_type sl1;
foo::slist2_type sl2;
sl1.push(&f1);
sl1.push(&f2);
sl1.push(&f3);
sl2.push(&f3);
sl2.push(&f2);
sl2.push(&f1);
for (foo::slist1_type::sl_iter_type i(sl1.head());
! i.end();
++i)
{
std::cout << "("
<< i.get()
<< ")->foo("
<< i->m_id << ")"
<< std::endl;
}
for (foo::slist2_type::sl_iter_type i(sl2.head());
! i.end();
++i)
{
std::cout << "("
<< i.get()
<< ")->foo("
<< i->m_id << ")"
<< std::endl;
}
}
return 0;
}
__________________________________________________________
AFAICT, everything should be Kosher.