Question 2
1. Background
Normal lists in C++ are either C-style arrays or standard-library containers (e.g. std::vector, std::array, std::list). We want to create a more powerful list structure in C++. We want to create one that can exhibit more interesting behaviours. For example:
auto l1 = smart_list<double>{1,2,3};auto l2 = smart_list<double>{4,5,6};auto l3 = l1 + l2;REQUIRE(l3 == smart_list<double>{1,2,3,4,5,6})
In rare cases we want a list that is very smart and can do everything a normal smart_list can do, but can also sometimes make use of particular properties of our types:
auto l = very_smart_list<int>{6,9,15};l /= 3;REQUIRE(l == very_smart_list<int>{2,3,5});REQUIRE(l.is_prime());
A smart_list should not be able to do these things: it's not smart enough.
Please note that the usage of "list" here is quite high level, and does not specifically refer to a linked list. In most cases "list" in higher level languages just refers to an object similar to std::vector.
2. Task
You are to develop a new class template smart_list<T> that behaves similar to a std::vector<T> except that it has a handful of modified funtionality and additional functionality. You are also to develop a new class very_smart_list<T> which can do everything a smart_list<T> can do, with more.
The interface of these classes are described below. Where functions are provided for both smart_list and very_smart_list, the use of "smart_list" should be replaced by "very_smart_list" when appropriate except when otherwise mentioned.
There are no constraints regarding internal representation or implement. As long as the interface functions as described that is all that matters. You are allowed to have more functions on the public interface than we have described (if this helps you solve the question).
Constructors
Both smart_list and very_smart_list:
explicit smart_list(std::size_t count)/explicit very_smart_list(std::size_t count)- A constructor that generates exactly
countdefault-constructed elements into the list. - Example:
auto x = smart_list<int>(5); - Exceptions: None.
- A constructor that generates exactly
smart_list(T const& one, T const& two, std::size_t count)/very_smart_list(T const& one, T const& two, std::size_t count)- A constructor that generates
countrepetitions of appending bothoneandtwoto the list. - Example:
auto x = smart_list<std::string>("hello", "there", 3)would produce a list containing["hello", "there", "hello", "there", "hello", "there"]. - Exceptions: If
one == two, throws"Cannot use multi-argument constructor with two identical elements"
- A constructor that generates
smart_list(std::initializer_list<T> il)/very_smart_list(std::initializer_list<T> il)- A constructor that initializes its contents with the given list.
- Example:
auto l = smart_list<double>{ 1.0, 1.5, 2.0 }; - Exceptions: None.
For very_smart_list only:
explicit very_smart_list(smart_list<T> const& other)- A constructor that copies all elements from
other. - Example:
auto vsl = very_smart_list<double>(sl); - Exceptions: None.
- A constructor that copies all elements from
explicit very_smart_list(smart_list<T>&& other)- A constructor that moves all elements from
other. - Example:
auto vsl = very_smart_list<double>(std::move(sl)); - Exceptions: None.
- A constructor that moves all elements from
Accessors
Both smart_list and very_smart_list:
std::size_t size()- Returns the number of elements in the container.
- Example:
auto x = sl.size(); - Exceptions: None.
Modifiers
Both smart_list and very_smart_list:
void push_back(const T& value)- Appends the given element to the end of the container.
- Example:
sl.push_back(5); - Exceptions: None.
void pop_back()- Removes the last element in the container.
- Example:
sl.pop_back(); - Exceptions: If
sl.size() == 0, throws"Cannot pop_back an empty list".
void emplace_back(Args... args)- Appends a new element to the end of the container, constructed in-place using perfect forwarding.
- Example:
auto sl = smart_list<std::pair<int, double>>(); sl.emplace_back(1, 2.0); - Exceptions: None.
- Notes: The provided signature is not totally correct; you must determine the appropriate signature to perfectly forward the list of arguments.
Operator overloads
Both smart_list and very_smart_list:
operator[](std::size_t index)- Get and/or set a value at the given index.
- Example:
auto a = sl[1]; sl[2] = a + 2; - Exceptions: None. (You can assume the index is valid.)
smart_list operator+(smart_list const& lhs, smart_list const& rhs)- Concatenate two smart lists together.
- Example:
auto c = a + b; - Exceptions: When
lhs.size() == 0orrhs.size() == 0, throw"Cannot concatenate smart lists where one is empty". - Notes: Always returns a
smart_list, even when called onvery_smart_lists.
smart_list operator-(smart_list const& lhs, smart_list const& rhs)- Return a copy of
lhs, with all elements also present inrhsremoved. - Example:
auto c = a - b; - Exceptions: When
lhs.size() == 0orrhs.size() == 0, throw"Cannot subtract smart lists where one is empty". - Notes: you can assume you may use
operator==to compare elements. Always returns asmart_list, even when called onvery_smart_lists.
- Return a copy of
smart_list<smart_list<T>> operator*(smart_list const& lhs, smart_list const& rhs)- Multiply two lists together. The output is a 2D smart list with products of all components.
- Example:auto a = smart_list<double>{1,2,3};auto b = smart_list<double>{2,3,4};auto c = a * b;REQUIRE(c == smart_list<smart_list<double>>{{2,3,4},{4,6,8},{6,9,12}});
- Exceptions: None.
- Notes: You can assume you may use
operator*to multiple elements. Always returns a nestedsmart_list, even when called onvery_smart_lists.
std::ostream& operator<<(std::ostream& os, smart_list const& sl)- Prints out each element of
sltooswith a|on either side of the element. An empty list should print nothing. - Example:auto sl = smart_list<double>{1,2,3};std::cout << sl; // |1|2|3|
- Exceptions: None.
- Prints out each element of
For very_smart_list only:
very_smart_list operator*(very_smart_list const& lhs, double scalar)- Scalar multiplication, where e.g.
[1 2] * 3 = 3 * [1 2] = [3 6]. IfTis not an arithmetic type, then this function has no effect and simply returns a copy of the list passed in. - Example:
auto x = sl * 3.0; auto y = 3.0 * sl; - Exceptions: None.
- Scalar multiplication, where e.g.
very_smart_list operator/(very_smart_list const& lhs, double scalar)- Scalar division, where e.g.
[3.0 6.0] / 2.0 = [1.5 3.0]. IfTis not an arithmetic type, then this function has no effect and simply returns the list passed in. - Example:
auto x = sl / 3.0; - Exceptions: None.
- Scalar division, where e.g.
Miscellaneous functions
For very_smart_list only:
bool is_prime()- Returns
falseifTis not an integer type. Otherwise, returnstrueiff all of the elements in the container are prime numbers. - Example:
auto x = vsl.is_prime(); - Exceptions: None.
- Returns
Other notes
You are also required to ensure that both classes have the following capabilities:
- It is comparable using
operator==andoperator!=with the normal meanings (assuming thatTis also comparable) - Standard default constructor that populates an empty list
- Standard copy semantics (construction and assignment) that does member-wise copy
- Standard move semantics (construction and assignment) that does member-wise move
- Standard destructor that ensures all memory is cleaned up
- For operators where it makes sense, a compound assignment form should exist as well (e.g. provide
operator+=too). It should throw the same exceptions as well. - Provides functions
begin()andend()that returns a type which models at leaststd::bidirectional_iteratorand act as iterators to your underlying container. You can assumebegin()andend()return onlyconst_iterator-like types (no non-const iterators).
You should be able to use a very_smart_list wherever a smart_list is expected. For example:
auto sl = smart_list<double>{1,2,3};auto vsl = very_smart_list<double>(sl);vsl *= 3.0;REQUIRE(sl + vsl == smart_list<double>{1,2,3,3,6,9});
However, you should not be able to use a smart_list where a very_smart_list is expected:
auto sl = smart_list<double>{1,2,3};sl *= 3.0; // should be a compiler error
You are required to ensure that relevant operators are marked const where appropriate, or have both a const and non-const version where appropriate.
All exceptions thrown are std::runtime_error. The use of "Exceptions: None." just means you do not need to throw any exceptions yourself: you do not need to handle exceptions thrown by operations on the types stored.
Please ensure that as a priority you ensure that operator==, push_back, and default construction work. We will rely on these 3 heavily for testing.
3. Assumptions & Constraints
- There are no performance requirements or constraints for this question
- You can assume that all input is valid unless stated otherwise in the spec
4. Mark Breakdown
For this question, the approximate mark allocations are:
- 60% for correctly implementing
smart_list- 20% of this will be for constructors
- 10% of this will be for Accessors
- 10% of this will be for modifiers
- 40% of this will be for operator overloads
- 10% of this will be for miscellaneous functions
- 10% of this will be other requirements listed in "Other notes"
- 30% for correctly implementing
very_smart_list(everything fromsmart_listplus additional functions)- 20% of this will be for constructors
- 10% of this will be for Accessors
- 10% of this will be for modifiers
- 40% of this will be for operator overloads
- 10% of this will be for miscellaneous functions
- 10% of this will be other requirements listed in "Other notes"
- 10% for allowing
very_smart_listto be used everywhere asmart_listmight be expected
