[9335] in The GTK GIMP ToolKit mailing list archive
[gtk-list] Re: g_list_append is O(n^2)
daemon@ATHENA.MIT.EDU (Federico Mena Quintero)
Thu Oct 15 12:29:52 1998
Date: Thu, 15 Oct 1998 12:29:45 -0400
From: Federico Mena Quintero <federico@nuclecu.unam.mx>
To: gtk-list@redhat.com
In-reply-to: <19981015132117.A20242@haegar.physiol.med.tu-muenchen.de>
(message from Robert Wilhelm on Thu, 15 Oct 1998 13:21:17 +0200)
Resent-From: gtk-list@redhat.com
Reply-To: gtk-list@redhat.com
> sorry for the confusion. STL has constant time at least for push_back()
> and push_front(), while glib has constant time for g_list_prepend()
> but linear time for g_list_append(). It has to go through the whole
> list in g_list_last().
Glib lists work pretty much like Lisp lists.
Applications which require O(1) append/prepend times use the "keep
pointers to the list start and end" method -- you can look at the
GnomeCanvas, GtkCList, etc.
Federico
--
To unsubscribe: mail -s unsubscribe gtk-list-request@redhat.com < /dev/null
