Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

In this assignment, youll implement a simple data structure which maintains a sorted array . This is essentially just a simple wrapper around a dynamically-allocated

image text in transcribed

In this assignment, youll 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. 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 arrays size is always 0 and 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 various member functions, and adding whatever 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.

#include // 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 8. 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 elen); /* 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 elen); /* exists(e) Returns true if e is present at least once in the array. If e == -2147483648 then this returns false. bool exists(int elen); /* at(i) Returns the value in the array at index i, which should be >= size(). and If i c 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. #include // 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 8. 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 elen); /* 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 elen); /* exists(e) Returns true if e is present at least once in the array. If e == -2147483648 then this returns false. bool exists(int elen); /* at(i) Returns the value in the array at index i, which should be >= size(). and If i c 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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Marketing Database Analytics

Authors: Andrew D. Banasiewicz

1st Edition

0415657881, 978-0415657884

More Books

Students also viewed these Databases questions