Arrays, Linked Lists and Unordered Lists

Note: This is part of an assignment for a course I am currently enrolled in.

I'm in a C++ programming class and part of my assignment is to write a class function "CopyEarlyList" for AUList (array-based unordered list) that duplicates the first N elements of the list and returns it as a new, separate list, in the same order.
I know that it would start something along the lines of:

Code:

---

class CopyEarlyList {
    public:
};

---

but passed that I am for some reason having a difficult time creating it completely. Lists, at least in this context, are a kind of new area for me. I have used them before but never using a class function.
Any help you all can provide is very appreciated!

C++ has classes, which are user-defined types, and C++ has functions. There are also member functions, which are like normal functions except:
- They have an additional hidden parameter: "this."
- They can be invoked on instances of the class on which they're defined, e.g. myList.CopyPrefix(4).
- They can access the members of the instance as if they were in scope.

I'm not sure, but it seems like your assignment is to add a member function to an existing list class, where the function does what you described. Is that right?

In a way yes that is correct but as far as I understand from the professor I am just responsible for creating a class function that if supplied with the necessary main function would run correctly. However, I do not have to supply any other functions passed the class. I also do not have an existing list class to add this CopyEarlyList class to.

I thought I had made another reply, but I think I accidentally deleted it.

I don't know what an array-based unordered list is, but after googling around and reading some Java documentation, my best guess is that it's a resizable array with a sequence interface.

In C++, the canonical class for that is

Code:

---

std::vector<T>

---

, for some element type T, e.g. int. You can use std::vector after including the standard vector header:

Code:

---

#include <vector>

---

You can read about the interface of vector and the algorithmic complexity of each operation here: std::vector - cppreference.com

It's likely that your professor has another type in mind (you mentioned some AUList). In that case, use the corresponding operations on that type.

Based on the problem described, a function having the following signature ought to do the trick (assuming you are working with integers):

Code:

---

std::vector<int> repeatPrefix(const std::vector<int>& original, int prefixLength);

---

That takes a reference providing non-modifiable access to a vector of ints, and returns a new vector of ints, where the idea is that the returned vector has the first prefixLength elements of the original repeated at the front.

Since you probably won't be using vector, I don't feel too bad writing this for you as an example:

Code:

---

#include <cassert>
#include <initializer_list>
#include <iostream>
#include <vector>

// Return a copy of the specified `original` but that has additionally had
// the `prefixLength`-length prefix repeated once at the beginning.  For example,
// `repeatPrefix({1, 2, 3, 4, 5}, 2) == std::vector<int>({1, 2, 1, 2, 3, 4, 5})`.  The
// behavior is undefined unless `prefixLength` is non-negative and less than
// or equal to the length of `original`.
std::vector<int> repeatPrefix(const std::vector<int>& original, int prefixLength) {
    assert(prefixLength >= 0);
    assert(prefixLength <= int(original.size()));

    // This is the object we will return.
    std::vector<int> result;

    // Make room for the elements.  This is unnecessary and a premature
    // optimization, but since we know the output length, I can't resist.
    result.reserve(original.size() + prefixLength);

    // Add the first `prefixLength` elements.
    result.insert(result.end(), original.begin(), original.begin() + prefixLength);

    // Add the entire input.
    result.insert(result.end(), original.begin(), original.end());

    return result;
}

int main() {
    // See what the result is when we use the example from the contract.
    for (int x : repeatPrefix({1, 2, 3, 4, 5}, 2))
        std::cout << x << '\n';
}

---

An array is the data structure that contains a collection of similar type data elements whereas the Linked list is considered as non-primitive data structure contains a collection of unordered linked elements known as nodes.