me22 wrote:
On 12/9/06, Mathias Gaunard <mathias.gaunard@etu.u-bordeaux1.fr> wrote:
I think you should try to model the STL. Indeed, containers such as std::list provide a constant time size function. ilist should do the same.
I'm fairly certain that this does not need to be the case.
There was a thread a while back about going though the sources to look for uses of list::size exactly because it could be O(n) to ensure that there was always an O(1) empty-using function as an alternative to size.
I think that Howard Hinnant has a very good paper about this, titled "On std::list::size": http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html He suggests adding a new splice overload taking the number of elements between two iterators to obtain a O(1) size with lists with O(1) size. I've added that overload both to the intrusive singly and doubly linked lists. Historically, SGI STL had a O(N) size std::list. In Interprocess, since I took SGI implementation as my base implementation I had O(N) list. The last version has O(1) size. I think that most users expect list::size() to be O(1) because they think that otherwise, the operation wouldn't be there, just like std::list has no operator[](). All other containers have O(1) size, so is reasonable to expect O(1) size in list. However, with intrusive containers I think that both possibilities should be provided. In most cases, if the user uses an intrusive list to store his objects, he might expect the same behavior than std::list and Windows users (surely using Dinkumware STL) will expect O(1) size. On the other hand, if people use list::splice as a basic operation, they want to obtain O(1) splice. There are more examples of more efficient operations with O(N) size: for an intrusive list "erase(iterator, iterator)" O(1) if we have O(N) size. There is another reason to have a O(N) size() intrusive list: space overhead. If a boost user wants to implement a TR1 unordered_map, a typical implementation is to have bucket array and each bucket is a singly (maybe doubly) linked list of values. The library author does not need islist::size() for nothing, but an empty circular singly linked list can be implemented with just a pointer pointing to itself. Since the hashmap's load factor is normally 1.0, this means that for every inserted object, there is a bucket. Adding the size member duplicates the size of the bucket, and this space overhead is noticeable. If the programmer has an option to have a O(N) size, he reduces the size of a bucket to just one pointer. If we have a "unordered_set<int>" with a load factor = 1.0, and a space-friendly allocator (a node allocator), there is a ~25% size overhead if we use a O(1) size intrusive singly linked list: every node has 2 words (1 word for every stored int, 1 word for the pointer used to implement the linked list) and every the bucket has two words (one for the pointer to implement the linked list and another word to store the size of the linked list). Original Intrusive library containers had O(N) size. Since I think that most users expect to have O(1) size, I've added that possibility. The default is to have O(N) size, but that, of course, can be changed, if people prefer O(1) size. Thanks for the comments, Ion