|
seiken posted:As Otto said, the fact that you don't care about the relative ordering of only red or only blue means this is an unstable sort. The fact that a simple linear-time algorithm exists is because you have exactly two different keys (red and blue). For three or more keys this won't work and you have to use a general n log n algorithm or radix sort or similar. It's somewhat common in parameterised computer science problems that the problem with K=2 is somehow fundamentally "much easier" than the problem for any greater K (see also SAT, graph colouring). I don't know if there's a name for that particular phenomenon, though. You can sort in O(n) for three keys - that's Dijkstra's dutch flag problem.
|
# ? Apr 9, 2014 18:13 |
|
|
# ? Jun 8, 2024 08:18 |
|
Subjunctive posted:Wrong getline. Yep, hence the comment about being sarcastic. I'm not a fan of C++'s IO APIs, I'd prefer standardising fopencookie and coming up with a better way to extend printf and scanf than this.
|
# ? Apr 9, 2014 18:21 |
|
Subjunctive posted:Only shrughes can settle this burning debate! This reminds me, Smokey the Bear was the laziest jackass who ever lived. "Only you can prevent forest fires." As opposed to the guy whose job it is to prevent forest fires.
|
# ? Apr 9, 2014 19:09 |
|
Zopotantor posted:Actually, the index type in C++ is ptrdiff_t (13.6.13). Touch. Edison was a dick posted:Yep, hence the comment about being sarcastic. I missed that as sarcasm. But there are no good I/O APIs. It may be impossible.
|
# ? Apr 9, 2014 20:52 |
|
ExcessBLarg! posted:What makes you think that shrughes thinks char is an unsigned type? what makes you think that i think that shrughes thinks that char is a unsigned type? makes u think
|
# ? Apr 9, 2014 21:01 |
|
Zopotantor posted:You can sort in O(n) for three keys - that's Dijkstra's dutch flag problem. You can sort in O(n lg k) for k known keys just by repeatedly dividing your key set in half. The standard Dutch flag solution is neat mostly because it does k=3 in (kindof) one pass, which also lets you divide your key set in thirds; none of this affects the asymptotic complexity, but it does help the practical performance. If, you know, you have to do this and for some reason it's so important to improve from O(n lg n) to O(n lg k) that it's worth implementing your own sort algorithm for it.
|
# ? Apr 10, 2014 00:58 |
|
Looks like I was talking poo poo then my bad
|
# ? Apr 10, 2014 02:14 |
|
I am basically trying to get an inherited class to call its overridden function on construction:code:
code:
Pontificating Ass fucked around with this message at 01:26 on Apr 11, 2014 |
# ? Apr 11, 2014 01:23 |
|
Basically, you can't do that.
|
# ? Apr 11, 2014 01:37 |
|
Well... C++ code:
Don't count on anything from Derived being initialized, but you can go ahead and use Base and Base_CRTP<Derived> stuff. If you're really crazy, you could probably initialize Derived members in Derived::foo(), but I'd look up in the standard whether or not that's undefined behavior first. The Laplace Demon fucked around with this message at 05:07 on Apr 11, 2014 |
# ? Apr 11, 2014 05:02 |
|
I think that's UB anyways; inside the base constructor, the object is not yet a derived, so you can't use a derived member.
|
# ? Apr 11, 2014 05:25 |
|
N3936 - 12.7/4 posted:Member functions, including virtual functions, can be called during construction or destruction. When a virtual function is called directly or indirectly from a constructor or from a destructor, including during the construction or destruction of the classs non-static data members, and the object to which the call applies is the object (call it x) under construction or destruction, the function called is the final overrider in the constructors or destructors class and not one overriding it in a more-derived class. If the virtual function call uses an explicit class member access and the object expression refers to the complete object of x or one of that objects base class subobjects but not x or one of its base class subobjects, the behavior is undefined. Emphasis mine. If I'm reading that and the rest of the surrounding standardese correctly, my statement from before stands. You can use Base and Base_CRTP<Derived> members without worrying about undefined behavior. I played around with some of the undefined behavior mentioned in the standard with g++ and clang++ (such as accessing Derived members from Derived::foo()), and neither of them emit any warnings or errors, so be careful. EDIT: That last sentence may be saying you should recast this within Derived::foo() back to Base_CRTP<Derived> when accessing those members from Base and Base_CRTP<Derived>. The Laplace Demon fucked around with this message at 06:02 on Apr 11, 2014 |
# ? Apr 11, 2014 05:56 |
|
It doesn't look like there's any reason for foo to be a virtual function in your example. So I think it's OK, but no matter how you do it, if you use uninitialised members you'll have a bad time. And it's kind of bad and weird design, just put the logic directly into the Derived constructor or use a factory or whatever other thing.
|
# ? Apr 11, 2014 11:18 |
|
heres a fun C thing for you guys:code:
However, when using < instead of <= it does stop (without doing the 100th of course) What's going on? Because I can't figure it out.
|
# ? Apr 11, 2014 23:56 |
So in an array with 100 elements, indexed from 0 to 99, both inclusive, what happens when you set element index 100? Because you do that. Answer: Undefined behavior Also your printf() call has more arguments than the string has format specifiers.
|
|
# ? Apr 12, 2014 00:02 |
|
Assigning to rooster[100][100] is undefined behavior, so that program is allowed to do whatever it wants. e:
|
# ? Apr 12, 2014 00:02 |
|
Also your compiler will warn about both of those issues.
|
# ? Apr 12, 2014 00:03 |
|
oh right, it makes an array with 100 elements, not until and including [100], thanks. Too much MATLAB recently has clouded my mind, sorry guys.
|
# ? Apr 12, 2014 00:06 |
|
It's totally defined behaviour. rooster[100] refers to the address 100 * sizeof int past rooster. The program has to store there. Which is almost certainly where i and j are, on the stack... Edit: what warning does the compiler emit? It's entirely legal to index an array beyond its declared size. You see it commonly in structures with variable-length components at the end. code:
Subjunctive fucked around with this message at 00:09 on Apr 12, 2014 |
# ? Apr 12, 2014 00:06 |
|
Accessing beyond the end of an array is only defined for flexible array members, which can only occur at the end of a struct.
|
# ? Apr 12, 2014 00:24 |
|
Subjunctive posted:It's totally defined behaviour. ... It's entirely legal to index an array beyond its declared size. Subjunctive posted:You see it commonly in structures with variable-length components at the end. I mean, your analysis of what's going on in The Belgian's case is probably accurate, but it's not well-defined behavior and the same program compiled with a different compiler or on a different platform may well behave differently.
|
# ? Apr 12, 2014 00:28 |
|
pseudorandom name posted:Accessing beyond the end of an array is only defined for flexible array members, which can only occur at the end of a struct. Ah, right. Though actually in this specific case it's defined, I believe: C99 sec 5.7 posted:If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. Edit: bleh, right, not to dereference. I'll get my coat. (I didn't mean to imply that the aliasing of i and j was defined, by any means.) Subjunctive fucked around with this message at 00:34 on Apr 12, 2014 |
# ? Apr 12, 2014 00:31 |
|
Is Visual Studio's type resolution in the C++ debugger just really buggy or am I missing some trick? I have some code where I can have a pointer to a value of a struct and can assign to properties of the struct, but if I set a breakpoint after that, the debugger has no idea that the type has actually been defined and I can't look at its contents. If I change the definition of the struct to extend an empty base struct, then it'll magically start working. If I then delete that extension and build, then it continues working even though the code is the same as what it was when it wasn't working. If I then rebuild and try again, it loses its marbles and forgets the type again. e: Apparently defining a local of that struct anywhere, or making a function that does nothing but call the destructor of that struct from a pointer, makes it work even with rebuild. OneEightHundred fucked around with this message at 06:22 on Apr 12, 2014 |
# ? Apr 12, 2014 05:13 |
|
The Laplace Demon posted:Emphasis mine. If I'm reading that and the rest of the surrounding standardese correctly, my statement from before stands. You can use Base and Base_CRTP<Derived> members without worrying about undefined behavior. No; "refer" here is about the dynamic identity of the subobject, and there's no way to juggle things to make this defined. You have an explicit class member access whose base is a subobject that is neither the subobject whose constructor is currently active nor one of its subobjects; the behavior is undefined. Even if there were a way to make this defined, it would still not be a good idea. You need to use two-phase initialization instead of trying to shoehorn everything into the constructor.
|
# ? Apr 12, 2014 06:21 |
|
I've just spent a week tracking down a nasty bug caused by a sort functor not having strict weak ordering. I think. The symptom was that a random element in a vector would become corrupted in certain rare circumstances. Memory that should contain integers would be filled with rubbish (usually strings used elsewhere in the programme). The sort functor itself was OK, but the getters used to obtain the value to sort by would quietly mutate global state and return a different value on the next comparison. On Monday I have to justify to management that this is what has been causing crashes in our product. I know this probably falls under the purview of undefined behaviour, but can anyone give a reasonable justification for why a dodgy sort functor would blat over memory with garbage? Incidentally, praise be to -D_GLIBCXX_DEBUG
|
# ? Apr 13, 2014 10:44 |
|
danishcake posted:I've just spent a week tracking down a nasty bug caused by a sort functor not having strict weak ordering. I think. why are you trying to sort values that give different orderings at different points in time
|
# ? Apr 13, 2014 15:27 |
|
danishcake posted:I've just spent a week tracking down a nasty bug caused by a sort functor not having strict weak ordering. I think. This doesn't make a whole lot of sense. You seem to be dancing around two explanations for the problem (sort function not strict weak ordered and getters mutating global state (WTF?)) and "certain rare circumstances" is pretty dodgy. I would not accept your explanation if I were your manager without doing further investigation.
|
# ? Apr 13, 2014 16:28 |
|
It's probably best explained with a chunk of pseudocode.code:
The 'in rare circumstances' bit is because the estimate would normally converge within one iteration for almost the entire range of inputs, and thus hide the problem. The fix I've bunged in has been to ensure the 'X' is stored by the Widget class so it can be sorted on directly without all the recalculation nonsense. The code is not nice, but what I was really after was some reassurance that breaking strict weak ordering could cause garbage to end up in my vector.
|
# ? Apr 13, 2014 17:13 |
|
danishcake posted:what I was really after was some reassurance that breaking strict weak ordering could cause garbage to end up in my vector. No, it cannot. Breaking the ordering constraint will cause the sort to produce out-of-order results, but it will not cause actual corruption of the elements in the vector. Something else was going on.
|
# ? Apr 13, 2014 17:17 |
|
ShoulderDaemon posted:No, it cannot. Breaking the ordering constraint will cause the sort to produce out-of-order results, but it will not cause actual corruption of the elements in the vector. Something else was going on. well never say never. could the people who sorted based on a changing value also implement a sort that causes data corruption? who knows! anyways, have you shown that before the sort the data is clean and after the sort data is corrupted? then you might have an argument after you use valgrind/gdb to investigate what that line of code is doing. if its not w/in the sort itself but only when elements aren't sorted correctly, then you might want to ask what is depending on this data being sorted correctly? also, you have data in a place that it shouldn't be. How does that happen? You are either treating memory which isn't a Widget as a Widget or you've defined a bit of memory as a Widget but failed to initialize it correctly.
|
# ? Apr 13, 2014 17:50 |
|
It's a standard std::sort. I've definitely tracked it down to the sort, with exactly the technique you mentioned (eg a SanityCheck() on the vector before and after the sort). As I've been compiling with -D_GLIBCXX_DEBUG the std::sort spits out "attempt to decrement a dereferenceable (start-of-sequence) iterator" Investigating this I found the strict weak ordering thing, and this Stack Overflow post that seemed to confirm it, but without any detail. Googling a little more now, it appears it's a thing that older versions of GCC (4.4 in my case) could be persuaded to do. http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59391
|
# ? Apr 13, 2014 18:30 |
|
Ah, goons, always ready to confidently pile on and shout down the results of somebody else's solid debugging, backed only by some logical assumptions about what the worst case behavior could possibly be. The answer is that C++ standard library writers all have their heads up their asses. You and I might sit here and think, "I sort a lot of stuff, and sometimes that stuff makes for a pretty big, complicated type, and sometimes that stuff is being compared with a pretty sophisticated and expensive comparison function." And after we thought that, we might go on to think, "It'd be awfully nice if algorithm writers tried to minimize the number of comparisons they do." But that's because we don't have our heads up our asses. When you're a C++ standard library writer, to a close approximation you are always thinking about iterators. There's this whole hierarchy of iterators, and the entire library specification is shot through with statements about what kind of iterator such-and-such algorithm takes and such-and-such data structures uses, and a lot of data structures layer even more requirements on top of that about stability and so on. And you've written some damned complicated iterators in your time, and you know that sometimes they're really expensive to copy, or to compare, but most of all you've gotten into the mindset of always avoiding doing unnecessary operations with iterators in your generic code because that might unnecessarily or illegally! restrict the kind of iterator you can use there. Whereas you and I whom we are currently assuming, for the sake of argument, do not have our heads up our asses have probably never even considered sorting any data structure whose iterators aren't basically pointers, and are therefore super cheap to copy and compare and so on. And the result is that library writers sit down to do simple operations like partitioning the data structure on a pivot, and they write stuff like this (from libstdc++): C++ code:
So no, the idea that a bad comparator could cause random writes into memory is not all that strange, because C++ library writers all have their heads up their asses.
|
# ? Apr 13, 2014 20:14 |
|
rjmccall posted:Ah, goons, always ready to confidently pile on and shout down the results of somebody else's solid debugging, backed only by some logical assumptions about what the worst case behavior could possibly be. tbf i felt p bad bout it. i think i wouldve been less of a jerk if he had mentioned the scope of global mutation and had he mentioned that he'd isolated it to the sort. not sure though.
|
# ? Apr 13, 2014 21:22 |
|
I'm trying to write a program that will perform Dijkstra's algorithm between two points on a directed graph constructed from an input file. The input file has a number of lines, with the first thing in a line being an int which is the vertex number, the second is another int which is a neighboring vertex, and the third thing is a double which is the path cost/length. I was going merrily along until I realized that I still need to be able to access vertices that may not have any adjacent vertices (that is, you cannot go anywhere from such a vertex). So, I figured I'd just assign constructed vertices to the index of a vector corresponding to that vertex's label, and reserve more space in the vector as necessary. I realize this may be a rather roundabout way of doing what I want, but it seems that it should still work. Here is my header:C++ code:
C++ code:
|
# ? Apr 13, 2014 21:35 |
hooah posted:I'm getting a "vector subscript out of range" at the indicated line. Why is this? At this point, the vector should have a capacity of at least 1. No, that's not what std::vector.reserve() does. It does allocate memory, but it does not resize the vector. The empty vector still has zero elements after reserving space for some, which makes it invalid to set any element in it by index.
|
|
# ? Apr 13, 2014 21:53 |
|
nielsm posted:No, that's not what std::vector.reserve() does. It does allocate memory, but it does not resize the vector. The empty vector still has zero elements after reserving space for some, which makes it invalid to set any element in it by index. Ok. I would think I wouldn't want to create dummy vertices. Is that a correct assumption? If it is, then what else can I do?
|
# ? Apr 13, 2014 22:10 |
hooah posted:Ok. I would think I wouldn't want to create dummy vertices. Is that a correct assumption? If it is, then what else can I do? Either you could have a default constructor for your Vextex class that initializes it to a "dead" state where it somehow marks itself as invalid. Then you can just resize the vector to something big. This is probably what you say you don't want to. Alternatively, switch to using a map instead of a vector for storing vertices in the Graph class.
|
|
# ? Apr 13, 2014 22:55 |
|
You can also store your graph as an adjacency matrix. If you have n vertices you allocate an nxn array of doubles (lets call it edges) and set edges[i][j] to be the weight of the edge from i to j (edges that don't exist get a weight of 0). This is not very memory efficient if your graph is sparse (it's not too bad if the graph is dense) but it is very convenient. If what you're really interested in is implementing Dijkstra's algorithm for practice then it might be a good choice.
|
# ? Apr 13, 2014 23:06 |
|
nielsm posted:Alternatively, switch to using a map instead of a vector for storing vertices in the Graph class. Oh poo poo. That's a much better solution. I'm already using one for keeping track of each vertex's neighbors and their path costs.
|
# ? Apr 13, 2014 23:09 |
|
|
# ? Jun 8, 2024 08:18 |
|
I'm a little confused on 'recv()' and how it behaves. Let's say the following happens My server accepts a connection from a client and begins polling the client's socket with select() The client sends "whattup homeslice?" or something of similar length. On the server, select() indicates there is new data on a socket. The server calls recv(client_fd, buf, 2048, 0) What situations will cause recv to return less than the length of the message the client sent? Replace recv() with SSL_read(), any difference?
|
# ? Apr 14, 2014 23:27 |