C/C++ Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > C/C++ Programming Questions Not Worth Their Own Thread

«‹›641 »

Zopotantor: Feb 24, 2013; ...und ist er drin dann lassen wir ihn niemals wieder raus...

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

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 23:42

Edison was a dick: Apr 3, 2010; direct current only

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

Blotto Skorzany: Nov 7, 2008; He's a PSoC, loose and runnin'
came the whisper from each lip
And he's here to do some business with
the bad ADC on his chip
bad ADC on his chiiiiip

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

Subjunctive: Sep 12, 2006; ✨sparkle and shine✨

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'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.

I missed that as sarcasm. But there are no good I/O APIs. It may be impossible.

# ? Apr 9, 2014 20:52

FamDav: Mar 29, 2008

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

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

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

seiken: Feb 7, 2005; hah ha ha

Looks like I was talking poo poo then my bad

# ? Apr 10, 2014 02:14

Pontificating Ass: Aug 2, 2002; What Doth Life?

I am basically trying to get an inherited class to call its overridden function on construction:

code:

class Syncable
{
public:
	Syncable() { SetSync(); };
protected:
	virtual void SetSync()=0;
};

code:

class Entity : public Syncable
{
public:
	Entity() : Syncable() {};
protected:
	void SetSync()
	{
		//code here
	}
};

I obviously get some unresolved externals around the Syncable class (Syncable::SetSync() referenced in function Syncable::Syncable()), but the Syncable class is always inherited and the virtual function is always defined in the derived class, so I feel like this should work somehow. Any way or better way to do this?

Pontificating Ass fucked around with this message at 01:26 on Apr 11, 2014

# ? Apr 11, 2014 01:23

seiken: Feb 7, 2005; hah ha ha

Basically, you can't do that.

# ? Apr 11, 2014 01:37

The Laplace Demon: Jul 23, 2009; "Oh dear! Oh dear! Heisenberg is a douche!"

seiken posted:

Basically, you can't do that.

Well...

C++ code:

#include <iostream>

struct Base {
    Base() {}
    virtual ~Base() {}
    virtual void foo() const = 0;
};

template<typename Derived>
struct Base_CRTP : Base {
    Base_CRTP() { static_cast<Derived*>(this)->Derived::foo(); }
    virtual ~Base_CRTP() {}
    virtual void foo() const = 0;
};

struct Derived : Base_CRTP<Derived> {
    Derived() {}
    void foo() const { std::cout << "Hello from Derived!" << std::endl; }
};

int main() {
    Base* b = new Derived();
    delete b;
}

You can do that by passing the type of the derived class back to the base. It works, but I don't know if I'd recommend it. The trick is called the curiously recurring template pattern.

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

tractor fanatic: Sep 9, 2005; Pillbug

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

The Laplace Demon: Jul 23, 2009; "Oh dear! Oh dear! Heisenberg is a douche!"

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 class�s 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 constructor�s or destructor�s 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 object�s 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>. :shrug:

The Laplace Demon fucked around with this message at 06:02 on Apr 11, 2014

# ? Apr 11, 2014 05:56

seiken: Feb 7, 2005; hah ha ha

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

The Belgian: Oct 28, 2008

heres a fun C thing for you guys:

code:

#include <stdio.h>
#define ROOSTER_DIM 100

int main (void) {
  int rooster[ROOSTER_DIM][ROOSTER_DIM], i, j;

  for (i=0;i<=ROOSTER_DIM;i++) 
  {
    for (j=0;j<=ROOSTER_DIM;j++) 
	{
      rooster[i][j]=0;
      printf("%d;%d \n",i,j,rooster[ROOSTER_DIM][ROOSTER_DIM]);
    }
  }
  return 0;
}

This doesnt stop, it gets to 100;9 and then goes to 1;10 and keeps looping forever

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

nielsm: Jun 1, 2009

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

raminasi: Jan 25, 2005; a last drink with no ice

Assigning to rooster[100][100] is undefined behavior, so that program is allowed to do whatever it wants.

e: :argh:

# ? Apr 12, 2014 00:02

pseudorandom name: May 6, 2007

Also your compiler will warn about both of those issues.

# ? Apr 12, 2014 00:03

The Belgian: Oct 28, 2008

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

Subjunctive: Sep 12, 2006; ✨sparkle and shine✨

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:


struct message {
  int length;
  char buf[0]; // allocated contiguously following this header
};

Subjunctive fucked around with this message at 00:09 on Apr 12, 2014

# ? Apr 12, 2014 00:06

pseudorandom name: May 6, 2007

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

ExcessBLarg!: Sep 1, 2001

Subjunctive posted:

It's totally defined behaviour. ... It's entirely legal to index an array beyond its declared size.

No it's not. By standard, pointer arithmetic is only valid for elements of the array and one entry past (without dereferencing).

Subjunctive posted:

You see it commonly in structures with variable-length components at the end.

That's defined in C99 for flexible array members, albeit with the limitation that the result of the pointer arithmetic must still point to a valid element of an array (or one entry past?). Also beware that there's other, non-portable variants of the concept (e.g., zero-length array members) that may be supported as non-standard extensions in some compilers.

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

Subjunctive: Sep 12, 2006; ✨sparkle and shine✨

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

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

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. :psyduck:

OneEightHundred fucked around with this message at 06:22 on Apr 12, 2014

# ? Apr 12, 2014 05:13

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

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.

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>.

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

danishcake: Aug 15, 2004

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

FamDav: Mar 29, 2008

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.
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

why are you trying to sort values that give different orderings at different points in time

# ? Apr 13, 2014 15:27

Bruegels Fuckbooks: Sep 14, 2004; Now, listen - I know the two of you are very different from each other in a lot of ways, but you have to understand that as far as Grandpa's concerned, you're both pieces of shit! Yeah. I can prove it mathematically.

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.
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

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

danishcake: Aug 15, 2004

It's probably best explained with a chunk of pseudocode.

code:

bool Sort(const Widget& a, const Widget& b)
{
    int X_a = HardwareInterface::GetX(a);
    int X_b = HardwareInterface::GetX(b);

    return X_a < X_b;
}

The calculation of GetX updates state in the HardwareInterface and would have been better called 'UpdateIterativeEstimateOfX'.
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

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

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

FamDav: Mar 29, 2008

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

danishcake: Aug 15, 2004

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

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

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:

template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
                      _RandomAccessIterator __last,
                      _Tp __pivot, _Compare __comp)
{
  while (true)
  {
    while (__comp(*__first, __pivot))
      ++__first;
    --__last;
    while (__comp(__pivot, *__last))
      --__last;
    if (!(__first < __last))
      return __first;
    std::iter_swap(__first, __last);
    ++__first;
  }
}

See those inner loops? They have been written � possibly with specific intent, possibly not � to not do an iterator comparison to stay in bounds, which would be sensible, but instead to assume that they'll eventually run into the pivot value, for which the comparison will return false, and therefore they'll terminate comfortably within the bounds of the range being sorted. And if the comparison doesn't return false, they'll just run off into the weeds somewhere until either the program crashes or they hit something which the comparator does return false for. And while it won't actually itself do a swap if either loop runs out of control (unless the pointers overflow, which would probably have caused the comparison to crash), it will happily return a possibly-bogus iterator back.

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

FamDav: Mar 29, 2008

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

hooah: Feb 6, 2006; WTF?

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:

#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include <string>
#include <map>
#include <vector>

class Vertex{
public:
	Vertex(int n) : _id(n){};
	void addNeighbor(int i, double d) { _adjacent.insert({ i, d }); };
	const int getId() const { return _id; }
	const double getPathWeight() const { return _pathWeight; }
	void setPathWeight(double d) { _pathWeight = d; }
	void setPrevious(int i) { _previous = i; }
	const int getPrevious() const { return _previous; }
	friend class Graph;
private:
	int _id;
	int _previous;
	double _pathWeight;
	std::map<int, double> _adjacent;
};

class Graph{
public:
	Graph(std::string);
	void traverse();
private:
	Vertex* findVertex(std::vector<Vertex> &, int);
	int findIndex(std::vector<Vertex> &, int);
	std::vector<Vertex> _vertices;
};

#endif

And here is the constructor for Graph:

C++ code:

Graph::Graph(string in){
	ifstream input(in);
	string line, temp;
	int label, adjacent;
	double weight;
	while (getline(input, line)){
		istringstream theLine(line);
		theLine >> temp;
		label = stoi(temp);
		Vertex temporary(label);
		theLine >> temp;
		adjacent = stoi(temp);
		theLine >> temp;
		weight = atof(temp.c_str());
		Vertex* found = findVertex(_vertices, label);
		if (found != nullptr)
			_vertices[findIndex(_vertices, label)].addNeighbor(adjacent, weight);
		else{
			if (label >= _vertices.size())
				_vertices.reserve(label * 2 + 1);
			temporary.addNeighbor(adjacent, weight);    // Problem is here
			_vertices[label] = temporary;
		}
	}
}

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.

# ? Apr 13, 2014 21:35

nielsm: Jun 1, 2009

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

hooah: Feb 6, 2006; WTF?

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

nielsm: Jun 1, 2009

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

Nippashish: Nov 2, 2005; Let me see you dance!

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

hooah: Feb 6, 2006; WTF?

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

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 23:42

Illusive Fuck Man: Jul 5, 2004; RIP John McCain feel better xoxo ð ð; Taco Defender

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

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > C/C++ Programming Questions Not Worth Their Own Thread

«‹›641 »