Assignment 1: C++ review

First, just for fun, read What every computer science major should know, by Matt Might (professor at Univ. of Alabama at Birmingham). Then proceed with the rest of the assignment.

Sorted Array data structure

In this assignment, you’ll implement a simple data structure which maintains a sorted array. This is essentially just a simple wrapper around a dynamically-allocated array of int (you can also use a vector) which allows the user to insert and remove values. The elements of the array should always be sorted in ascending order; this means that when you add new elements, you need to figure out where they go in the array, shift everything after them up, and then drop the new element into place. Likewise, when you remove an element, you have to find it, and then shift everything after it down.

In other words, if we do

ordered_array arr(10); // Capacity 10, Size 0

cout << arr.size() << endl; // Should print 0

arr.insert(3);
arr.insert(2);
arr.insert(1);

cout << arr.size() << endl; // Should print 3

// This should print 1, 2, 3
for(int i = 0; i < arr.size(); ++i)
  cout << arr.at(i) << ", ";

The ordered_array has a maximum size known as its capacity which is specified when it is created, and fixed from that point forward. This is the maximum number of elements that can be insert-ed into the array, if none are remove-d, before the array is full. The number of elements currently in the array is its size. Member functions .size() and .capacity() provide access to both these values. Note that an array’s size is always \(\ge 0\) and \(\le\) its capacity. The size of an ordered array should be 0 when it is first created.

Use the following class definition, supplying definitions for the the various member functions, and adding whatever private members you need.

/*
 * ordered_array.hpp
 * Definition of the ordered_array class. You can either create a separate 
 * ordered_array.cpp and put the method definitions there, or replace the 
 * method declarations below with definitions. E.g., replace
 *
 *     int size();
 *
 * with 
 * 
 *     int size() 
 *     {
 *         // Your code here...
 *     }
 *
 * and similarly for all the other functions
 */

class ordered_array {
  public:
    /* constructor
       Construct a new ordered_array with the given capacity (maximum size).
       The size of a new ordered_array should be 0.
    */
    ordered_array(int cap); 

    /* destructor
       Note that you only need a destructor if you're using a dynamic array.
       If you're using a vector, you should delete or comment this out.
    */
    ~ordered_array();

    /* This assignment does not require you to implement the copy constructor
       or copy assignment operator, even if you are using dynamic memory.
    */

    /* size()
       Returns the size (number of elements in the array).
    */
    int size();

    /* capacity()
       Returns the maximum size of the array.
    */
    int capacity();

    /* insert(e)
       Insert e into the array. Note that it is OK to insert duplicates; if n 
       copies of a value are inserted into the array then n copies should appear
       in the array.

       If size() == capacity() then this does nothing.

       If e == -2147483648 then this does nothing (i.e., -2147483648 is not a
       valid value to insert).
    */
    void insert(int elem);

    /* remove(e)
       Remove e from the array, if it exists. (If it does not exist, the
       array should be unchanged.) If multiple copies of e are present, only
       one should be removed.

       If e = -2147483648 then this does nothing.
    */
    void remove(int elem);

    /* exists(e)
       Returns true if e is present at least once in the array.

       If e == -2147483648 then this returns false.
    */
    bool exists(int elem);

    /* at(i)
       Returns a *reference* to the element at index i. If i < 0 or i >= size(),
       then the function should throw a std::out_of_range exception (this is the
       same exception that std::vector::at would throw in this situation).

       Note that at() should *never* return -2147483648.
    */
    int& at(int i);

  private:

    // Add private members as needed
};

You can download a copy of this file, or find it on the server in /usr/local/class/src/cs133/ordered_array.hpp.

You should place this class definition in a header file named ordered_array.hpp. Your method implementation (if not part of the class definition) should be in ordered_array.cpp. You can write your entire class definition in the header, if you want, or do the old-fashioned thing and write only the method declarations in the header, and put their implementations in a .cpp file.

In the comments before insert(), remove(), and exists(), try to answer the following question:

Explain and justify your answers.

Getting started

Like in “assignment 0”, to start on this assignment, execute the following commands on the server:

mkdir -p ~/cs133/assign1
cp /usr/local/class/src/cs133/assign1_test.cpp ~/cs133/assign1
cp /usr/local/class/src/cs133/ordered_array.hpp ~/cs133/assign1
cd ~/cs133/assign1
git init

and then open ordered_array.hpp in whatever editor you prefer.

You only need to do these once at the beginning; later, to continue working on assignment 1 you can just do

cd ~/cs133/assign1

and then open ordered_array.hpp in whatever editor you prefer.

Remember that you must maintain a history of your changes in Git; the test-assignment script will create a Git commit for you every time it is run, but you should be adding your own commits (or at least updating the commit message for those created by test-assignment). To add your own commit:

git commit --allow-empty -m "Message"

Replace Message with some description of the changes you’ve made. (The --allow-empty flag is necessary because if you’ve just run test-assignment it will have created a commit for you, so this commit is technically empty.)

Alternatively, if you’ve just run test-assignment, you can edit the message attached to its commit with 

git amend -m "New message"

To see the list of all commits, just run

git log

Testing

The easiest way to test is just to run the test-assignment script, from within the assign1 directory:

test-assignment

However, if you need to use the debugger, or you want to modify the test runner to print more information, you may want to compile manually. To do this, make a copy of assign1_test.cpp in the same directory as your source files (this is necessary because assign1_test.cpp #includes your ordered_array.hpp so that it can use your class definition) and then compile with 

compile assign1_test.cpp

or

g++ -o assign1_test assign1_test.cpp

(If you added a ordered_array.cpp file, then add that to the list of files to be compiled.)

You are welcome to examine assign1_test.cpp to see what kinds of tests it will perform; you can also modify it to print more information, but of course I’ll always use the “stock” version.

After compiling, run ./assign1_test. If your code fails any tests, it will print a message telling you what went wrong.

Some hints

Here are some things that don’t work:

The fact that -2147483648 is not a valid value for insert() means that you can use it within the array as a “special” value. E.g., to indicate that an entry is not yet used, or has been remove()-d. But be aware that this may not be the most efficient way to implement an ordered array!

How to submit

To submit this and all future assignments, create a subdirectory of your home directory named cs133 and then within that, create a subdirectory named assign1 and place your source files there. My script will automatically make a copy of whatever is in that directory on the due date.