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

«‹›639 »

Lexical Unit: Sep 16, 2003

Ugg boots posted:

How is this a problem from using "non-default" libraries? Instead of including a Header and CPP files in your project you include a Header and LIB files...

See my last paragraph. Basically what it amounts to is we can't do that because what we put into our code base is strictly regulated by agencies not under our control. So it would be much more of a hassle to try and package some third party code/library in our code base than it is to just re-invent the wheel where necessary or work around not having certain functionality that's readily available from third parties.

Sucks.

# ? Jul 17, 2008 19:29

Adbot: ADBOT LOVES YOU

# ? Apr 29, 2024 06:12

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Lexical Unit posted:

But then there's the issue of wether or not you really want to incorporate some third party's code into your codebase or not. In many situations this would entail a full audit of the third party code and require additional further audits each time the third party released a new version that you might want to incorporate.

That is completely retarded (though it seems you're aware of that). Do these people audit the code for their compilers (and standard libraries) and every other app in their toolchain? I can just about guarantee that no organization that does this actually knows what the machine-code contents of their executables look like anyway.

# ? Jul 17, 2008 19:39

Lexical Unit: Sep 16, 2003

You're completely right in my estimation.

However the situation is that every few years we get to use a new version of RHEL (that's recently been stamped with a seal of approval) and that implicitly OKs a number of packages/libraries for our consumption. The assumption being that all those libraries/packages that come with some defined configuration/installation of that version of RHEL have undergone some kind of audit (though I highly doubt this is the case or if it is the case I highly doubt the usefulness or completeness of those audits).

# ? Jul 17, 2008 19:44

UberJumper: May 20, 2007; woop

I got a few questions for your pro cpp devs:

1. STL Objects, is it really bad to do things such as having: vector<map> or basically 2d STL objects?

2. For string manipulation lets say i have 3 std::string a, b, c, and i want to concat them all. Would it be better to just do : std::string d.append(them all) or would it be better to use std::stringstream.

3. Why should i ever use pointers? The only reason i can see them being useful, is for when creating and allocating big blocks of memory, then having that memory freed half way through the application. I've always passed everything by reference, returned references when i can etc.

4. Are design patterns and methodologies always needed, for simple applications?

5. Is there a reason to create, .h files that just hold a set of functions? Or is it better practice to encapsulate the functions in a class, and have these functions declared as static.

6. Do try and catch statements add considerable overhead to the application?

I'm kinda just learning C++ now. so bear with me.

# ? Jul 20, 2008 17:14

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

UberJumper posted:

1. STL Objects, is it really bad to do things such as having: vector<map> or basically 2d STL objects?

It's fine, just so long as you remember that inserting an element into the parent collection makes a copy.

UberJumper posted:

2. For string manipulation lets say i have 3 std::string a, b, c, and i want to concat them all. Would it be better to just do : std::string d.append(them all) or would it be better to use std::stringstream.

It doesn't matter, chances are that micro-optimizations like that aren't really important (and if they are you would do better to use char *s anyway.

UberJumper posted:

3. Why should i ever use pointers? The only reason i can see them being useful, is for when creating and allocating big blocks of memory, then having that memory freed half way through the application. I've always passed everything by reference, returned references when i can etc.

Pointers are very important, since they allow objects to have other-than-lexical scope. If you make an object on the stack in a function and return a reference to it, that object will get destructed when the function returns. It's also necessary for dynamically-sized data.

UberJumper posted:

4. Are design patterns and methodologies always needed, for simple applications?

I don't use "design patterns" as such for any of my projects. Granted, a design-pattern nerd will probably look at my code and say "oh well this is a clear example of design pattern X", but I just write code in whatever way I find to be most elegant.

UberJumper posted:

5. Is there a reason to create, .h files that just hold a set of functions? Or is it better practice to encapsulate the functions in a class, and have these functions declared as static.

God yes. This isn't Java, and it makes no sense to have a class that can't actually be instantiated. Use a namespace if you need to encapsulate all the functions, or just leave them global if you don't care.

UberJumper posted:

6. Do try and catch statements add considerable overhead to the application?

They do add overhead, in that a function that may throw needs to be compiled such that it can "return" at arbitrary points in its execution. Additionally, exceptions require some form of RTTI (run-time type identification) in order to inspect the exception's type when caught.

That said, if you have to ask, it's not important for what you're doing.

# ? Jul 20, 2008 18:26

ahobday: Apr 19, 2007

I've checked out Bjarne's book on C++. It seems comprehensive. I've also taken a look at Thinking in C++.

Is there a book I can get hold of that takes C++ programming and explains each and every detail in layman's terms? Or gives metaphors to help understanding. I find myself reading some sentences or paragraphs in "The C++ Programming Language" several times in an effort to digest them.

A book which can be used as sort of a reference for explaining concepts in plain English rather than relying on other programming concepts would definitely be helpful.

Like, is the C++ For Dummies book any good? I'd imagine that would break things down well enough.

# ? Jul 20, 2008 18:30

more falafel please: Feb 26, 2005; forums poster

Avenging Dentist posted:

Pointers are very important, since they allow objects to have other-than-lexical scope. If you make an object on the stack in a function and return a reference to it, that object will get destructed when the function returns. It's also necessary for dynamically-sized data.

Yes. Pointers are also necessary for referencing objects that may be invalid, since they can be NULL, and references (for any defined behavior) can't be. Also, references can not be reseated to refer to a different object - once they're defined they point at that object forever until they go out of scope.

That said: you should use references over pointers whenever feasible.
http://www.parashift.com/c++-faq-lite/references.html#faq-8.6

(As an aside, you would probably benefit from reading large portions of the C++ FAQ Lite, as well Scott Meyer's Effective C++)

quote:

I don't use "design patterns" as such for any of my projects. Granted, a design-pattern nerd will probably look at my code and say "oh well this is a clear example of design pattern X", but I just write code in whatever way I find to be most elegant.

The most important part of the Gang of Four Design Patterns book is the prologue, where it says that the purpose of the book is to create a common language for talking about patterns that "naturally occur" in object-oriented programming. In other words, every competent programmer will, at some point, decide that they need something like the Strategy pattern, but instead of describing exactly how they accomplish it in code, they can say "I use something like the Strategy pattern here."

Design patterns are NOT a set of idioms for you to put in your programs. I would even advise against specifically referring to the classes that implement things like design patterns by their pattern name (for instance, don't call your classes FooStrategy and BarStrategy). For one thing, it adds little information: the code you're writing should make it pretty obvious that you're using something like Strategy. But the main problem is that it will lead to a tendency to write code that conforms more closely to the Go4 book than to your actual problem. Again, the usefulness of design patterns comes from the fact that it lets programmers talk about solutions to design problems with a common language -- not a starting-off point where you just fill in the details. If you try to do this, you'll end up with patternitis and over-engineer everything about your program. In other words, you'll end up as a Java programmer.

quote:

God yes. This isn't Java, and it makes no sense to have a class that can't actually be instantiated. Use a namespace if you need to encapsulate all the functions, or just leave them global if you don't care.

Again, don't overthink it. The main reasons you use classes are for associating code with the data it operates on, encapsulating that data (implementation details) and hiding it behind the interface, and polymorphism. If you don't need any of these, then the only reason you're putting things in a class is so they're not in the global namespace. Ok, then put them in a namespace. If you don't want clients to be able to call certain functions directly (what you would put private in a class), then put them in the anonymous namespace so they won't be visible outside the file they're defined in.

Classes are a tool that C++ programmers have. They're a very powerful tool, but they're by no means the only tool.

quote:

They do add overhead, in that a function that may throw needs to be compiled such that it can "return" at arbitrary points in its execution. Additionally, exceptions require some form of RTTI (run-time type identification) in order to inspect the exception's type when caught.

That said, if you have to ask, it's not important for what you're doing.

Yeah, there's definitely overhead involved. The biggest problem is that using exceptions in one place in a program essentially means that the rest of the program has to be using RTTI and have exception-handling code compiled in.

But generally when you try to solve a similar problem without exceptions, you end up with a half-assed complicated ugly version of exception handling. Unless you're talking about game development (like real AAA-title game development), real-time trading, or something else that needs to be super-loving-fast and use as little memory as possible, just use exceptions. Putting it in perspective: if 1ms doesn't sound like a lot of time, use exceptions.

# ? Jul 20, 2008 18:55

more falafel please: Feb 26, 2005; forums poster

Centipeed posted:

I've checked out Bjarne's book on C++. It seems comprehensive. I've also taken a look at Thinking in C++.

Is there a book I can get hold of that takes C++ programming and explains each and every detail in layman's terms? Or gives metaphors to help understanding. I find myself reading some sentences or paragraphs in "The C++ Programming Language" several times in an effort to digest them.

A book which can be used as sort of a reference for explaining concepts in plain English rather than relying on other programming concepts would definitely be helpful.

Like, is the C++ For Dummies book any good? I'd imagine that would break things down well enough.

Accelerated C++:
http://www.amazon.com/Accelerated-Practical-Programming-Example-Depth/dp/020170353X

# ? Jul 20, 2008 18:56

Smackbilly: Jan 3, 2001; What kind of a name is Pizza Organ! anyway?

UberJumper posted:

3. Why should i ever use pointers? The only reason i can see them being useful, is for when creating and allocating big blocks of memory, then having that memory freed half way through the application. I've always passed everything by reference, returned references when i can etc.

Consider the scenario in which a class Foo has a member that needs to refer to some other object of type Bar. Say that either you don't know what Bar object you need to refer to when you construct your Foo object, or that you want to be able to change which Bar object the Foo uses at will.

Given that references cannot be uninitialized or null, and they cannot be changed to refer to something else, how do you do this with references?

Answer: You can't; you use pointers.

References in C++ are basically just shorthand for pointers when you only need to do very basic things with them. When you need to do more complex things like have a pointer that points nowhere, or a pointer that changes where it points to, or a pointer that points to a dynamically sized piece of memory, or a pointer that doesn't point to the beginning of an allocation, then references don't support what you want, and you have forgo the shorthand and use pointers directly.

The benefit of references of course is that because they disallow those things, and those things are the kinds of things that end up causing pointer-related errors, references are less error-prone, and so you should use them when you can. But their relative safety makes them very limited, and when you start writing larger C++ applications you will encounter these limitations frequently.

Smackbilly fucked around with this message at 20:26 on Jul 20, 2008

# ? Jul 20, 2008 20:23

Entheogen: Aug 30, 2004; by Fragmaster

I used pointers before to switch between two arrays that contain same types.

such as

code:

vector< int > A, B;
vector<int> * curr = & A;
while( true )
{
   // do something 
   if( curr == & A ) curr = &B;
   else curr = &A;
}

Is there a better way of doing this without pointers? Or is this fine. Also in this case the pointer, is of course, pointing to something on a stack, right?

If I did something like this:

code:

int * a = & int(5);

then a is pointing to something on the stack and will be gone after it is popped off?

Also is there a way to get around using some confusing rear end referencing and dereferncing operators when dealing with iterators on containers that contain pointers themselves?

such as

code:

#define FOREACH(_it,_l) for(__typeof((_l).begin()) _it=((_l).begin());(_it)!=(_l).end();(_it)++) 

.....

class Foo
{
   public:
      void lol(){}
};

.......

vector< Foo * > lolz;
FOREACH( el, lolz )
{
   (*el)->lol();
}

Entheogen fucked around with this message at 21:02 on Jul 20, 2008

# ? Jul 20, 2008 20:57

Brackhar: Aug 26, 2006; I'll give you a definite maybe.

So in preparation for job searching I've been systematically solving the problems posted at this blog as practice, but I'm having a bit of trouble figuring out a decent implementation for one of the questions that would be feasible in a timed environment. Here is the question:

quote:

Write a function �void noparens(char * expression)� that prints all the possible different results you can get from different grouping of parentheses in the given expression.

The string �expression� contains the operators �+�, �-�, �*� and positive integers (or possibly no operators and just one integer). The expression is entirely unparenthesized. Your function should determine the result of every possible parenthesization of the expression and print the distinct ones.

Don�t worry about overflowing int or strange formatting of the expression.

Examples:
A. expression �1 + 2 � 3 * 4�
(((1 + 2) � 3) * 4) = 0
((1 + 2) � (3 * 4)) = -9
((1 + (2 � 3)) * 4) = 0
(1 + ((2 � 3) * 4)) = -3
(1 + (2 � (3 * 4))) = -9
There were five possible, but two were the same, so your function should print:
3 unique { 0, -9, -3 }

I'm trying to figure out a solution that would work in strict Ansi C, but I'm not able to figure out an elegant approach. Particularly, my implementations seem to break down as they attempt to generate functions of the form ((1 + 2) � (3 * 4)). Can any of you provide some advice?

# ? Jul 20, 2008 21:26

Smackbilly: Jan 3, 2001; What kind of a name is Pizza Organ! anyway?

Entheogen posted:

I used pointers before to switch between two arrays that contain same types.

such as
code:
vector< int > A, B;
vector<int> * curr = & A;
while( true )
{
   // do something 
   if( curr == & A ) curr = &B;
   else curr = &A;
}
Is there a better way of doing this without pointers? Or is this fine. Also in this case the pointer, is of course, pointing to something on a stack, right?

Yes, curr is pointing to the stack. As far as whether there's a more elegant way to do that depends on what exactly you are trying to accomplish.

quote:

If I did something like this:
code:
int * a = & int(5);
then a is pointing to something on the stack and will be gone after it is popped off?

This isn't legal C++ (does your compiler allow it?). int(5) is nothing more than the integer literal '5' being C-style casted to an integer, which does nothing. Literals are not lvalues (things that can appear on the left side of an = assignment) and therefore you can't legally take their address because they might not have one.

quote:

Also is there a way to get around using some confusing rear end referencing and dereferncing operators when dealing with iterators on containers that contain pointers themselves?

such as
code:
#define FOREACH(_it,_l) for(__typeof((_l).begin()) _it=((_l).begin());(_it)!=(_l).end();(_it)++) 

.....

class Foo
{
   public:
      void lol(){}
};

.......

vector< Foo * > lolz;
FOREACH( el, lolz )
{
   (*el)->lol();
}

I can't seem to think of a general way to get rid of that syntax with a macro, but that's not particularly confusing to anyone who has worked with STL iterators.

# ? Jul 20, 2008 21:43

Smackbilly: Jan 3, 2001; What kind of a name is Pizza Organ! anyway?

Brackhar posted:

So in preparation for job searching I've been systematically solving the problems posted at this blog as practice, but I'm having a bit of trouble figuring out a decent implementation for one of the questions that would be feasible in a timed environment. Here is the question:

I'm trying to figure out a solution that would work in strict Ansi C, but I'm not able to figure out an elegant approach. Particularly, my implementations seem to break down as they attempt to generate functions of the form ((1 + 2) � (3 * 4)). Can any of you provide some advice?

((1 + 2) � (3 * 4)) is a valid insertion of parenthesis. That example leaves off several valid insertions such as the one you had and, for example, ((1 + 2 - 3) * 4). However note that the question is only looking for the unique solutions that can be obtained through parenthesis insertion, not an enumeration of all possible parenthesis insertions.

If you want a hint as to how you should approach this problem, I'll tell you that this problem appears to be NP-Complete (read: don't try to brute-force it!), but it is a prime candidate for a dynamic programming solution.

There's nothing really C++ or C-centric about this problem - it's a test of your ability to design an algorithm.

Smackbilly fucked around with this message at 21:52 on Jul 20, 2008

# ? Jul 20, 2008 21:50

That Turkey Story: Mar 30, 2003

Entheogen posted:

Also is there a way to get around using some confusing rear end referencing and dereferncing operators when dealing with iterators on containers that contain pointers themselves?

Adapt the iterator similar to how you make reverse iterators. Boost actually has an iterator adapter for exactly your situation.

Edit: Also use BOOST_FOREACH instead of that macro you posted! It's more portable and only evaluates its macro arguments once.

# ? Jul 20, 2008 22:01

sarehu: Apr 20, 2007; (call/cc call/cc)

Entheogen posted:

I used pointers before to switch between two arrays that contain same types.

such as
code:
vector< int > A, B;
vector<int> * curr = & A;
while( true )
{
   // do something 
   if( curr == & A ) curr = &B;
   else curr = &A;
}
Is there a better way of doing this without pointers?

Yeah, use a function.

code:

vector<int> A, B;
while(true) {
  f(A);
  f(B);
}

# ? Jul 20, 2008 22:07

Brackhar: Aug 26, 2006; I'll give you a definite maybe.

Smackbilly posted:

((1 + 2) � (3 * 4)) is a valid insertion of parenthesis. That example leaves off several valid insertions such as the one you had and, for example, ((1 + 2 - 3) * 4). However note that the question is only looking for the unique solutions that can be obtained through parenthesis insertion, not an enumeration of all possible parenthesis insertions.

If you want a hint as to how you should approach this problem, I'll tell you that this problem appears to be NP-Complete (read: don't try to brute-force it!), but it is a prime candidate for a dynamic programming solution.

There's nothing really C++ or C-centric about this problem - it's a test of your ability to design an algorithm.

Right, I was just saying that the algorithmic approaches I tried could not account for ((1 + 2) � (3 * 4)), which I agree is a valid insertion. Would you be willing to provide a larger hint? While I'm not familiar with Dynamic Programming by name, the link you provided looked somewhat close to the recursive approach I was trying and failing with.

# ? Jul 20, 2008 22:09

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Brackhar posted:

I'm trying to figure out a solution that would work in strict Ansi C, but I'm not able to figure out an elegant approach. Particularly, my implementations seem to break down as they attempt to generate functions of the form ((1 + 2) � (3 * 4)). Can any of you provide some advice?

Just iterate over every permutation of the operators and evaluate the results. e.g.

code:

+, -, *:   ((1+2)-3)*4 = 0
+, *, -:   (1+2)-(3*4) = -9
-, +, *:   (1+(2-3))*4 = 0
-, *, +:   1+((2-3)*4) = -3
*, +, -:   (1+2)-(3*4) = -9
*, -, +:   1+(2-(3*4)) = -9

Then store the results in a set, eliminating duplicates. Granted, this solution is O(n!), but for small expressions, should be plenty fast.

# ? Jul 20, 2008 22:12

Brackhar: Aug 26, 2006; I'll give you a definite maybe.

Avenging Dentist posted:

Just iterate over every permutation of the operators and evaluate the results. e.g.
code:
+, -, *:   ((1+2)-3)*4 = 0
+, *, -:   (1+2)-(3*4) = -9
-, +, *:   (1+(2-3))*4 = 0
-, *, +:   1+((2-3)*4) = -3
*, +, -:   (1+2)-(3*4) = -9
*, -, +:   1+(2-(3*4)) = -9
Then store the results in a set, eliminating duplicates. Granted, this solution is O(n!), but for small expressions, should be plenty fast.

So that seems the fairly obvious way to approach it, but what's the underlying mechanism to handle the evaluations? Do you parse through the string and create a tree, do you use a stack, modify the string in place...? I thought about constructing a tree, but I worried that in a timed situation I'd not be able to do the insertions in the proper order to generate all possible combinations.

# ? Jul 20, 2008 22:20

Smackbilly: Jan 3, 2001; What kind of a name is Pizza Organ! anyway?

Brackhar posted:

So that seems the fairly obvious way to approach it, but what's the underlying mechanism to handle the evaluations? Do you parse through the string and create a tree, do you use a stack, modify the string in place...? I thought about constructing a tree, but I worried that in a timed situation I'd not be able to do the insertions in the proper order to generate all possible combinations.

Iterating over every permutation is an O(n!) brute-force algorithm. It will work, but it will have an insanely long runtime for anything but the smallest inputs.

I'm writing a solution to this problem because I'm bored and it's interesting, and here's the dynamic programming setup that I came up with:

Parse the input set so that V(n) is the value of the nth integer, and OP(n) is the operator appearing after the nth integer. Let N be the number of integers in the equation. Now define a function Q such that:

Q(n,n) = V(n)
Q(n,m) = { All unique values you can get by parenthesizing terms n through m }

And then your solution is the value of Q(1,N). The remaining step in designing the algorithm is how do you compute Q(n,m) for an arbitrary m in terms of V, OP, and Q? After you figure that out, you're down to the implementation details of what data structures you use to store the value sof Q, V, and OP in a program.

I haven't done a full complexity analysis on this, but I'm fairly sure this ends up being pseudo-polynomial (polynomial in the size of the largest integer value that you can generate in a subterm). So it should be fast as long as the integers involved are small, even if there are a whole lot of terms.

# ? Jul 20, 2008 22:27

Brackhar: Aug 26, 2006; I'll give you a definite maybe.

Smackbilly posted:

Iterating over every permutation is an O(n!) brute-force algorithm. It will work, but it will have an insanely long runtime for anything but the smallest inputs.

I'm writing a solution to this problem because I'm bored and it's interesting, and here's the dynamic programming setup that I came up with:

Parse the input set so that V(n) is the value of the nth integer, and OP(n) is the operator appearing after the nth integer. Let N be the number of integers in the equation. Now define a function Q such that:

Q(n,n) = V(n)
Q(n,m) = { All unique values you can get by parenthesizing terms n through m }

And then your solution is the value of Q(1,N). The remaining step in designing the algorithm is how do you compute Q(n,m) for an arbitrary m in terms of V, OP, and Q? After you figure that out, you're down to the implementation details of what data structures you use to store the value sof Q, V, and OP in a program.

I haven't done a full complexity analysis on this, but I'm fairly sure this ends up being pseudo-polynomial (polynomial in the size of the largest integer value that you can generate in a subterm). So it should be fast as long as the integers involved are small, even if there are a whole lot of terms.

Hmmm... ok, I think I follow. Would you be at all willing to PM the solution to me when you get done with it? I never had any exposure to dynamic programming in undergrad, and I'd be interested to how the internal workings of such an approach are done. If not I think your summation and wikipedia give me a decent enough idea of how I could slog through it.

# ? Jul 20, 2008 22:32

The1ManMoshPit: Apr 17, 2005

quote:

references...dynamically sized piece of memory

While it isn't possible to create dynamically sized memory in a reference, people often forget that you can still use solely references to refer to objects on the heap. For instance you can do this:

code:

SomeObject& ref = *(new SomeObject());

    . . . . . . . .

delete &ref;

Which is admittedly pretty pointless except that you can avoid dereferencing syntax if it bothers you. However, it means you can do something slightly more useful like this:

code:

class RefExample
{
   SomeOtherObject& mRef;
public:
   RefExample(const tParams& params) 
    : mRef(SomeOtherObjectFactory::GetInstance()->CreateSomeOtherObject(params))
   {}
   ~RefExample() { mRef.Destroy(); }

  //other methods using mRef go here
};

Where the factory method returns a reference instead of the usual pointer which is neat, anyways, if not really all that different from just using a pointer. One caveat here is that you're basically up poo poo creek if memory allocation fails for whatever reason. While you could maybe recover in the second case by creating a default "SomeOtherObject" that indicates error (which is ugly), in the first case there is really no way to cleanly handle the out of memory error except through some ridiculous overloading of the new operator.

So yeah that's pretty pointless all around but it's something to keep in mind if you ever want to make your C++ code look more like java :haw:

# ? Jul 20, 2008 22:40

sarehu: Apr 20, 2007; (call/cc call/cc)

Ultimately somebody can always throw you one of these:

code:

0 - 0 + 1 - 0 + 3 - 0 + 27 - 0 + 81 - 0 + 243 - 0 + 729 - 0 + 2187

and there's nothing you can do about it.

Smackbilly posted:

I haven't done a full complexity analysis on this, but I'm fairly sure this ends up being pseudo-polynomial (polynomial in the size of the largest integer value that you can generate in a subterm).

That's right.

# ? Jul 20, 2008 22:43

Smackbilly: Jan 3, 2001; What kind of a name is Pizza Organ! anyway?

sarehu posted:

Ultimately somebody can always throw you one of these:
code:
0 - 0 + 1 - 0 + 3 - 0 + 27 - 0 + 81 - 0 + 243 - 0 + 729 - 0 + 2187
and there's nothing you can do about it.

code:

tyler@kusari ~ $ time ./parse
Enter unparenthesized equation: 0 - 0 + 1 - 0 + 3 - 0 + 27 - 0 + 81 - 0 + 243 - 0 + 729 - 0 + 2187
Unique results: -3271, -3269, -3265, -3263, -3217, -3215, -3211, -3209, -3109, -3107, -3103, -3101, 
-3055, -3053, -3049, -3047, -2785, -2783, -2779, -2777, -2731, -2729, -2725, -2723, -2623, -2621, 
-2617, -2615, -2569, -2567, -2563, -2561, -1813, -1811, -1807, -1805, -1759, -1757, -1753, -1751, 
-1651, -1649, -1645, -1643, -1597, -1595, -1591, -1589, -1327, -1325, -1321, -1319, -1273, -1271, 
-1267, -1265, -1165, -1163, -1159, -1157, -1111, -1109, -1105, -1103, 1103, 1105, 1109, 1111, 1157,
 1159, 1163, 1165, 1265, 1267, 1271, 1273, 1319, 1321, 1325, 1327, 1589, 1591, 1595, 1597, 1643, 
1645, 1649, 1651, 1751, 1753, 1757, 1759, 1805, 1807, 1811, 1813, 2561, 2563, 2567, 2569, 2615, 
2617, 2621, 2623, 2723, 2725, 2729, 2731, 2777, 2779, 2783, 2785, 3047, 3049, 3053, 3055, 3101, 
3103, 3107, 3109, 3209, 3211, 3215, 3217, 3263, 3265, 3269, 3271

real    0m6.004s
user    0m0.036s
sys     0m0.000s

Anyway, I'll put the solution code right in here because it's interesting/useful anyway and it's apparently not homework though it does make a really good dynamic programming exercise)

This is in C++. I know you were asking about ANSI C but I really didn't want to have to rewrite your standard map and set data structures when that's not really the point of this problem

code:

#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

enum Operation { Add, Subtract, Multiply, Divide };

int doOperation(int x, Operation op, int y) {
  switch(op) {
  case Add:
    return x + y;
  case Subtract:
    return x - y;
  case Multiply:
    return x * y;
  case Divide:
    return x / y;
  }
}

set<int> Q(uint n, uint m, map<uint, Operation> OP, map<uint, int> V) {
  static map<pair<uint,uint>, set<int> > cache;
  if (cache.find(make_pair(n,m)) != cache.end()) {
    return cache[make_pair(n,m)];
  }
  
  set<int> unique_results;

  if (n == m) {
    unique_results.insert(V[n]);
  } else {
    for (uint y = n; y < m; ++y) {
      set<int> results_n_to_y = Q(n,y,OP,V);
      set<int> results_yplus1_to_m = Q(y+1,m,OP,V);

      for (set<int>::iterator i = results_n_to_y.begin();
           i != results_n_to_y.end(); ++i)
        {
          for (set<int>::iterator j = results_yplus1_to_m.begin();
           j != results_yplus1_to_m.end(); ++j)
            {
              unique_results.insert(doOperation(*i, OP[y], *j));
            }
        }
    }
  }

  cache.insert(make_pair(make_pair(n,m), unique_results));
  return unique_results;
}

int main()
{
  string input;
  map<uint, Operation> OP;
  map<uint, int> V;
  set<int> results;

  cout << "Enter unparenthesized equation: ";
  getline(cin, input);

  string::size_type nextNonWS = input.find_first_not_of(" ", 0);
  string::size_type nextWS = 0;
  int n = 1;
  bool expectNumber = true;
  string token;
  
  while(nextNonWS != string::npos) {
    nextWS = input.find_first_of(' ', nextNonWS);
    token = input.substr(nextNonWS, nextWS - nextNonWS);
    if (expectNumber) {
      V.insert(make_pair(n, atoi(token.c_str())));
    } else {
      if (token.size() > 1) {
        cerr << "Multi-character operator!" << endl;
        return -1;
      }
      Operation op;
      switch (token[0]) {
      case '+':
        op = Add;
        break;
      case '-':
        op = Subtract;
        break;
      case '*':
        op = Multiply;
        break;
      case '/':
        op = Divide;
        break;
      default:
        cerr << "Unknown operator!" << endl;
        return -1;
      }
      OP.insert(make_pair(n, op));
    }

    if (!expectNumber) n++;
    expectNumber = !expectNumber;
    nextNonWS = input.find_first_not_of(" ", nextNonWS + token.size());
  }
  
  results = Q(1, V.size(), OP, V);

  cout << "Unique results: ";
  for (set<int>::iterator i = results.begin(); i != results.end(); ++i)
    {
      if (i != results.begin()) {
        cout << ", ";
      }
      cout << *i;
    }

  cout << endl;

  return 0;
}

This is dynamic programming, so the point is that you start by computing small sub-problems, and then save their solutions to later use them to solve large subproblems. The largest subproblem, of course, is the whole problem.

The algorithm, like I posted before, is this:

quote:

Parse the input set so that V(n) is the value of the nth integer, and OP(n) is the operator appearing after the nth integer. Let N be the number of integers in the equation. Now define a function Q such that:

Q(n,n) = V(n)
Q(n,m) = { All unique values you can get by parenthesizing terms n through m }

The missing piece is:

Q(n,n+1) = { V(n) OP(n) V(n+1) }
Q(n,n+k) = { x OP(y) z | n <= y < n+k, x in Q(n,y), z in Q(y+1, n+k) }

Here, our subproblems are continuous runs of adjacent terms. We start with single terms, then we use those answers to build the answers to pairs of terms, then we use those answers to build the answers to four terms in a row, etc, etc.

In english, the above equations for Q mean:

1. The only possible result from parenthesizing a single term is itself, so Q(n,n) = V(n).

2. The only possible result from parenthesizing a pair of terms is the operation between them performed on the two terms, so Q(n,n+1) = { V(n) OP(n) V(n+1) }

3. The possible results for parenthesizing terms n through n + k are computed as follows: For each term y between n and n + k, consider all of the possible results for parenthesizing the terms n to y and y+1 to n+k. For each pair of possible results, one from the left and one from the right, perform OP(y) on these results and add them to the set of possible results for parenthesizing n to n+k, excluding duplicates.

The code above simply implements this definition of the function Q, and caches the results so that no sub-problem is computed more than once (Note that in C++, sets automatically eliminate duplicates). Then, main just parses the input string into terms and operations, and calls Q(1,N) to get the answer set.

# ? Jul 20, 2008 23:08

more falafel please: Feb 26, 2005; forums poster

Entheogen posted:

code:

#define FOREACH(_it,_l) for(__typeof((_l).begin()) _it=((_l).begin());(_it)!=(_l).end();(_it)++)

You don't even need BOOST_FOREACH for this, just use std::for_each. It'll work for anything that has a T::iterator type (and begin(), end() and operator++ on the iterator), and makes way more sense than using the macro version.

# ? Jul 21, 2008 08:54

Zombywuf: Mar 29, 2008

Entheogen posted:

I used pointers before to switch between two arrays that contain same types.

such as
code:
vector< int > A, B;
vector<int> * curr = & A;
while( true )
{
   // do something 
   if( curr == & A ) curr = &B;
   else curr = &A;
}
Is there a better way of doing this without pointers? Or is this fine. Also in this case the pointer, is of course, pointing to something on a stack, right?

std::swap will usually be optimised to do this internally, i.e. it woun't copy the contents of the vectors, just swap the pointers to the internal arrays. It's also better from a readability perspective, i.e. swap(A, B) does what it says.

# ? Jul 21, 2008 10:01

floWenoL: Oct 23, 2002

Zombywuf posted:

std::swap will usually be optimised to do this internally, i.e. it woun't copy the contents of the vectors, just swap the pointers to the internal arrays. It's also better from a readability perspective, i.e. swap(A, B) does what it says.

Just a nitpick, but you mean A.swap(B). I'm not sure if there's a specialized version of swap(A, B) for vectors, but it's worth noting that if it is, with ADL it is not std::swap that will be called (which is good as std::swap works by copying) unless you do std::swap(A, B).

# ? Jul 21, 2008 10:51

Mustach: Mar 2, 2003; In this long line, there's been some real strange genes. You've got 'em all, with some extras thrown in.

floWenoL posted:

I think I would kill myself if I had to define a new functor every time i wanted loop with an iterator (or deal with C++'s bastardized version of functional programming).

Entheogen's example in his question was just calling a member function, though.

# ? Jul 21, 2008 12:22

Entheogen: Aug 30, 2004; by Fragmaster

Zombywuf posted:

std::swap will usually be optimised to do this internally, i.e. it woun't copy the contents of the vectors, just swap the pointers to the internal arrays. It's also better from a readability perspective, i.e. swap(A, B) does what it says.

does it copy in the example I had? I thought that the pointer just changed address from either A or B. I didn't realize it was copying their entire contents each time I did curr = & A

# ? Jul 21, 2008 14:58

TSDK: Nov 24, 2003; I got a wooden uploading this one

Entheogen posted:

does it copy in the example I had?

No, it doesn't. I'd be tempted to do something like this though:

code:

std::vector<int> vecs[2];
int current_vector = 0;
while ( some_condition )
{
    // Get a reference to the current vector for convenience
    std::vector<int> &vec = vecs[current_vec];

    // Use vec
    ...

    // Swap currently active vector
    current_vec = 1 - current_vec;
}

I personally think that makes it a bit clearer that you're alternating between the two different vectors, and by having the reference variable 'vec' in the loop, you're making it clear that it's just there to refer to one of a possible set of vectors, and not for any other purpose.

# ? Jul 21, 2008 15:21

Zombywuf: Mar 29, 2008

floWenoL posted:

Just a nitpick, but you mean A.swap(B). I'm not sure if there's a specialized version of swap(A, B) for vectors, but it's worth noting that if it is, with ADL it is not std::swap that will be called (which is good as std::swap works by copying) unless you do std::swap(A, B).

I'd assumed the inclusion of using std::swap somewhere in the scope. ADL will mean that swap will work for anything which specialises it in its own namespace. In this case however, swap is being specialised in std (presumably by vector), meaning it is still std::swap however you look at it.

This code says it is specialised in g++:

code:

#include<iostream>
#include<vector>

class A {
public:
  A(){}
  A(const A &a) { std::cout << "Copying" << std::endl; }
};

int main() {
  using std::vector; using std::swap;
  using std::cout; using std::endl;
  vector<A> a(10), b(10);
  cout << "Starting swap" << endl;
  swap(a, b);
  cout << "Finished swap" << endl;
}

Entheogen posted:

does it copy in the example I had? I thought that the pointer just changed address from either A or B. I didn't realize it was copying their entire contents each time I did curr = & A

Your code doesn't copy, my point was that std::swap does it in a cleaner way.

# ? Jul 21, 2008 15:33

Insurrectum: Nov 1, 2005

If you've read through and understand all of the material in Accelerated C++, about how good of an understanding will you have of the language? I've read through most of the book and I feel like I can use the language now, but is there anything really critical that's left out knowledgewise?

# ? Jul 21, 2008 16:53

Lexical Unit: Sep 16, 2003

Ok, so I'm using private inheritance and promoting the methods I want to expose in the base class with using directives (did I get those technical terms correct?) but I'm a bit confused about one thing.

Say I want to expose only the const version of a method, how do I do that? This doesn't work: using base::operator[] const;, and using base::operator[]; exposes both the const and non-const methods.

Is there a common workaround for this or is my syntax wrong?

\/\/ Oh well, that's what I thought. I was kinda hoping there was some c++ dark magic I could use to accomplish this.

Lexical Unit fucked around with this message at 20:27 on Jul 21, 2008

# ? Jul 21, 2008 16:57

That Turkey Story: Mar 30, 2003

Lexical Unit posted:

Ok, so I'm using private inheritance and promoting the methods I want to expose in the base class with using directives (did I get those technical terms correct?) but I'm a bit confused about one thing.

Say I want to expose only the const version of a method, how do I do that? This doesn't work: using base::operator[] const;, and using base::operator[]; exposes both the const and non-const methods.

Is there a common workaround for this or is my syntax wrong?

You can't. You need to make a wrapper function.

# ? Jul 21, 2008 18:13

floWenoL: Oct 23, 2002

Zombywuf posted:

Your code doesn't copy, my point was that std::swap does it in a cleaner way.

Unless someone overrode operator& for vectors somewhere before. :q:

# ? Jul 21, 2008 20:41

Vanadium: Jan 8, 2005

floWenoL posted:

Unless someone overrode operator& for vectors somewhere before.

Just use boost::addressof!!

# ? Jul 21, 2008 20:44

Entheogen: Aug 30, 2004; by Fragmaster

floWenoL posted:

Unless someone overrode operator& for vectors somewhere before.

I don't understand. Is not & a referencing operator. So it gets you address of whatever it is on its right? What is going on here, I am getting confused.

vvvvvvvvvvvvvvvvvvvvvv OK, so STL overloaded & operator for vectors to copy them?

Entheogen fucked around with this message at 23:06 on Jul 21, 2008

# ? Jul 21, 2008 21:29

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Entheogen posted:

I don't understand. Is not & a referencing operator. So it gets you address of whatever it is on its right? What is going on here, I am getting confused.

You can overload it to make it do whatever you want. That's what operating overloading means.

# ? Jul 21, 2008 21:32

Vanadium: Jan 8, 2005

Entheogen posted:

OK, so STL overloaded & operator for vectors to copy them?

No, but if floWenoL did, the STL code might not work anymore.

# ? Jul 22, 2008 00:19

Adbot: ADBOT LOVES YOU

# ? Apr 29, 2024 06:12

Vanadium: Jan 8, 2005

(This is becaue floWenoL hates the STL and likes to break it)

# ? Jul 22, 2008 03:39

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

«‹›639 »

Ugg boots posted:

Lexical Unit posted:

UberJumper posted:

UberJumper posted:

UberJumper posted:

UberJumper posted:

UberJumper posted:

UberJumper posted:

Avenging Dentist posted:

quote:

quote:

quote:

Centipeed posted:

UberJumper posted:

code:

code:

code:

quote:

Entheogen posted:

code:

quote:

code:

quote:

code:

Brackhar posted:

Entheogen posted:

Entheogen posted:

code:

code:

Smackbilly posted:

Brackhar posted:

code:

Avenging Dentist posted:

code:

Brackhar posted:

Smackbilly posted:

quote:

code:

code:

code:

Smackbilly posted:

sarehu posted:

code:

code:

code:

quote:

Entheogen posted:

code:

Entheogen posted:

code:

more falafel please posted:

Zombywuf posted:

floWenoL posted:

Zombywuf posted:

Entheogen posted:

code:

floWenoL posted:

code:

Entheogen posted:

Lexical Unit posted:

Zombywuf posted:

floWenoL posted:

floWenoL posted:

Entheogen posted:

Entheogen posted: