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.
#include <stdexcept> // For out_of_range
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
~ordered_array();
/* 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 the value in the array at index i, which should be >= 0 and <
size().
If i < 0 or i >= size(), then at(i) should throw a std::out_of_range
exception. (This is what std::vector does in this situation.)
Note that at() should *never* return -2147483648 (because insert() should
never insert it).
*/
int at(int i);
private:
// You can add any private members you need.
};
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:
- If
size() == n
for some unknown \(n\), approx. how much time will the method take, in terms of n? For example, if a method examines each element of the array twice, you might say it will take roughly \(2n\) time to run.
Explain and justify your answers.
Testing
To test your code, I have supplied a file assign1_test.cpp
which, when linked
with your code, will provide a main
which runs several tests on your
implementation. If your implementation is incomplete or incorrect in any way,
the test code will (hopefully!) catch it and give you a message.
To test, make a copy of assign1_test.cpp
in the same directory as your source
files (this is necessary because assign1_test.cpp
#include
s your
ordered_array.hpp
so that it can use your class definition). assign1_test.cpp
is found on the server in the directory /usr/local/class/src
so to copy it, use
cp /usr/local/class/src/assign1_test.cpp .
and then compile with
g++ -o assign1_test assign1_test.cpp ordered_array.cpp
or
compile assign1_test.cpp ordered_array.cpp
(You can omit ordered_array.cpp
if your entire implementation is in the
header file.)
You are welcome to examine assign1_test.cpp
to see what kinds of tests it
will perform.
After compiling, run ./assign1_test
. If your code fails any tests, it will
print a message telling you what went wrong. If nothing went wrong, it will
print “All tests passed!” which means you are done!
Some hints
Here are some things that don’t work:
Creating the array as a global variable. The test runner will create more than one instance of
ordered_array
and expects all instances to be independent.Assuming that all
insert
s will be performed at once. The test code may mix up a sequence ofinsert
andremove
s.
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. After I evaluate
your work, I’ll post a grade to Blackboard/Canvas and then copy a file
instructor_comments.txt
into the assignment subdirectory with any comments
I have for you.
To create these directories, you can enter the commands:
mkdir cs133
mkdir cs133/assign1
cd cs133/assign1
and then launch Micro or the editor of your choice to start working.