> If the link pointer is part of the data structure, then > it's only one extra pointer in the same memory location as the data.... plus the linking code that you would have to implement all over again. You could make the list template require a 'next' member in the data type, but that might not be acceptable.
> The main problem with an array is that it is not dynamic. > If you wantto remove an item from the middle, > you have to copy all the other data backwards
Yes, that is true. However, most types of data do not require random element removal very often. If you need to add and remove elements in completely random locations and it is your performance bottleneck, then I would concede that you would be better off with a linked list. I would also suggest that you rethink your design. In most cases, however, addition and removal happen much less often than reading, and optimizing for reading will make your code faster. Try it and profile. You might be surprized just how little insert/remove matters.
> An arbitrary number of items can be added to the > end of it which you cannot do with an array.
You can do paged allocation, which will create less memory fragmentation than a linked list. STL does that for its vector template. If you keep reusing your array for lists of similar length, you gain two more advantages: no memory allocation at all for the steady state condition and very good cache utilization. These are things that are very important if you use this data in a tight loop and you will never be able to get the same performance with a linked list.
You can use paged allocation to grow the array, as you add the items. If you use realloc, there will be no copying involved, as it will simply extend your allocated block. See vector template implementation in http://sourceforge.net/projects/ustl for an example.
> So I put them in front of a white board and ask > them to show me the code to add an item to a > singly linked list, using the language of their choice.
Why would anyone ever use a linked list? They cause memory fragmentation, screw up your cache, add two pointers of overhead per item (quite possibly in a different memory location from the data), are slow to access thanks to all that dereferencing, and require ugly special casing code for the head (unless you are smart or have read Knuth and remember the circular list trick). Using an array is almost always a better solution, so you better profile and make damn sure the linked list is faster before you even consider putting it in your code.
> Can you pass this test? Post a link to your resume, > we are hiring in the East Bay, California. C#.
So you are a company that has C# code with linked lists in it? And it looks like you do it MANUALLY EVERY TIME! (or else why ask the question?) And you want my resume? Not bloody likely!
Obviously, you are not going to be convinced until I go and actually write a C++ compiler. Of course, that is the only answer possible these days to any software problem. Linux has no desktop? Quit complaining and go write one! Linux has no games? Shut up and go write one! C++ compilers are impossible? Why don't you go and write one! Yes, proof by accomplishment really is incontrovertible, but it is sad that it is the only one left. Sure I can write a few good programs, and I am, but it will take many years for me to write everything, even if I were interested enough to try. What I wonder, is why am I the only one charged with this task? Why doesn't somebody else say "It can be done!" and do it? Where are the confident people who do instead of profess the impossibility of doing? Where will the world go if it is overrun by the latter?
Bullshit. I can explain every feature of C to you in a few hours. C++ is no harder. The problem is not learning the language, it is learning to work with the computer in the first place. What you need to learn is how to design programs; a skill that has very little to do with what language you use. Learn to extract the problem domain and to implement it in a minimal interface. Learn to make interfaces in such a way as to be used by writing as little code as possible. Learn to see similarities in cut-n-paste code and to abstract them into a more generic function. Learn to see similarities in function sets and combine them into a class. Learn to see similarities between classes and generalize them into templates. And then look at the assembly output and learn how to make all your syntactic sugar collapse into a few instructions in all the right places. That is what takes a long time to learn, and if you do not know these things, you will write lousy code, whether in C++, Java, or C.
> If it takes half a year to write a working > okayish C compiler and five years to write a C++ compiler
You obviously have never written a compiler. C++ features are not that difficult to implement. I have written simple compilers (no, not for C++) that supported inheritance, encapsulation, and templates, in a few weeks. Optimization of output code is hard. Parsing language features is not.
> If C++ compiler sucks, the problem isn't entirely in the vendor.
Of course it is in the vendor. They wrote it, so if it sucks (i.e. does not conform to the standard), then it is nobody's fault but theirs. The ANSI standard has been around since '89 or so, and if the vendor has not fixed the compiler, it is most likely because they are not willing to pay someone to do it.
> Well, if it's non-virtual, then it isn't polymorphic is it?
Then it is compile-time polymorphic. It's something you would use in a template, for instance. I am simply addressing your original complaint of a store becoming a virtual function call. If you don't need it, don't do it! I was saying that the capability is there if you need it, and if you look at the kernel code you will find plenty of places that do. Yes, you incur overhead, but lots of times it pays for itself in cleaner design, and if you don't do it in a time-critical loop (there aren't as many of those as you think), nobody will notice a few extra cycles. As for compile-time class selection in a template, it is much better than cut-n-paste code (or macros, for that matter) that you would have to do in C.
> So, there's no problem with C++ so long as we > assume all the tools and users are perfect. > That's what you said, right?
No language can force a programmer to write good code. If you are a bad programmer, you will write equally bad code in C++, C, Java, Python, Ruby, Eiffel, Perl, Prolog, Lisp, or BASIC. A language may prevent use of certain "dangerous" things, like memory allocation, but such hacks only convert the bugs from one type to another. In Java, for example, you never have invalid pointers, but you have memory leaks instead; you have bounds checking which cause an exception if you overrun your array, but to a user an exception creates an outcome identical to a crash. Good code requires good programmers. Period. So yes, that's what I said.
Like I said, inline functions in C is a gcc extension, and is not portable. You could do it by declaring the function as static, in which case the compiler will almost always expand it inline, but that only works in one file, so mostly you will see things like that done with macros.
This will not catch stupid type mistakes like this: int* reg; regs = GetRegs(); ENABLE_FEATURE_X(reg); Type safety is a good thing. It saves you time by not letting you do with your types what you did not want to do with them. Macros have other problems, like not being visible in the debugger, unlike inline functions which can be stepped through.
These are only minor annoyances though compared with the scoping problem. In C++ CDevice::EnableFeatureX is clearly associated with CDevice, which represents a specific interface. All functions in CDevice compose that interface and are naturally aggregated in both space and scope. The C function in your example is an algorithm operating on SOMEREG_ptr*, which gives the developer no clue as to what interface this function belongs. A C interface simply can not look as coherent as a C++ class because the language can not encode that type of information. It also can not encapsulate information about the device within itself. enableFeatureX depends on the internal structure of SOMEREG_ptr, which for this reason must remain exposed. A C++ class can keep internals to itself and expose only the functionality that is needed outside, allowing change of internal implementation without modification of client code. Of course, this is not a limitation for small programs, such as most UNIX command line stuff like ls, mv, rm, etc., but it becomes a larger problem the larger your project grows, possibly becoming a tangled mess of components reaching into each other where they are not supposed to.
> The point is that people like you delight in > creating gadget interfaces, and avoid minimal, > repetative, direct programming designs.
A good "gadget" interface will produce your "minimal, repetetive, and direct" code, but with less effort. More abstraction does not necessarily lead to more code. Consider the following:
CDevice dev (GetDeviceRegs()); dev.EnableFeatureX();
This code will compile to a copy to a local variable (the constructor), an OR and a memory store, just as your original code did. There is absolutely no extra overhead. But now you see exactly what the code wants to do. BIT_A and BIT_B do not necessarily mean much, and you would have to add comments all over the place. In C++ the code can be much more self-explanatory, which means that maintainers would not have to dig through documentation as much. And then consider what happens if you have to add |BIT_C to EnableFeatureX. If you wrote this in C (which normally does not support inline functions), you would have to change every occurence of setting BIT_A and BIT_B. In the C++ implementation you change it in one place and you are done.
> This will compile to an indirect-branch (to figure out which class to use at run-time)
Not necessarily. If you implement your call as virtual and give your function a class pointer, then of course that is what will happen. In C you would have to do the same thing for similar functionality. But you do not have to do this. An non-virtual inline operator= will always produce a simple or and store, just like the original C code. The difference is that you have now abstracted the interface from implementation and can substitute another implementation without changing the original code. That is what C++ is all about and it is an enormous benefit if you ever need to modify your code.
>// C++, is this really better? > Register_set regset(base_address); > regset.write(SOMEREG_OFFSET , Register_set::BIT_A | Register_set::BIT_B);
Only a complete novice would write code like this. Your code setting *SOMEREG_ptr = BIT_A | BIT_B will work just fine in C++ too. In fact, you could transparently support multiple types of registers by overloading operator= of SOMEREG_ptr, which could be a polymorphic class. And if you think that is going to bloat your code, you obviously have never looked at the output of a good compiler like gcc. A good C++ design is FAR more readable than any C hack you can come up with.
> Typical compilers for DSP's lag the C++ standard by 10 years
That is the problem of your compiler, not the language. Stop bashing C++ when you should be blaming your vendor for not being able to write a decent compiler, or even port gcc to their platform.
> I'll have to wear a lead apron and protective > glasses when I turn on my new computer?
Geeks have no need to wear a lead apron, for reasons that should be obvious after a moment's reflection. And as for protective glasses, well, most of us already wear them...
> In the binary system, one of the stars 'gave too > much' (Reuters) of its own resources to its > partner white dwarf star, resulting in a breakdown > of nuclear fusion, thus producing this 'dead' entity.
A good example to illustrate the evil of altruism.
For a really good grilling the candidates should field questions from first grade kids, and be required to answer each one. Let's see how well they stand up under the constant stream of "Why?", "I don't get it", "Is this some grownup thing?", "Why?", "What's a 'recovery'?", "Why?", etc. Especially if "because I said so" is not considered to be an acceptable answer.
> Who in their right minds is going to buy a new PC and put such an old OS on it?
To run DOS games, of course! How else will you be able to run such great oldies like Civilization, Dark Sun, or even Leisure Suit Larry. Then there is Space Quest, Mega Traveller II, Life and Death, and many other titles, which simply do not exist on any other platform. Windows games these days are mostly of the 3D FPS kind and are rather boring. Linux has no games at all, except for those that can run in an emulator (if you can get the emulator to run, that is). So what's a gamer to do? Run DOS, of course!
> - More than double the payroll tax, from 15.3% to 32% of wages
And by doing so close half the businesses in the country? What president is dumb enough to do that?
> - Raise income taxes by two thirds
This may be a good time to remember why we declared independence from England. As I recall, the high tax rate was one of the reasons. "High" was something like 5% back then...
> - Cut Social Security and Medicare benefits by 45%
Do you realize how old most people who vote are? Doing this would automatically prevent reelection of everyone who votes for it.
> - Eliminate all "discretionary" spending
If you look at other debt-laden governments in the world (like Argentina, for instance), you will see that these "options" are not even considered. When the debt can not be raised any further, the government simply defaults on it, or prints more money. In either case the result is hyperinflation and immediate devaluation of the currency, but nobody seems to know that until it happens "entirely without warning".
Slashdot Mirror
> But there are ways around memory fragmentation.
... plus the linking code that you would have to implement all over again. You could make the list template require a 'next' member in the data type, but that might not be acceptable.
Like what?
> If the link pointer is part of the data structure, then
> it's only one extra pointer in the same memory location as the data.
> The main problem with an array is that it is not dynamic.
> If you wantto remove an item from the middle,
> you have to copy all the other data backwards
Yes, that is true. However, most types of data do not require random element removal very often. If you need to add and remove elements in completely random locations and it is your performance bottleneck, then I would concede that you would be better off with a linked list. I would also suggest that you rethink your design. In most cases, however, addition and removal happen much less often than reading, and optimizing for reading will make your code faster. Try it and profile. You might be surprized just how little insert/remove matters.
> An arbitrary number of items can be added to the
> end of it which you cannot do with an array.
You can do paged allocation, which will create less memory fragmentation than a linked list. STL does that for its vector template. If you keep reusing your array for lists of similar length, you gain two more advantages: no memory allocation at all for the steady state condition and very good cache utilization. These are things that are very important if you use this data in a tight loop and you will never be able to get the same performance with a linked list.
> Now tell me, how big should my array be?
You can use paged allocation to grow the array, as you add the items. If you use realloc, there will be no copying involved, as it will simply extend your allocated block. See vector template implementation in http://sourceforge.net/projects/ustl for an example.
"If you can do it, it ain't braggin"
> 24/7 support, Monday-Friday 8am to 8pm.
There's a legend at Microsoft of an employee who bumped into Bill Gates in the parking lot.
"Going home already?" Asks Bill.
"Sure. I've done my 12 hours."
"Ah, so you only work half-time?"
> So I put them in front of a white board and ask
> them to show me the code to add an item to a
> singly linked list, using the language of their choice.
Why would anyone ever use a linked list? They cause memory fragmentation, screw up your cache, add two pointers of overhead per item (quite possibly in a different memory location from the data), are slow to access thanks to all that dereferencing, and require ugly special casing code for the head (unless you are smart or have read Knuth and remember the circular list trick). Using an array is almost always a better solution, so you better profile and make damn sure the linked list is faster before you even consider putting it in your code.
> Can you pass this test? Post a link to your resume,
> we are hiring in the East Bay, California. C#.
So you are a company that has C# code with linked lists in it? And it looks like you do it MANUALLY EVERY TIME! (or else why ask the question?) And you want my resume? Not bloody likely!
> when do the nerds/geeks worry about clothing style?
When picking up chicks, of course. Uh... On the internet.
Obviously, you are not going to be convinced until I go and actually write a C++ compiler. Of course, that is the only answer possible these days to any software problem. Linux has no desktop? Quit complaining and go write one! Linux has no games? Shut up and go write one! C++ compilers are impossible? Why don't you go and write one! Yes, proof by accomplishment really is incontrovertible, but it is sad that it is the only one left. Sure I can write a few good programs, and I am, but it will take many years for me to write everything, even if I were interested enough to try. What I wonder, is why am I the only one charged with this task? Why doesn't somebody else say "It can be done!" and do it? Where are the confident people who do instead of profess the impossibility of doing? Where will the world go if it is overrun by the latter?
> it takes 1 year to learn every feature of C
Bullshit. I can explain every feature of C to you in a few hours. C++ is no harder. The problem is not learning the language, it is learning to work with the computer in the first place. What you need to learn is how to design programs; a skill that has very little to do with what language you use. Learn to extract the problem domain and to implement it in a minimal interface. Learn to make interfaces in such a way as to be used by writing as little code as possible. Learn to see similarities in cut-n-paste code and to abstract them into a more generic function. Learn to see similarities in function sets and combine them into a class. Learn to see similarities between classes and generalize them into templates. And then look at the assembly output and learn how to make all your syntactic sugar collapse into a few instructions in all the right places. That is what takes a long time to learn, and if you do not know these things, you will write lousy code, whether in C++, Java, or C.
> If it takes half a year to write a working
> okayish C compiler and five years to write a C++ compiler
You obviously have never written a compiler. C++ features are not that difficult to implement. I have written simple compilers (no, not for C++) that supported inheritance, encapsulation, and templates, in a few weeks. Optimization of output code is hard. Parsing language features is not.
> If C++ compiler sucks, the problem isn't entirely in the vendor.
Of course it is in the vendor. They wrote it, so if it sucks (i.e. does not conform to the standard), then it is nobody's fault but theirs. The ANSI standard has been around since '89 or so, and if the vendor has not fixed the compiler, it is most likely because they are not willing to pay someone to do it.
> Well, if it's non-virtual, then it isn't polymorphic is it?
Then it is compile-time polymorphic. It's something you would use in a template, for instance. I am simply addressing your original complaint of a store becoming a virtual function call. If you don't need it, don't do it! I was saying that the capability is there if you need it, and if you look at the kernel code you will find plenty of places that do. Yes, you incur overhead, but lots of times it pays for itself in cleaner design, and if you don't do it in a time-critical loop (there aren't as many of those as you think), nobody will notice a few extra cycles. As for compile-time class selection in a template, it is much better than cut-n-paste code (or macros, for that matter) that you would have to do in C.
> So, there's no problem with C++ so long as we
> assume all the tools and users are perfect.
> That's what you said, right?
No language can force a programmer to write good code. If you are a bad programmer, you will write equally bad code in C++, C, Java, Python, Ruby, Eiffel, Perl, Prolog, Lisp, or BASIC. A language may prevent use of certain "dangerous" things, like memory allocation, but such hacks only convert the bugs from one type to another. In Java, for example, you never have invalid pointers, but you have memory leaks instead; you have bounds checking which cause an exception if you overrun your array, but to a user an exception creates an outcome identical to a crash. Good code requires good programmers. Period. So yes, that's what I said.
> Umm, huh?
> inline void enableFeatureX(SOMEREG_ptr* pRegs)
Like I said, inline functions in C is a gcc extension, and is not portable. You could do it by declaring the function as static, in which case the compiler will almost always expand it inline, but that only works in one file, so mostly you will see things like that done with macros.
> #define ENABLE_FEATURE_X(regs) *(regs) = BIT_A | BIT_B;
This will not catch stupid type mistakes like this:
int* reg;
regs = GetRegs();
ENABLE_FEATURE_X(reg);
Type safety is a good thing. It saves you time by not letting you do with your types what you did not want to do with them. Macros have other problems, like not being visible in the debugger, unlike inline functions which can be stepped through.
These are only minor annoyances though compared with the scoping problem. In C++ CDevice::EnableFeatureX is clearly associated with CDevice, which represents a specific interface. All functions in CDevice compose that interface and are naturally aggregated in both space and scope. The C function in your example is an algorithm operating on SOMEREG_ptr*, which gives the developer no clue as to what interface this function belongs. A C interface simply can not look as coherent as a C++ class because the language can not encode that type of information. It also can not encapsulate information about the device within itself. enableFeatureX depends on the internal structure of SOMEREG_ptr, which for this reason must remain exposed. A C++ class can keep internals to itself and expose only the functionality that is needed outside, allowing change of internal implementation without modification of client code. Of course, this is not a limitation for small programs, such as most UNIX command line stuff like ls, mv, rm, etc., but it becomes a larger problem the larger your project grows, possibly becoming a tangled mess of components reaching into each other where they are not supposed to.
> The point is that people like you delight in
> creating gadget interfaces, and avoid minimal,
> repetative, direct programming designs.
A good "gadget" interface will produce your "minimal, repetetive, and direct" code, but with less effort. More abstraction does not necessarily lead to more code. Consider the following:
class CDevice {
public:
CDevice (SOMEREG_ptr* pRegs) : m_pRegs(pRegs){}
inline void EnableFeatureX (void) { *m_pRegs = BIT_A | BIT_B; }
private:
SOMEREG_ptr m_pRegs;
};
CDevice dev (GetDeviceRegs());
dev.EnableFeatureX();
This code will compile to a copy to a local variable (the constructor), an OR and a memory store, just as your original code did. There is absolutely no extra overhead. But now you see exactly what the code wants to do. BIT_A and BIT_B do not necessarily mean much, and you would have to add comments all over the place. In C++ the code can be much more self-explanatory, which means that maintainers would not have to dig through documentation as much. And then consider what happens if you have to add |BIT_C to EnableFeatureX. If you wrote this in C (which normally does not support inline functions), you would have to change every occurence of setting BIT_A and BIT_B. In the C++ implementation you change it in one place and you are done.
> This will compile to an indirect-branch (to figure out which class to use at run-time)
Not necessarily. If you implement your call as virtual and give your function a class pointer, then of course that is what will happen. In C you would have to do the same thing for similar functionality. But you do not have to do this. An non-virtual inline operator= will always produce a simple or and store, just like the original C code. The difference is that you have now abstracted the interface from implementation and can substitute another implementation without changing the original code. That is what C++ is all about and it is an enormous benefit if you ever need to modify your code.
> // C++, is this really better?
> Register_set regset(base_address);
> regset.write(SOMEREG_OFFSET , Register_set::BIT_A | Register_set::BIT_B);
Only a complete novice would write code like this. Your code setting *SOMEREG_ptr = BIT_A | BIT_B will work just fine in C++ too. In fact, you could transparently support multiple types of registers by overloading operator= of SOMEREG_ptr, which could be a polymorphic class. And if you think that is going to bloat your code, you obviously have never looked at the output of a good compiler like gcc. A good C++ design is FAR more readable than any C hack you can come up with.
> Typical compilers for DSP's lag the C++ standard by 10 years
That is the problem of your compiler, not the language. Stop bashing C++ when you should be blaming your vendor for not being able to write a decent compiler, or even port gcc to their platform.
A war on X would be a great idea. Let's destroy all those ugly C interfaces; they are all just so 1986.
> I'll have to wear a lead apron and protective
> glasses when I turn on my new computer?
Geeks have no need to wear a lead apron, for reasons that should be obvious after a moment's reflection. And as for protective glasses, well, most of us already wear them...
> In the binary system, one of the stars 'gave too
> much' (Reuters) of its own resources to its
> partner white dwarf star, resulting in a breakdown
> of nuclear fusion, thus producing this 'dead' entity.
A good example to illustrate the evil of altruism.
Only have 3.5 minutes to do it ;)
> Now there won't be any place where I can go to avoid the tourists.
Try South Dakota
For a really good grilling the candidates should field questions from first grade kids, and be required to answer each one. Let's see how well they stand up under the constant stream of "Why?", "I don't get it", "Is this some grownup thing?", "Why?", "What's a 'recovery'?", "Why?", etc. Especially if "because I said so" is not considered to be an acceptable answer.
Now we know how those "canals" got there :)
> Who in their right minds is going to buy a new PC and put such an old OS on it?
To run DOS games, of course! How else will you be able to run such great oldies like Civilization, Dark Sun, or even Leisure Suit Larry. Then there is Space Quest, Mega Traveller II, Life and Death, and many other titles, which simply do not exist on any other platform. Windows games these days are mostly of the 3D FPS kind and are rather boring. Linux has no games at all, except for those that can run in an emulator (if you can get the emulator to run, that is). So what's a gamer to do? Run DOS, of course!
> - More than double the payroll tax, from 15.3% to 32% of wages
And by doing so close half the businesses in the country? What president is dumb enough to do that?
> - Raise income taxes by two thirds
This may be a good time to remember why we declared independence from England. As I recall, the high tax rate was one of the reasons. "High" was something like 5% back then...
> - Cut Social Security and Medicare benefits by 45%
Do you realize how old most people who vote are? Doing this would automatically prevent reelection of everyone who votes for it.
> - Eliminate all "discretionary" spending
If you look at other debt-laden governments in the world (like Argentina, for instance), you will see that these "options" are not even considered. When the debt can not be raised any further, the government simply defaults on it, or prints more money. In either case the result is hyperinflation and immediate devaluation of the currency, but nobody seems to know that until it happens "entirely without warning".
> proble#$#$%$%$#%@#%%@$%@#$%REF$%$F^............NO CARRIER.
:)
It's so nice to see that not everyone has succumbed to broadband arrogance
Have you heard of that new drug called "Snow Crash"?