Posts by arkoenig

You say:

/*When the object in cars[x] is a TaxiVehicle, only the information held in regVehicle is printed. NOTE also that 'point1' in never reached when the program is run */

but you never show any actual code that proves it. How do the values get into cars[0], cars[1], etc? What actually happens when you run the code?

If your problem is really what you say it is, you should be able to say

Vehicle* v = new TaxiVehicle(appropriate arguments);
v->print();

and have it do the wrong thing. But so far all we have is your unsupported claim that it doesn't work.

Please post a small, complete test case that fails.

Again, I see nothing in your code that suggests that there should be any problem.

Can you post a short example of what is going wrong?

It's hard to believe that this is your actual code, because you don't declare a return type for any of your print functions. I see no reason why calling print on a pointer to a C object should call anything but C::print, so I can only conclude that your problem lies in the difference, whatever it might be, between your actual code and what you posted.

You'd be better off using std::copy than memcpy.

I should point out that there are some fairly subtle problems with your code, in the sense that it often constructs objects with default values and then assigns new values to them. This behavior is often invisible, but does slow things down. It's a bit of a pain to avoid unless you use the allocators and deallocators from the standard library. It's somewhat self-serving to say so, but you can find a detailed description of how to implement vectors in a way that avoids this problem in Accelerated C++.

Anyway, I stand by my implicit claim about the bug in line 75: That isn't just a matter of efficiency; it's a matter of correctness.

I don't know what line the compiler doesn't like, but I'm guessing it's line 13. I'm also guessing that poke returns a reference to const (i.e. a reference to an object that you have promised not to change), but you're trying to bind a plain reference to it in the definition of p.

If my guess is correct, you need to change line 13 to say:

const PokeBattle &p = this->poke(player,slot);

If not, then I would need more context in order to advise you.

Without seeing the relevant code in its current form, it's hard to guess what the problem might be.

Well, yeah.

Line 7 defines situation as a reference to an object of type BattleSituation that you have promised not to change (because you defined it as a reference to const).

Line 9 calls the getHPData member of situation. That member is permitted to change the value of its object because you did not promise not to do so. To make that promise, you would have to make line 1 look like this:

int BattleSituation::getHPData(int player, int slot) const

and change the definition of class BattleSituation analogously.

Shouldn't line 75 be assigning to data, not data[size-1]?

Also, what does Q_memcpy do? That's anot a standard function, and you don't include its definition.

You've been studying this subject for two years. Surely you must be able to do something.

So how about showing us how much of your program you've written successfully. Then you might get a hint as to what to do next.

Are there any steps I can take while coding any function that will make it better?

Make it as simple as possible. That makes it easier to measure, and also easier to optimize the hot spots that the measurement reveals.

There are no 2D vector types in standard C++. There are only vectors of vectors (or vectors of maps, or whatever).

Step 1. Understand the problem thoroughly.

Step 2. Realize that I was really serious about step 1, and go back and understand the problem even more thoroughly.

Step 3. Write the clearest, most straightforward program you can that solves the problem correctly.

Step 4. Measure your program's performance. If you're satisfied with the results of your measurements, you're done.

Step 5. Your measurements will tell you what part(s) of your program are spending the most time. Rewrite those parts to make them faster. The most effective rewriting strategy will often be to find a way to avoid computing the same result more than once, or to find a more efficient algorithm. Now go back to step 4.

My experience is that many programmers will omit one or more of these steps in an effort to get the job done more quickly. Most of the time, doing so will have the opposite effect from what you intended.

I continue to believe that the first example that the OP cited is the most interesting.

Once you understand enough to be able to write a program that evaluates "2 - 3 * 4 + 2" as -8 instead of -2, parentheses are easy.

Please post the code you have written so far, and explain what problems you having in getting it to work.

Switch-case statements will work fine.

However, if you think that the hard part of the problem is deciding what kind of statement to use to detect parentheses, then I think you do not understand the problem.

I also think that before you start worrying about parentheses, you write a program that can handle the first of the examples correctly. In other words, write a program that can accept "2 - 3 * 4 + 2" as its input and give -8 as its result.

OK, you don't get the parentheses part. So how about writing a program to do the rest of it and posting it when you're done? If you do that, I'm sure someone will give you a hint about how to do the rest of it.

As it is, you're just asking people to do your homework for you, without evidence that you've done any of it yourself.

int* array_end = array_begin;
for (register int i = 0; i < len; i++) array_end++;

This is a pointlessly roundabout (and slow) way of writing

int* array_end = array_begin + len;

More generally, what is the point in posting a bubble sort that works only on arrays of integers? The C++ standard library already contains a much faster sorting algorithm that works on any data structure that has an associated random-access iterator, and on any element type with a corresponding strict weak ordering.

The first function is riddled with errors:

1) It is missing two right curly braces.

2) Its parameter is named h but the body of the function uses an otherwise undefined variable named head.

3) The loop goes through only one iteration.

4) The code compares the pointer named current with 0, rather than comparing the contents of the node with 0.

5) The parameter is a Node* rather than a const Node*, even though there is no need for the function to modify the contents of any node.

The second function shares errors (2) and (5) with the first function. In addition, there is a subtle algorithmic disadvantage to what I think is the approach you're trying to follow, which is to compute the length of each list and then compare the lengths. The trouble with this approach is that if one of the lists is much longer than the other -- say, one has 10 elements and the other has 1,000,000 elements, your program will march out to the ends of both lists even though it really needed only to determine that the longer list had only a single element.

One way to solve this problem is to have two pointers that you step together each time through a single loop. As soon as either of them reaches the end of the list, you have your answer; it depends only on which pointer got to the end first (or whether they …

I gave a new programmer's algorithm, one that will suffice for homework, not a mathematically perfect distribution. That is above the needs for a beginning programming class.

I completely disagree. As a practical matter, whether the original algorithm suffices for homework depends on the instructor. If I were the instructor, it certainly would not suffice.

As a philosophical matter, I think that as a general rule, it's a bad idea to advocate solutions that don't solve the stated problem correctly, and an even worse idea to do so without pointing out that the solution is oversimplified and doesn't actually yield the right answer.

As for the use of random_shuffle, I have three comments:

1) I didn't recommend it because I assumed that the OP would have used it if permitted.

2) Even if not, random_shuffle is geared toward linear data structures, not rectangular ones. It is true that you can treat an array of arrays as a linear data structure, but I believe that the subtleties of doing so are even greater than the subtleties of getting the code right in the first place. In fact...

3) The call to random_shuffle in the previous example is just plain wrong, for two reasons:

3a) The indices are wrong. If you want to use random_shuffle on the whole array, you have to pass an address that is one past the last element. That is &a[3][3], not &a[4][3]. Think about it.

3b) Unfortunately, even computing &a[3][3] …

b. “Algorithm P” which Knuth attributes to Moses and Oakford (1963), but is now known to have been anticipated by Fisher and Yates (1938); the 'Fisher–Yates shuffle' http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

I believe the algorithm I suggested is equivalent to the one shown on this page under the heading "The Modern Algorithm."

Just some skeleton to help you visualize whats been said above :

for row = 0 to ROW_SIZE
    for col = 0 to COL_SIZE
         int rowToSwap  = a random valid row
         int colToSwap    = a random valid col
         swap array[row][col] with array[rowToSwap][colToSwap]

This is not quite right: You need to restrict the swapping so that the destination position is always >= the source position.

int rowToSwap = a random valid row that is >= row
int colToSwap = rowToSwap == row?
    a random valid row that is >= col :
    a random valid row

To see why, consider what happens if there are only two elements in the array using the original strategy. We look at the first element and swap it with the second with probability 0.5. Then we look at the second and swap it with the first with probability 0.5. The net effect is to keep the original ordering 3/4 of the time. Not a random distribution.

I hate to sound smug, but this is not a difficult problem. In effect, you have a string of 0's and 1's that you want to treat as a binary number, and you want to add 1 to it repeatedly.

Adding 1 to a binary number is easy: Take all the consecutive 1's at the low-order end, change them to 0, and change the 0 immediately before that to 1. As an example, consider 001010110100111. There are 3 1's at the low-order end, so you change them to 0's and change the 0 before that to 1, yielding 001010110101000.

Let's see how this process works for three digits.

You start with 000. There are no 1's at the end, so there's nothing to change; but you have to change the 0 before that empty string of 1's to a 1, yielding 001.

For 001, you have to change the 1 at the end to 0 and the 0 before that to 1, giving 010. The next steps yield 011, 100, 101, 110, and 111 in turn.

At the last step, you would have to change all the 1's to 0, but there's no 0 before that so you can't complete the process. That is your signal that you are done.

Of course, as others have pointed out, the number of steps you will have to go through is 2^n where n is the number of bits in your number. This gets out of hand rather quickly. Nevertheless, this description shows how to do it if you have time.

Take each element of your array in turn, and swap it with a randomly chosen element with a position that is >= the one you're swapping. Note that this raises the possibility that an element may be swapped with itself; if it is, that's equivalent to leaving that element alone.

It should be easy to see that after this is done, the first element can be swapped with any element in the array with equal probability. Applying this argument inductively shows that each element has equal probability of winding up in any spot in the array.

In the last section of code you posted, you are referring to DetectedFaces[j]. If TrackingFaces has more elements than DetectedFaces, at some point j will be >= DetectedFaces.size(). When that happens, DetectedFaces[j] is an out-of-range subscript.

You haven't told us the type of the elements of temp or DetectedFaces.

I see nothing technically wrong with the original code, which suggests that the problem is elsewhere.

However, the code is unnecessarily complicated and can also be very slow if the DetectedFaces vector is large. Moreover, it destroys the DetectedFaces vector, which may or may not be what you want.

A much easier solution:

temp.insert(temp.end(), DetectedFaces.begin(), DetectedFaces.end());

I will ask some questions that should help you solve your problem--if you answer them.

Here are the first three questions:

1) How many different moves are possible from the starting position?

2) Once you have made the first move, how many different moves are possible from the position that results?

3) More generally, how many different moves are possible from an arbitrary position? How does that number depend on the nature of the position?

When you have answered these three questions correctly, I will ask some more questions. If you cannot answer them, that means that you do not understand the problem well enough to begin solving it.

You're doing a division in line 8. Can you prove that the divisor is never zero?

Before you spend too much time trying to find faster ways of copying vectors, you might give some thought to whether (and, if so, why) copying is a significant part of your program's total execution time.

After all, if you're copying a vector, presumably you need two copies, so you're doing something different to one copy than you are to the other. Are you sure that whatever else you're doing to those vectors isn't going to take longer than copying them? After all, copying is just about the simplest operation one can imagine. So if it's really the performance bottleneck, maybe you can rethink your algorithm to avoid it altogether.

Yeah but the function is recursive and is supposed to call itself until eventually it returns something.

Yeah but you're doing it wrong.

Every call, including recursive calls, must have a matching return. If any of these calls causes the "if" test in line 9 to be true, the corresponding return causes undefined behavior. The entire program could potentially do anything at all after that.

I really don't want to debate this. The code is broken, and there is no point in looking for any other problems until this one is fixed.

If the "if" statement that is the subject of the else in line 9 yields true in its test, then the function falls off the end without executing a return statement. The value that the function returns in that case is undefined.

There was an extended debate in the C++ standards committee about whether the standard library should be required to support recursive data structures. The simplest case:

struct T {
    vector<T> vt;
};

There is no technical reason why this should not be possible, but implementing it is quite difficult, and in the end, the committee decided that C++ implementations should not be required to do so.

So if your implementation happens to support the kind of mutual recursion we are discussing here, that's just a stroke of luck; another implementation might not be so generous.

The pointer solution adds memory-management problems, so perhaps some kind of smart pointer class (such as auto_ptr) might be in order. Despite the complexity of such solutions, they are the only way that I can think of to be assured of portability when you want to implement such recursive data structures.

On line 15, you define a variable named "word." Because that is a string variable, it is automatically initialized to an empty string--that is, a string with no characters in it.

I do not see any place in the code you posted where you give a different value to that variable, which means that it is always going to be an empty string.

In line 20, you execute the statement word[l]='_', which is legitimate only if word has at least "l" characters in it. But we have already established that word does not have any characters in it. Therefore, this statement will always fail.

In line 20, change "_" to '_'

How about posting your compare function? That seems to me to be the most likely cause of the problem.

Why are you bothering to write your own sort instead of using std::stable_sort?

pA->B::runAlg()

Ah. You have a set of pointers and a comparison function that compares pointers. (Incidentally, the comparison function you provided in your example won't compile, so I assume you've made it right in your actual code)

No problem. For a set<T>, the key type is just T. So if you have a set of pointers and want to call upper_bound, you have to hand it a pointer.

So... Use "new" to allocate an object of type c, with its p member initialized to the value for which you want to search. Pass that pointer as an argument to upper_bound. If it's appropriate, delete the object after upper_bound has returned.

Why not define a third parameter to your addMap function:

// I changed the return type to void because you don't use the return value
void addMap(strMap& mymap, string Fname, string Lname)
{   // where Fname and Lname are strings entered by the user
    // in main that hold someone first and last names respectively.
    mymap[Fname] = Lname;
}

And then you can add an element to the map m by calling addMap(m, Fname, Lname).

The question remains as to why you would be using char arrays instead of strings for Fname and Lname, but you didn't ask about that :-)

Sets are ordered based on the comparison function that you supply. So when you call upper_bound, what you get is an iterator referring to a position in the set that is based on calling the comparison function. If your comparison function compares based on a member variable, then that's what you get.

If that isn't what you want, then you need to explain what you're trying to do in more detail, along with code examples.

The trouble is that the general technique of picking random numbers and seeing if they're prime is not guaranteed to terminate. For example, if "result" is 2, then there isn't any prime number less than it.

And why does the prime number you pick need to be random? After all, if "result" is greater than 2, then 2 is a prime number that is less than result. What do you hope to gain by this randomness?

I think you'd be better off learning to understand Euclid's Algorithm.

You might try looking here.

I could tell you that functional programming (FP) is a style of programming in which one never changes a value that has already been computed. Instead, one creates new values as needed. By implication, using FP in practice requires a good garbage collector in order to get rid of values that are no longer needed.

Here's a simple example in C:

int factorial (int n) {
    int result = 1;
    while (n > 1) {
        result *= n;
        --n;
    }
    return result;
}

This code does not use FP, because it has the side effect of modifying the variables named n and result each time through the loop.

It is possible to achieve the same effect in an FP style, even in C, as follows:

int factorial(int n) {
    if (n <= 1)
        return 1;
    return factorial(n-1) * n;
}

You will see that in this second example, no variable is ever changed after being given its initial value, so there are no side effects.

The foregoing explanation is grossly oversimplified, and I can think of no short way to explain why FP is important or useful, but this is a start.

As for your other questions:

There are several programming languages in widespread use that make FP easy (or sometimes even necessary). The three best known are probably Lisp (particularly its Scheme dialect), Haskell, and SML. There are substantial differences between the three languages, but it's not easy to explain those difference …

1. I see nothing wrong with your code.
2. Yes.
3. It's up to the compiler whether a1 and a2 share the same string constant.

OK, here's a trick. The hard part, as you will see, is figuring out how to unify the comparisons--i.e., to make the comparisons the same for each loop. So let's start in that direction by changing the comparison to inequality comparisons:

if (flag)
    for (i = 0; i != 10; i++)
        {LARGE_BLOCK_OF_CODE (that visits an array in order)}
else
    for (i = 9; i != -1; i--)
        {LARGE_BLOCK_OF_CODE (that visits an array in REVERSE order)}

Now let's unify the increment/decrement statements:

if (flag)
    for (i = 0; i != 10; i += 1)
        {LARGE_BLOCK_OF_CODE (that visits an array in order)}
else
    for (i = 9; i != -1; i += -1)
        {LARGE_BLOCK_OF_CODE (that visits an array in REVERSE order)}

Now the form of our two for statements is identical except for the values of three constants. So we can unify them by making those constants into variables:

int start, end, direction;

if (flag) {
    start = 0;
    end = 10;
    direction = 1;
} else {
    start = 9;
    end = -1;
    direction = -1;
}

for (i = start; i != end; i += direction)
    {LARGE_BLOCK_OF_CODE (that visits an array in the specified order)}

Compared to swapping by using 3 variables, this is akin to MOV operations on the processor which are generally more expensive than XOR operations.

Really? Why do you think so?

An assignment requires one fetch and one store. An XOR requires two fetches, one store, and the XOR operation itself. So why do you think that three XOR operations would be faster than three assignments?

I'm sticking with my last suggestion:

Before you ask other people to spend time reading and discussing code you have written, that you first take the trouble to (1) explain what you expect the code to do and why you are writing it, and (2) verify that the code actually compiles and does what you claim it does.

The easiest way to improve it is to throw it out and use the queue implementation from the standard library. Why reinvent the wheel?

If your purpose in writing this code is as an exercise, rather than to do something that you intend to be useful, then I don't understand how you got this code to compile. Line 15 is not valid C++, and lines 34 and 41 make no sense. I can guess what you intended them to do, but they don't do that.

Despite your name of Queue, the code you have written appears to implement a stack, not a queue. I say "appears" because it's not hard to find errors in the code--though it would be easier if it were possible to compile the code in the first place.

I would like to suggest that before you ask other people to spend time reading and discussing code you have written, that you first take the trouble to (1) explain what you expect the code to do and why you are writing it, and (2) verify that the code actually compiles and does what you claim it does.

Depends on what you're trying to do.

If you just write something like

input_file >> var;

then your program will normally stop reading as soon as it finds a space, which means that it will read only a single word no matter what type var has. If, on the other hand, you write

std::string line;
getline(input_file, line);

then it will read an entire line of input into the string named "line", and after that you can do as you like with it.

The phrase "the first cell of country_name[20]" is meaningless, because the expression country_name[20] is not something that has cells.

So I think you need to go back and understand what C++ expressions mean, and what types they have.

What I'm trying to say is that I'm not going to solve your problem for you. I've shown you where it is, and now it's your job to understand what's going on and how to solve it.