The array Project

Introduction

In this programming project we are implementing a data structure based on the Abstract Data Type (ADT) sequence container, also known as a list, with a static array as its underlying data structure.

List ADT Attributes (Overview)

The List ADT is implemented as a C++ class called sc::array. This class stores its data in a dynamically allocated array, whose size will be specified by the client at run time. Once the client has chosen the array's size, it cannot be modified. This means that we are implementing a fixed-size list.

The first attribute of the sc::array class is the storage area, m_data. The storage area can be represented by either a raw pointer or a smart pointer, such as std::unique_ptr. In the case of a raw pointer, it is important to free the memory at the end of the array's life cycle.

The second attribute of the class is its maximum storage capacity, m_capacity. As the name implies, it keeps track of the maximum storage capacity (or length) of the internal storage area. This value should be specified by the client when the list is instanced and cannot be changed directly once the list is created.

The third attribute of the class is m_end. This is an integer index that points to the location just past the last valid element. It is also the index to the location at the end of the list where new elements are inserted. Its initial value is zero (indicating an empty list).

Important

All the behavior decision above are arbitrary and were made with focus on the teaching aspect of this exercise. If you do not agree with any of them, you might change them as you wish to better suit your needs when you design and create your own container. However, for this exercise, we are following these design decisions.

The diagram below shows an example of an array with a maximum storage capacity of seven elements that has already received three elements (3, 8, and 2).

class sc::array {
 0 1 2 3 4 5 6
 +---+---+---+---+---+---+---+
m_data: | 3 | 8 | 2 | | | | |
 +---+---+---+---+---+---+---+
 ^
 |
m_end: 3 -------------+
m_capacity: 7
};

The client code to create this array and insert these elements could look something like this:

int main(){
 sc::array<int> v(7); // specify the max capacity
 v.push_back(3);
 v.push_back(8);
 v.push_back(2);
}

List ADT Interface

Here is a list of actions or operations that an ADT List should support. These operations will become methods of a C++ class called sc::array.

Constructor: creation of the list

Creates a list with a capacity specified by the client code. The process of creating a list involves the dynamic allocation of memory to hold the data that will be inserted in the list. This process will be coded in the constructor of the sc::array class.

Destructor: destruction of the list

Frees the memory allocated in the creation process. This will be coded as the destructor of the sc::array class.

array( const array& )

This is the copy constructor, which creates a new list from an existing one, passed as argument. You need to do a deep copy of the array passed as argument for this to work properly.

Inserting an element in the list

The method insert(pos, value) inserts a new value at the pos location in the list. Here, we need to deal with three possibilities:

Note

The insertion should be done only if there is room for the new element, i.e. size() < capacity().

1. pos is an index already occupied by an element previously inserted. In this case, the operation must shift all elements of the array starting at the pos location to the right. After the shift operation is done, the new value is inserted at pos.

int main(){
 sc::array<int> v(7); // specify the max capacity
 v.push_back(3);
 v.push_back(8);
 v.push_back(2); // Array is [3,8,2,?,?,?,?].
 v.insert(1,-1); // insert value -1 at index 1.
 // Now array becomes [3,*-1*,8,2,?,?,?].
}

2. pos is an index that points to a location beyond the last element of the list but before the array capacity. In this case, pos becomes the new last valid element of the list, thus increasing the list occupation size. Default-initialized objects must be inserted between the previous last valid element and the newly inserted one at pos.

 int main(){
 sc::array<int> v(7); // specify the max capacity
 v.push_back(3);
 v.push_back(8);
 v.push_back(2); // Array is [3,8,2,?,?,?,?].
 v.insert(5,-1); // insert value -1 at index 5.
 // Now array becomes [3,8,2,0,0,*-1*,?].
 }

3. Lastly, pos is greater than or equal to the original array's capacity (in our example, seven). In this case, the insert() method should throw an exception (std::length_error) so that the client may take appropriate action.

int main(){
 sc::array<int> v(7); // specify the max capacity
 v.push_back(3);
 v.push_back(8);
 v.push_back(2); // Array is [3,8,2,?,?,?,?].
 v.insert(8,-1); // trying to insert value -1 at index 8.
 // the code crashes here, exception no caught!
}

Note

Remember that an uncaught exception crashes the program, but this is not our direct concern as the array's developer. It is up to the client of the array to handle any eventual exceptions that might be thrown as result of their misuse of the array. Our job is to report in the class documentation that some of the array's methods may throw an exception in specific conditions.

array(const std::initializer_list<T>& il)

Creates a new array that is already filled in with a list of elements provided in the il object. This is a traditional way of instancing and object and, at the same time, assigning content to it.

int main(){
 sc::array<int> v({3,8,2,6,5}); // Creating an array with 5 elements.
}

to_string()

Returns a string representation of the array's content. This is a useful method for debugging.

The method should return a string with the array content, enclosed in brackets, having each element separated by a single white space.

push_back(value)

Inserts a new value at the end of the list. If the list is already full, the method throws an exception (std::length_error) and the array remains unchanged.

remove(pos)

Removes a value at location pos, shifting all the elements from pos+1 until the end of the list one position to the left. The relative order of all remaining elements is preserved. If pos lies outside the valid range of the list, the method throws an exception (std::out_of_range) and the array remains unchanged.

pop_back()

Removes the last value of the list. If the list is empty, the method throws an exception (std::length_error).

at(pos)

Retrieves the value located at pos in the list. If the pos corresponds to a location beyond the array's capacity, the method throws an exception (std::out_of_range).

at(pos) (2)

This is a second version of the method at().

It retrieves the reference to the location pos in the list. This allows the replacement of that content if this method is used on the left-hand side of an assignment. If the pos corresponds to a location beyond the array's capacity, the method throws an exception (std::out_of_range) and the array remains unchanged.

empty()

Returns true is the list is empty, false otherwise. The list is considered empty is m_end is equal to zero.

size()

Returns the current number of elements stored in the list.

capacity()

Returns the max storage capacity of the list.

clear()

Removes all elements of the list, making it empty.

operator=()

This is the traditional assignment operator, common to almost every class in C++. This is a binary operator that makes the receiving object (the one on the left-hand side of =) have the same content of another object (the one on the right-hand side of =).

If the client tries to assign arrays of different sizes the method throws an exception (std::length_error).

The Code

In this repository, you will find the code that has been developed during the classes. The code is currently incomplete.

To Run

Run with the following:

./bin/driver_array

TO DO

We need to finish the implementation of the sc::array class.

List of methods already implemented:

• Constructor
• Destructor
• Copy constructor
• to_strin()
• push_back()
• insert()
• full()
• empty()
• capacity()
• size()