STL / Custom Linked List
-
Which is better writing my own custom Linked List class or using STL? Which is better not just from the point of speed, but also memory usage?
-
Which is better writing my own custom Linked List class or using STL? Which is better not just from the point of speed, but also memory usage?
I don't know the answer, however I'm rather pragmatic on such issues: what makes you think your implementation would be better in some way (speed, memory, whatever)? :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
-
I don't know the answer, however I'm rather pragmatic on such issues: what makes you think your implementation would be better in some way (speed, memory, whatever)? :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
Big-O-Notation!?
-
Big-O-Notation!?
That does not even start to look like the answer to my question. If you think you can design and build a better linked list, and can afford to spend the time to do it right, then do it, debug it, test it, document it, and compare it to existing implementations. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
-
Which is better writing my own custom Linked List class or using STL? Which is better not just from the point of speed, but also memory usage?
Fareed Rizkalla wrote:
Which is better writing my own custom Linked List class or using STL?
unless proven otherwise : STL.
Fareed Rizkalla wrote:
Which is better not just from the point of speed, but also memory usage?
unless proven otherwise : STL, and if you really need to tweak something you can try to create and use your own allocator; but the time and effort needed for that is not that worthwhile. BUT if you have a very peculiar application that needs very customized linked list and does not care about portability, accessibility, expendability, write your own. Also, if you ever want to do some performance analysis of STL, remember to do it in RELEASE mode, the debug mode is considerably slower than release mode.
Watched code never compiles.
-
Which is better writing my own custom Linked List class or using STL? Which is better not just from the point of speed, but also memory usage?
Custom lists are typically deployed when object need themselves to form a chain (objects that knows about their containment and know who is before and after. For this STL has no solution) Where no such need exist, a double linked list -however you implement it- can do nothing more that what
std::listdo. The algorithms to manage links are the same from about a century, and are nothing more that a swap between four pointers. The only advantage happens when you can code and test them faster then learning how STL methods and concept are defined. About portability ... Sorry but must disagree with many previous posts. Simply, I cannot understand how a self contained code that does nothing more pointer assignment, new and delete, cannot be portable. It can be buggy, but not unportable. Who speaks about "portability" is just doing "marketing lies" (and simply repeating acritically what read on STL books: The prove is that is using the exact same phrase -including adverbs and commas- everybody else sustaining the same thesis is using, so it's not his own original thought). The problem arise when your code need to interact with some other code doing his own implementation... and the two implementations conflict in prerequisite. But if normal good design rules are observed, I don't see that problem.2 bugs found. > recompile ... 65534 bugs found. :doh:
-
I don't know the answer, however I'm rather pragmatic on such issues: what makes you think your implementation would be better in some way (speed, memory, whatever)? :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
I have done this where each node is an element but the forward and back 'pointers' are offsets from the base address to a block of memory, rather than individual 'nodes' allocated from the current process heap. If you put this into a custom Win32 Heap, then the entire list deletes almost instantly! I am not sure that is the case even if you feed the STL a custom allocator - it still asks for a node one at a time? Anyways, that was done years before STL existed.
-
I have done this where each node is an element but the forward and back 'pointers' are offsets from the base address to a block of memory, rather than individual 'nodes' allocated from the current process heap. If you put this into a custom Win32 Heap, then the entire list deletes almost instantly! I am not sure that is the case even if you feed the STL a custom allocator - it still asks for a node one at a time? Anyways, that was done years before STL existed.
I agree there can be circumstances where a specialized implementation (or even an entirely different data structure, e.g. some kind of tree) is (much) better; however the OP did not give any hint in that sense. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.