• Home   /  
  • Archive by category "1"

Assignment Operator C Swapper

Swapping in
C, C++, and Java


Parameters, by value and by reference: Both C and Java use only parameters that pass by value, which means that the value of the actual parameter is used to initialize the formal parameter. For simple variables C allows one to pass the address of the variable explicitly. (Java does not allow this.) This is sometimes called passing a parameter by reference. C++ allows this also, but C++ also allows an implicit pass by reference, which will be described at the end of this writeup.

In C, the mechanism above is what is used for parameters in the function, which have the extra (the "address of" operator) in front of them.


A swapping values: In C and in Java, we can always swap values with the use of three assignment statement and no function or paramters. The code on the left shows this, while the code on the right shows how the same task can be accomplished using the C exclusive-or operator . (Notice that is this case you don't need the variable .)

C Simple Swap Program -- AssignmentsC Simple Swap Program -- Exclusive-Or
#include <stdio.h> int main() { int a = 23, b = 47; int t; printf("Before. a: %d, b: %d\n", a, b); t = a; a = b; b = t; printf("After. a: %d, b: %d\n", a, b); return 0; } #include <stdio.h> int main() { int a = 23, b = 47; printf("Before. a: %d, b: %d\n", a, b); a ^= b; b ^= a; a ^= b; printf("After. a: %d, b: %d\n", a, b); return 0; }
Runs of the two programs
% cc -o swap_simple0 swap_simple0.c % swap_simple0 Before. a: 23, b: 47 After. a: 47, b: 23 % cc -o swap_simple1 swap_simple1.c % swap_simple1 Before. a: 23, b: 47 After. a: 47, b: 23


A swapping function: To understand how explicit pass by reference of parameters works in C, consider implementing a function in C, that is, a function that passes in two variables and swaps their values. The code on the left below shows one failed attempt at an implementation. The code on the right uses pointers, that is, explicitly passes the address of variables, and manipulates the numbers that are at that address, using the operator (the "dereference" operator that fetches the contents of the given address).

C Swap Program -- FailsC Swap Program with Pointers -- Works
#include <stdio.h> void swap(int i, int j) { int t = i; i = j; j = t; } int main() { int a = 23, b = 47; printf("Before. a: %d, b: %d\n", a, b); swap(a,b); printf("After. a: %d, b: %d\n", a, b); return 0; } #include <stdio.h> void swap(int *i, int *j) { int t = *i; *i = *j; *j = t; } void main() { int a = 23, b = 47; printf("Before. a: %d, b: %d\n", a, b); swap(&a, &b); printf("After . a: %d, b: %d\n", a, b); }
Runs of the two programs
% cc -o swap0 swap0.c % swap0 Before. a: 23, b: 47 After. a: 23, b: 47 % cc -o swap1 swap1.c % swap1 Before. a: 23, b: 47 After. a: 47, b: 23

With the program on the left, no swapping took place. The values of and are passed to , and the function does swap them, but when the function returns, nothing has changed in the function.

To get an idea of what this code does, print it out, draw the two integers and , and enter and in them. Now draw the two pointers and , along with the integer . When is called, it is passed the addresses of and . Thus, points to (draw an arrow from to ) and points to (draw another arrow from to ). Once the pointers are initialized by the function call, is another name for , and is another name for . Now run the code in . When the code uses and , it really means and . When the function completes, and have been swapped.

Suppose you accidentally forget the when the function is called, and that the swap line accidentally looks like this: . This causes a segmentation fault. When you leave out the , the value of is passed instead of its address. Therefore, points to an invalid location in memory and the system crashes when is used.

This is also why crashes if you forget the on variables passed to it. The function is using pointers to put the value it reads back into the variable you have passed. Without the , is passed a bad address and crashes. Reference parameters are one of the most common uses of pointers in C. Another way to say this is to say that the calling function is telling the called function where to find the variable.


Swapping in Java: The swapping just above using reference parameters in C doesn't work in Java, since Java doesn't have these kind of parameters, but often an application really only needs to swap two values in an array. In this case one can pass the array and the two indexes to swap as three parameters, and this will work in Java. The "bubble sort" program below illustrates this.

Java BubbleSort ProgramRun of the Program
public class BubbleSort { // swap: interchange inside array static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } // bubbleSort: very short code, but ineffient static void bubbleSort(int[] a) { for (;;) { boolean sorted = true; for (int i = 0; i < a.length - 1; i++) if (a[i] > a[i+1]) { sorted = false; swap(a, i, i + 1); } if (sorted) break; } } static void printArray(int[] a) { for (int i = 0; i < a.length; i++) { if (i%4 == 0) System.out.println(); System.out.print(a[i] + " \t"); } System.out.println(); } public static void main(String[] args) { int size = Integer.parseInt(args[0]); System.out.println("Bubblesort, size = " + size); int[] r = new int[size]; for (int i = 0; i < size; i++) r[i] = (int)(Math.random()*size*10 + 1); long startTime =System.currentTimeMillis(); bubbleSort(r); System.out.println("Elapsed time(millis) "+ (System.currentTimeMillis()-startTime)); // printArray(r); } } % javac BubbleSort.java % java BubbleSort 60 Bubblesort, size = 60 Elapsed time (millis) 1 5 7 9 18 21 27 41 44 67 104 104 109 116 118 151 151 170 175 181 182 196 196 207 220 231 240 241 242 244 247 251 274 279 290 302 325 329 339 341 363 366 369 376 380 385 411 435 440 471 484 492 504 505 547 556 559 564 583 588 591 % java BubbleSort 100 Bubblesort, size = 100 Elapsed time (millis) 3 % java BubbleSort 1000 Bubblesort, size = 1000 Elapsed time (millis) 394 % java BubbleSort 10000 Bubblesort, size = 10000 Elapsed time (millis) 39518 % java BubbleSort 20000 Bubblesort, size = 20000 Elapsed time (millis) 158317 % java BubbleSort 40000 Bubblesort, size = 40000 Elapsed time (millis) 646717


Swapping in Java Using Wrapped Integers: In Java we can get the function to work if we use wrapped integers and pass references to them to the function. However, the Java wrapper class for is and it doesn't allow you to alter the data field inside. Thus we need our own wrapper class, which I have called below. The program here is only presented as what could be done, not as an example of how to do swaps. If one passes the address of an object to a function, then changes to the inside of that object will persist after returning from the function

Java Swapping Using a Wrapper Class
// MyInteger: similar to Integer, but can change value class MyInteger { private int x; // single data member public MyInteger(int xIn) { x = xIn; } // constructor public int getValue() { return x; } // retrieve value public void insertValue(int xIn) { x = xIn;} // insert } public class Swapping { // swap: pass references to objects static void swap(MyInteger rWrap, MyInteger sWrap) { // interchange values inside objects int t = rWrap.getValue(); rWrap.insertValue(sWrap.getValue()); sWrap.insertValue(t); } public static void main(String[] args) { int a = 23, b = 47; System.out.println("Before. a:" + a + ", b: " + b); MyInteger aWrap = new MyInteger(a); MyInteger bWrap = new MyInteger(b); swap(aWrap, bWrap); a = aWrap.getValue(); b = bWrap.getValue(); System.out.println("After. a:" + a + ", b: " + b); } }
% javac Swapping.java % java Swapping Before: a: 23, b: 47 After: a: 47, b: 23


Swapping in C++: Of course the C swapping methods will work in C++ also, but C++ has the very important concept of references, which we probably won't study in this course. However, below is a C++ swap program using this feature. Notice that the code for the actual swap is simple: . In a similar way, the simple form of C++ input, such as requires these kind of parameters.

C++ Swap Program Using References
#include <iostream> using std::cout; void swap(int& i, int& j) { int t = i; i = j; j = t; } int main() { int a = 23, b = 47; cout << "Before. a: " << a << ", b: " << b << "\n"; swap(a, b); cout << "After. a: " << a << ", b: " << b << "\n"; return 0; }
Run of the program
% CC -o swap_CC swap.cpp % swap_CC Before: a: 23, b: 47 After: a: 47, b: 23


Swapping in C Using the Preprocessor: Another very good way to swap in C (perhaps the best way) uses the C preprocessor, which we will study later. For now, a preprocessor function like swap below does a textual substitution, before the actual compiler is invoked. The second listing below is what is sent to the compiler. (This is why there is no semicolon at the end of , since in the compiled code it would become a redundant semicolon at the end of a block (although not an error).)

C Swap Program Using Preprocessor
#define swap(type, i, j) {type t = i; i = j; j = t;} int main() { int a = 23, b = 47; printf("Before swap. a: %d, b: %d\n", a, b); swap(int, a, b) printf("After swap. a: %d, b: %d\n", a, b); return 0; }
Preprocessed Output
% cc -E swap_p.c int main() { int a = 23, b = 47; printf("Before swap. a: %d, b: %d\n", a, b); { int t = a ; a = b ; b = t ; } printf("After swap. a: %d, b: %d\n", a, b); return 0; }
Run of the program
% cc -o swap_p swap_p.c % swap_p Before swap: a: 23, b: 47 After swap: a: 47, b: 23


Copyright © 2011, Neal R. Wagner. Permission is granted to access, download, share, and distribute, as long as this notice remains.

Before we move into discussing move semantics (the next step on my quest to convert you all to teaching in C++14), let’s clear up something that I often see being taught in a subtly “wrong” way with respect to memory management in even C++98.

Consider the following class, which might be written by a student in a fundamental data structures course:

What we see here is standard fare: we have a class that utilizes dynamic memory (via the pointer), and thus is provides the “Big Three”: a copy constructor, an assignment operator, and a destructor. These three overloads give us the value semantics that we desire, making it so that our class can “blend in” with the built in types of the language and standard library. C++ is rooted in value semantics, so it’s crucial that we get this right so that our classes are well behaved.

But let’s look more closely at our assignment operator. You may have seen it written something like this:

where is a helper function for releasing the memory associated with the current object, and is another helper function that is responsible for creating the memory for a new independent copy of the parameter, assigning it into the current object.

There are actually a couple of problems with this approach.

Pedagogical Complaints

Because the language semantics are often taught very early on in the course, and (at least at UIUC) to fairly inexperienced programmers (through no fault of their own: it’s just their second programming experience in the curriculum in its current form), you have to dance around this issue of the “self assignment” check.

: an enigma for “green” students

is particularly nuanced for students still struggling to understand some of the fundamental differences between Java and C++ (or C and C++). This requires them to understand:

  • the type of (a pointer to the current instance)

  • the purpose of as getting a pointer to the argument (not a reference, and understanding that itself is not a pointer)

  • what it would mean if .

That’s quite a bit of information we’re expecting them to digest in just a short little snippet. But if you write your assignment operator this way, it’s such a critical moment: if they forget this check, they will have memory errors coming out of their ears.

Technical Complaints

However, that’s not the real meat of my argument. My real beef with this setup is that it is completely exception unsafe. And, unless you’re living in a fairytale world where you

  • never allocate to the free store, and
  • never use the standard library

ignoring exceptions will be a fatal mistake at some point in your experience with C++.

And, please don’t come to me claiming that your codebase “doesn’t throw exceptions”, because you and I both know that’s just a load of crock. =)

Nearly every useful program is going to at least do one (and, likely, both) of the above two things. This means you have to care about exceptions.

Exception Safety

So what’s “unsafe” about this code?

Patience, young padawan. Let’s take a step back.

First, let’s identify where exceptions could be thrown, and then define what we want our class to do in the event of an exception. This will define what kind of “exception safety guarantee” we want to provide.

One of the bullet points I made above (when I was being rude; sorry) was that the memory allocator can throw exceptions. How could that be the case? Let’s look at three fairly simple examples:

  • We’re out of memory. This causes a exception to be thrown from the call to that we’ll be using to allocate our array.

  • A constructor for an element in the array throws during the call.

  • The assignment operator for an element in the new array throws when we are copying the data.

So clearly, then, the line that invokes has the potential to throw an exception. What would happen to our data structure in this case? There are a few cases:

  • It could be completely empty if the allocation itself fails (out of memory or a throwing constructor for during the call).

  • It could be partially-copied if the exception came from when copying the data.

So what can we do to deal with this exception?

Let me be clear here: our goal is not to handle the exception. What should the program do if it can no longer allocate heap memory, for example? That’s not something that our data structure should be deciding. So we’re not even going to try to catch and handle this error: instead, what we’re going to try to guarantee is something about the state of our class after the exception has been thrown—namely, that it is in the same state as it was before the assignment line that caused the exception.

Putting the safety back on our assignment operator

Using the template we had before, we could imagine rewriting it in the following way:

Shield your eyes! The horror! The code has exploded, has a horrible block to handle the fact that could throw during the assignment into the array (the cost of a generic type here), and is now almost certainly above the threshold of beginner programmers.

But it is exception safe.

Back to the drawing board

The above monstrosity is clearly beyond what we want to teach. There’s no reason we shouldn’t be able to achieve both goals: the ease of understanding that came with the then version, and also providing the strong exception safety guarantee.

This is where the “copy and swap” idiom comes into play. (It’s worth noting that this idiom is even more useful in C++11/14, but we’ll get there later.)

We start with the following observations:

  • We want to create new memory that is a completely independent copy of the parameter.

  • We must release the memory associated with the current object.

  • The current object must refer to the new memory that we’ve created.

…what if I told you that we already wrote most of this by virtue of having a well defined class? A helper? We have a copy constructor! Let’s see if we can’t use that as a form of “helper function”. Remember from the above code that we want the following chain of events:

  • Allocate memory
  • Copy over values
  • Free old memory
  • Refer to the new copy

and further note that there’s no reason we couldn’t do the last two in a different order (we’d just need a temporary).

Let’s first define a helper function that we’ll use in our implementation:

To be a good citizen, let’s also define a non-member swap function for our class that just delegates to the helper above:

And now consider the following implementation for the assignment operator:

Woah! We have two lines of code. There’s no way that gets us everything we need… right?

But it does.

  • We get the copy by virtue of the argument being passed by value.

  • If the copying fails (e.g., the copy constructor throws), our function is not run at all, so our class appears unchanged by the assignment because it truly didn’t happen.

  • Swapping with the value parameter accomplishes our resource release. Remember that any parameters passed by value are going to have their destructors invoked when the stack frame for that function is popped.

  • We don’t have to check for self assignment anymore, as that code path can now be handled without a special case. Yes, it is less efficient, but the point of checking for self assignment wasn’t as an optimization, it was a “please don’t crash my program” check.

The Catch

The only thing we have to guarantee now is that our copy constructor satisfies the basic exception guarantee (which is to say that it does not leak in the event of an exception), which isn’t too bad (though the code is still not ideal):

The nastiness here is because the marked line (1) could throw during ’s assignment operator.

In the general case, there are ways of avoiding the here, but I think this is a reasonable compromise for now. It’s worth noting at this point that if you were teaching with the then style, your copy constructor was probably exception unsafe, too, so this isn’t just a reflection of some “complication” in the copy-and-swap idiom.

If you’re dealing with some type that you know does not throw from its assignment operator (an assumption I’m willing to make when teaching novice programmers), then the code can be simplified to just:

We’ll revisit this later when we start talking about C++11/14 and show how just a simple language switch can ensure that we get the basic exception guarantee out of our copy constructor in the general case by only a one line change to the above initializer list!

Closing Thoughts: An exception-safe “Big Three” for intro programmers

Let’s recap what our code for the “Big Three” looks like now, including all of our helper functions:

Advantages

  • Real world applicability: exceptions are everwhere, you need to know them and how to handle them

  • Simplified explanation for , using language concepts they’re learning as they are doing copy constructors anyway (pass by value)

  • Elimination of the self assignment check (self assignment is automatically valid in the copy-and-swap idiom)

  • A helper function that’s useful to the outside world:

Disadvantages

  • Requires some discussion of what exceptions are, what they are used for, and why we care about them

  • If you are truly being careful, in C++98/03 you will need to have a block in the copy constructor (but not in C++11/14, more to come…)

Coming Up

Now that we know about the copy-and-swap idiom, in the next post I’m going to talk briefly about move semantics in C++11/14, and then we can move on to tackle what I teased at in the very first post in this series: that we can teach manual memory management in C++11/14 without losing out on any teaching opportunities compared to C++98/03, all the while simultaneously being more modern and encouraging students to write safe code.

Yell at me in the comments!

One thought on “Assignment Operator C Swapper

Leave a comment

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *