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 »

hooah: Feb 6, 2006; WTF?

nebby posted:

I'm having some troubles with some code that works fine on Windows, but not really at all on Linux. The problem is to check if a graph is bipartate by traversing it and coloring nodes adjacent to the current one the opposite color (e.g. we start at white, and color any adjacent nodes black). If we run into a color conflict, then the graph is not bipartate. I'm using a breadth-first search to do the traversal. Here's my header:

C++ code:

#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <string>

class Graph;

class Vertex{
public:
	Vertex(int i) : _visited(false), _label(i), _color(10) {};
	void setVisitedFalse(){ _visited = false; }
	void setVisitedTrue(){ _visited = true; }
	void setColor(int c){ _color = c; }
	const int getLabel(){ return _label; }
	const bool isVisited(){ return _visited; }
	const int getColor() { return _color; }
	friend const bool found(const std::vector<Vertex> &, Vertex);
protected:
	bool _visited;
	int _color; // 0 is white, 1 is black
	int _label;
};

class Graph{
public:
	Graph(std::string);
	bool isBipartate();

private:
	std::vector<std::vector<Vertex*>> _vertices;
};


#endif

My definitions file is here, and my main file is:

C++ code:

#include <iostream>
#include <string>
#include "graph.h"

using std::cout; using std::endl; using std::boolalpha;

int main(int argc, char* argv[]){
	if (argc != 2){
		cout << "Incorrect number of parameters" << endl;
		return 1;
	}
	else{
		Graph myGraph(argv[1]);
		bool result = myGraph.isBipartate();
		cout << boolalpha;
		cout << result << endl;
	}
}

The two inputs are here, which is bipartate, and here, which is not.

As I said, my program works fine on Windows - it finds that the first input is bipartate and that the second isn't. However, on Linux, both produce the following output:

code:

10 black
conflict 10 10
false

I tried a little debugging with gdb, but I'm not very familiar with it and couldn't get it to step into my isBipartate function. I then put the files into NetBeans to use its debugger, but it doesn't deal with vectors of vectors very clearly, so I wasn't sure what was happening. Could anyone lend a hand, please?

# ? Mar 25, 2014 14:00

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 19:10

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

It looks like you might be trying to read the first number on each line as an entry in the adjacency list for that index instead of as the index itself. I'm only guessing without looking at the parsing code itself.

# ? Mar 25, 2014 14:50

hooah: Feb 6, 2006; WTF?

The Laplace Demon posted:

It looks like you might be trying to read the first number on each line as an entry in the adjacency list for that index instead of as the index itself. I'm only guessing without looking at the parsing code itself.

I started out doing that, but then realized I needed to be able to have a vertex that is the first number on a given line in the input, so now it creates new entries for everything in the adjacency list (or should, anyway).

# ? Mar 25, 2014 15:12

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

I don't see a reason to construct a whole bunch of redundant vertices when you're initially parsing the input, and then trying to finish constructing the graph as you're doing the bipartite check. It seems needlessly complicated, and a great way to introduce errors.

One example of an error that you've introduced: when you check isVisited(), the answer is almost always going to be false, even if you have in fact already visited that particular vertex via a different path.

What I would do is make the graph construction routine construct the complete graph (with everything that points to a particular vertex pointing at the exact same vertex instance), and then write a routine that prints out what the graph is. That way you can check your graph-reading and your bipartite-checking code in isolation, instead of having to worry about figuring out which half of the program a particular bug is in.

# ? Mar 25, 2014 15:27

hooah: Feb 6, 2006; WTF?

Jabor posted:

What I would do is make the graph construction routine construct the complete graph (with everything that points to a particular vertex pointing at the exact same vertex instance), and then write a routine that prints out what the graph is. That way you can check your graph-reading and your bipartite-checking code in isolation, instead of having to worry about figuring out which half of the program a particular bug is in.

Since this is due soon, I'd rather not do a major re-write if I don't have to, but I'll keep this in mind.

# ? Mar 25, 2014 16:19

nielsm: Jun 1, 2009

Instead of having "visited" and "color" be properties of each node, just keep them as local variables in the bipartite check algorithm. Since that's what they are! The std::set or std::map types can be very useful for that, but if you aren't allowed to use those then you can also just do with some simple vectors of ints. One set (vector) containing the IDs of nodes that you have already visited, one map (or two vectors, one for each color) that tells which color a node has been assigned. That will first of all solve your problem with the adjacency list representation of your graph storing whether you have traversed a specific edge rather than visited a specific node, and similarly that you end up coloring edges rather than nodes. It will also allow you to simplify your adjacency list representation to just be a vector (indices being node names) of vectors of adjacent nodes, instead of needing each element in a node's adjacency list to be a complex object.

# ? Mar 25, 2014 16:38

Praseodymi: Aug 26, 2010

I'm trying to write an RRT and I was getting occasional long pauses while trying to find the nearest existing node to the new point. I could understand if it was hitting a wall on the map and discarding the new point but I can't think of a reason it can't get past this, even if there are two points equal distances away.
This is my code:

code:

		Vector2D xRand;
		xRand.x = rand() % width;
		xRand.y = rand() % height;

		Vector2D xNear = points[0];

		for ( unsigned int j = 0; j < points.size(); j++ )
		{
			if ((points[j] - xRand).sqrLength() < (xNear - xRand).sqrLength())
				xNear = points[j];
		}

(sqrLength just returns the square of the length of the vector).

For a reason I can't figure out the final if statement is where VS says the program is getting hung. Sometimes it continues after a little pause but sometimes it takes longer than I'm willing to wait. And it can happen after any number of tree generations, does anyone know why it might be doing this?

Praseodymi fucked around with this message at 17:22 on Mar 25, 2014

# ? Mar 25, 2014 17:17

nielsm: Jun 1, 2009

I think you need to post some more code. How often is that code you posted being run? How many elements do you have in your points list?

VS allows you to set breakpoints then alter them to trace-points, i.e. make the debugger write a message each time a breakpoint is passed, but not actually stop at it. That can also include printing the values of in-program variables and more. You can try using that to trace what your program is actually doing.

# ? Mar 25, 2014 17:24

Praseodymi: Aug 26, 2010

Points starts with a single point in it. After the code I posted a unit vector is created a certain length from xNear to xRand, which is added to points, so that code then runs until Points reaches the number of iterations defined at the start of the program, in this case 1000.

This problem only became evident when I was testing to find out how quick it was by running it over and over again, but all the containers are cleared when a new tree is generated, and like I said, i've seen it happen after anywhere between 5 generations and 350.

EDIT: I just tried it on two different maps, and it seems to happen less often the larger the map is.

Praseodymi fucked around with this message at 17:47 on Mar 25, 2014

# ? Mar 25, 2014 17:38

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

hooah posted:

Since this is due soon, I'd rather not do a major re-write if I don't have to, but I'll keep this in mind.

You might also want to just write a routine to print the graph (could use gnuplot format), so that you can verify it, or call it from the debugger when things get weird. Also makes for good record-and-compare for regression testing.

# ? Mar 25, 2014 17:58

slovach: Oct 6, 2005; Lennie Fuckin' Briscoe

Does it really win me much to be const'ing parameters that are passed by value? It's documentation, but is there much use to it?

# ? Mar 28, 2014 03:44

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

slovach posted:

Does it really win me much to be const'ing parameters that are passed by value? It's documentation, but is there much use to it?

There is close to zero practical use for it (it might impact an optimization in some weird fringe case). It's not really useful as documentation either - why would anyone outside the function care whether the function is going to modify something that isn't coming back out in any way?

If you're passing something big as a const value, pass it as a const reference. If you're passing something small as a const value, you're probably wasting some keystrokes.

# ? Mar 28, 2014 03:53

Plorkyeran: Mar 22, 2007; To Escape The Shackles Of The Old Forums, We Must Reject The Tribal Negativity He Endorsed

Marking a (non-ref, non-pointer) function parameter as const in the declaration doesn't do anything at all. It doesn't even serve as documentation of implementation details that the caller shouldn't care about, as the constness of values in the definition of the function doesn't have to match the declaration.

Making arguments const in the definition itself is useful for the same reason as making local variables const is ever useful: if you think you shouldn't be modifying an argument but do, then you may have a bug. However, keep in mind that you can't move out of const values.

# ? Mar 28, 2014 04:02

Gazpacho: Jun 18, 2004; by Fluffdaddy; Slippery Tilde

I suppose you mean documentation for people who don't know that value arguments are not written back, but you can't cargo-cult someone into learning the features of a programming language.

# ? Mar 28, 2014 04:12

giogadi: Oct 27, 2009

Praseodymi posted:

RRT

Sup robotics buddy :hfive:

There's some weirdness in RRT's performance sometimes due to its randomness, so it can be hard to pin down issues. If you post your full source code I can try to help you out. RRTs and related algorithms are my primary research area.

# ? Mar 28, 2014 17:28

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

We just released our custom C/C++ preprocessor, Warp. It had a surprisingly large impact on our build times.

https://code.facebook.com/posts/476987592402291/under-the-hood-warp-a-fast-c-and-c-preprocessor/

# ? Mar 28, 2014 19:34

MrMoo: Sep 14, 2000

That's a few days early no? I know none of the Boost headers I use don't have include guards in.

# ? Mar 28, 2014 19:46

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

People actually use D for things??

# ? Mar 28, 2014 19:52

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

GrumpyDoctor posted:

People actually use D for things??

Well Andrei obviously does.

# ? Mar 28, 2014 19:52

giogadi: Oct 27, 2009

Praseodymi posted:

This is my code:

code:

		Vector2D xRand;
		xRand.x = rand() % width;
		xRand.y = rand() % height;

		Vector2D xNear = points[0];

		for ( unsigned int j = 0; j < points.size(); j++ )
		{
			if ((points[j] - xRand).sqrLength() < (xNear - xRand).sqrLength())
				xNear = points[j];
		}

One thing I did notice was that, the way you've implemented the point sampling, you're actually sampling from a fixed, discrete grid of points in space. The coarseness of your grid depends entirely on the size of the space; therefore, the larger the width and height, the finer the grid will be relative to the space. This might explain why the method's performance seems to improve with larger maps.

You should change the sampling to actually sample from RAND_MAX possible values. This way the performance will be less sensitive to the size of your map.

code:

xRand.x = width * ((double) rand() / RAND_MAX);

This'll work better, but it still isn't the best way because the standard rand() function on most systems has really lovely randomness properties and RAND_MAX can be literally anything greater than 32767. Boost's random library is great for stuff like this.

About VS hanging at the sqrLength() line: how did you test for "hanging"? Did you just break execution randomly and find it was always in that spot? On typical problems RRT spends the most time deciding whether a point is in collision or not, but in some cases the most expensive part is that distance comparison, which would explain how often the program happens to be there when you cut execution.

# ? Mar 28, 2014 22:17

Praseodymi: Aug 26, 2010

giogadi posted:

This'll work better, but it still isn't the best way because the standard rand() function on most systems has really lovely randomness properties and RAND_MAX can be literally anything greater than 32767. Boost's random library is great for stuff like this.

That's reminded me of something. I came into contact with C++11's random stuff for the first time a while ago, is that any good, or is it just more customisable?

# ? Mar 28, 2014 23:01

Volguus: Mar 3, 2009

Subjunctive posted:

Well Andrei obviously does.

Andrei just bragged not too long ago about pushing the first D program in production at facebook: http://forum.dlang.org/thread/l37h5s$2gd8$1@digitalmars.com

Volguus fucked around with this message at 23:06 on Mar 28, 2014

# ? Mar 28, 2014 23:03

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

roomforthetuna posted:

There is close to zero practical use for it (it might impact an optimization in some weird fringe case).

It could, yes. It is undefined behavior to modify a const object.* ** *** Therefore, if you take the address of such an object and pass it to an opaque function, the compiler can assume that the function doesn't actually modify the original object. I don't know of any compilers that specifically do this optimization right now, but it's legal, and we've certainly looked into it for clang.

* That is, an object which was constructed as a const object per its declaration/construction, as opposed to a non-const object that you happen to have a const reference/pointer to, where you are totally allowed to cast away the constness and modify the object.
** Of course, you can modify any mutable fields of such an object.
*** Because C++ is dumb, you can destroy a const object and create a new object there with a different value, but then it's undefined behavior to access it through the original name.****
**** This is some of the vaguest bullshit in the standard.

# ? Mar 29, 2014 00:35

durtan: Feb 21, 2006; Whoooaaaa

Would someone like to clue me in on why I can't declare this variable array? I keep getting "Unused variable 'code'" messages and I'm completely stumped since I'm declaring a new variable right before it and have done similar things in the past with no issue. I surrounded it with asterisks so it can be found easily, it's near the bottom of the code and this program is unfinished, but I'm fairly certain I have all the braces where they need to be.

code:

 #include <stdio.h>
#include <stdlib.h>
#include <cs50.h>
#include <ctype.h>
#include <string.h>

int main (int argc, string argv[])
//argument check
{
if (argc != 2)
    {
    printf("You need 1 argument, sucka!\n");
    return 1;
    }    
    
else
//codword check and storage. k is keyword and j is each letter in the keyword. 
    {
    string k = argv[1];
    int j[strlen(k)];
    for (int i = 0, n = strlen(k); i < n; i++)
        {
        if (isalpha(k[i]))
            {
            j[i] = (int) k[i];
            //printf("%i\n", j[i]);
            }
        else
            {
            printf("Alphabet only, please!\n");
            return 1;
            }
        }
//Get the phrase *coded is array for converted letters*
     string phrase = GetString();
     *****char code[strlen(phrase)];******
    
//convert the phrase
    for (int i = 0, n = strlen(phrase); i < n; i++)
        {
        
        }
    }
}

# ? Mar 29, 2014 00:41

Star War Sex Parrot: Oct 2, 2003

It looks like you need to dynamically allocate an array since the length isn't a compile-time constant. You need to do a heap allocation if the size is to be determined at run-time.

# ? Mar 29, 2014 00:48

Xerophyte: Mar 17, 2008; This space intentionally left blank

Variable length local arrays are not allowed in C++ (but are in C99, I think). The probably not entirely correct explanation is that this is because local arrays go on the stack and C++ wants to know how much stack to allocate early, but here the space required is not known until the relevant strlen is calculated. Solution: allocate on the heap.

In C++03:

C++ code:

	char *code = new char[strlen(phrase)];

	// Before returning, throwing exceptions or otherwise leaving your function...
	delete[] code;

In C++11:

C++ code:

	auto code = std::unique_ptr<char[]>(new char[strlen(phrase)]);
	// Is automatically cleaned up, no delete needed

In C++14:

C++ code:

	auto code = std::make_unique<char[]>(strlen(phrase));
	// Is also a std::unique_ptr<char[]>, so no cleanup needed

Err, yep, it should. I'm totally a professional at this.
vvvvvv

Xerophyte fucked around with this message at 01:11 on Mar 29, 2014

# ? Mar 29, 2014 00:59

Star War Sex Parrot: Oct 2, 2003

Xerophyte posted:

In C++03:

C++ code:

	char *code = new char[strlen(phrase)];

	// Before returning, throwing exceptions or otherwise leaving your function...
	delete code;

Shouldn't that be delete[]?

# ? Mar 29, 2014 01:02

Jewel: May 2, 2009

Xerophyte posted:

In C++14:

C++ code:

	auto code = std::make_unique<char[]>(strlen(phrase));
	// Is also a std::unique_ptr<char[]>, so no cleanup needed

I still can't believe they added std::make_shared but completely left out std::make_unique for reasons unknown :sigh:

Edit: Especially when it doesn't use any C++14 features, it seems. I found an answer on StackOverflow that implements the same functionality if you want to use it in C++11:

C++ code:

#include <cstddef>
#include <memory>
#include <type_traits>
#include <utility>

namespace std {
    template<class T> struct _Unique_if {
        typedef unique_ptr<T> _Single_object;
    };

    template<class T> struct _Unique_if<T[]> {
        typedef unique_ptr<T[]> _Unknown_bound;
    };

    template<class T, size_t N> struct _Unique_if<T[N]> {
        typedef void _Known_bound;
    };

    template<class T, class... Args>
        typename _Unique_if<T>::_Single_object
        make_unique(Args&&... args) {
            return unique_ptr<T>(new T(std::forward<Args>(args)...));
        }

    template<class T>
        typename _Unique_if<T>::_Unknown_bound
        make_unique(size_t n) {
            typedef typename remove_extent<T>::type U;
            return unique_ptr<T>(new U[n]());
        }

    template<class T, class... Args>
        typename _Unique_if<T>::_Known_bound
        make_unique(Args&&...) = delete;
}

Jewel fucked around with this message at 01:14 on Mar 29, 2014

# ? Mar 29, 2014 01:08

durtan: Feb 21, 2006; Whoooaaaa

For what it's worth, it's C, not C++. C99, specifically. So does that mean I *should* be able to declare a variable length array farther down in the code?

# ? Mar 29, 2014 01:16

Gazpacho: Jun 18, 2004; by Fluffdaddy; Slippery Tilde

Even if durtan is using C, the smart array type in standard C++ is not named *_ptr at all. It's named "vector"

Gazpacho fucked around with this message at 01:42 on Mar 29, 2014

# ? Mar 29, 2014 01:32

Xerophyte: Mar 17, 2008; This space intentionally left blank

durtan posted:

For what it's worth, it's C, not C++. C99, specifically. So does that mean I *should* be able to declare a variable length array farther down in the code?

Ah. What's string here? A typedef to char* in one of those headers I guess...

Anyhow, far as I know the VLA declaration should be fine in a C99-compliant compiler and you're obviously making one earlier (j) and that works. I guess you might be getting unused variable warnings because you're not actually using the code variable anywhere in the posted code, though. :v:

You're declaring it, but that's not using.

# ? Mar 29, 2014 01:38

durtan: Feb 21, 2006; Whoooaaaa

Xerophyte posted:

Ah. What's string here? A typedef to char* in one of those headers I guess...

Anyhow, far as I know the VLA declaration should be fine in a C99-compliant compiler and you're obviously making one earlier (j) and that works. I guess you might be getting unused variable warnings because you're not actually using the code variable anywhere in the posted code, though. You're declaring it, but that's not using.

I believe the "string" declaration is part of the cs50.h file provided to me by the class. And you're right, I wasn't using the variable so it was giving me that error. Thanks everyone!

# ? Mar 29, 2014 01:51

WaterIsPoison: Nov 5, 2009

giogadi posted:

Sup robotics buddy

There's some weirdness in RRT's performance sometimes due to its randomness, so it can be hard to pin down issues. If you post your full source code I can try to help you out. RRTs and related algorithms are my primary research area.

Robotics researchers represent! SLAM here, although I submitted an RRT variant to IROS, just to get the notch in my belt...

# ? Mar 29, 2014 02:34

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Variadic templates. :suicide:

(Making a thing that can expect a number of values which can be any combination of strings, ints or bools, which will be parsed out of a single string parameter, and then the results need to get crammed into a pre-existing variadic templated class.)

This isn't a question, just :suicide:

# ? Mar 29, 2014 05:44

xgalaxy: Jan 27, 2004; i write code

Xerophyte posted:

Variable length local arrays are not allowed in C++ (but are in C99, I think). The probably not entirely correct explanation is that this is because local arrays go on the stack and C++ wants to know how much stack to allocate early, but here the space required is not known until the relevant strlen is calculated. Solution: allocate on the heap.

In C++14:
C++ code:
	auto code = std::make_unique<char[]>(strlen(phrase));
	// Is also a std::unique_ptr<char[]>, so no cleanup needed

C++ 14 supports runtime sized arrays without heap, so you don't need this.

# ? Mar 29, 2014 08:21

Jewel: May 2, 2009

xgalaxy posted:

C++ 14 supports runtime sized arrays without heap, so you don't need this.

That's a really good tidbit, thanks for mentioning it! C++14 now sounds worth it.

# ? Mar 29, 2014 09:18

space kobold: Oct 3, 2009

edit: wrong thread, I'm an idiot.

space kobold fucked around with this message at 22:10 on Mar 29, 2014

# ? Mar 29, 2014 21:47

That Turkey Story: Mar 30, 2003

xgalaxy posted:

C++ 14 supports runtime sized arrays without heap, so you don't need this.

No it doesn't, that was cut.

# ? Mar 30, 2014 08:37

Zerf: Dec 17, 2004; I miss you, sandman

xgalaxy posted:

C++ 14 supports runtime sized arrays without heap, so you don't need this.

Meh, just write a wrapper around alloca() and most platforms will support it independent from any C/C++ standard.

# ? Mar 30, 2014 11:35

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 19:10

shrughes: Oct 11, 2008; (call/cc call/cc)

Zerf posted:

Meh, just write a wrapper around alloca() and most platforms will support it independent from any C/C++ standard.

How would you destroy the objects you've constructed in the region?

# ? Mar 30, 2014 11:50

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

«‹›641 »