Inputting elements of unknown type into a vector

Question

I'm working on a program that takes elements from a user and sorts them. For this program, I have to use a vector as the size of the element list is unknown prior to user input. Our instructions were:

Write a program in C++ to implement sorting of a list of elements. Elements can be of any type but will all be of same type, like all integers or all floats or all chars or all strings (strings shall be sorted like in a dictionary). You can implement any sorting algorithm of your choice.

1. Ask the user how many elements will be there
2. Ask the user to input elements
3. Ask the user to choose the sorting order: ascending or descending or both
4. Print both input and output lists
5. User will not provide any information regarding the type of elements

I'm not very familiar with vectors (teacher basically skimmed topic in class) and my book isn't giving me a whole lot of information on the subject. The problem I'm running into is that I don't know the type of the element list until the user begins input. So far, I have tried:

• creating a void type vector (obviously not allowed now that I've researched it, oops)
• overloading a function called insertInVector by sending the first element to the function and letting the function determine which vector type to create based on the type of the first element (which seemed like my best option when I thought of it, except I need access to the vector after the function terminates, so that ended up being a no go, too)
• #include <typeinfo> in program, finding the type of the first element, and then creating a vector using vector<typeid(firstElement).name()> and honestly I'm not sure why that didn't work, but it didn't.

Like I said I have EXTREMELY limited experience with vectors as this is my first time using them. I'm also a fairly new programmer so a lot of the research I've done on this has gone over my head. Any help that could be given in this would be GREATLY appreciated!

Answer 1

C++ is a language statically typed. It means that all the types should be determined during compilation: you cannot introduce new types when running the program.

• creating a void type vector (obviously not allowed now that I've researched it, oops)

void is actually quite a strange type, mostly a placeholder for when you would expect a type (like a function return type) and have none to provide. void* is used as a pointer to an unknown type (mostly in C) but this is quite a hack, because the information about the original is discarded (as far as the language is concerned) so this causes issues to actually do things with the value so obtained.

• overloading a function called insertInVector by sending the first element to the function and letting the function determine which vector type to create based on the type of the first element

• #include <typeinfo> in program, finding the type of the first element, and then creating a vector using vector<typeid(firstElement).name()> and honestly I'm not sure why that didn't work, but it didn't.

Unfortunately neither is possible: since you cannot declare a variable without a type, what would be the type of firstElement to begin with ?

---

The problem you are describing is difficult in general. Basically it means that you will have to accept a string of characters, and then code a set of rules to determine how to interpret those characters. This is done generically by using a grammar to encode those rules; but grammars might way complicated for what is probably a simple task.

Let me put together a small example:

class Input {
public:
    enum Type {
        Int,
        Double,
        String
    };

    static Input Parse(std::string const& s);

    Input(): _type(Int), _int(0), _double(0.0) {} // need to define a default...

    Type type() const { return _type; }

    int asInt() const {
        assert(_type == Int && "not an int");
        return _int;
    }

    double asDouble() const {
        assert(_type == Double && "not a double");
        return _double;
    }

    std::string const& asString() const {
        assert(_type == String && "not a string");
        return _string; 
    }

private:
    Type _type;
    int _int;
    double _double;
    std::string _string;
};

Obviously, the real challenge is to correctly Parse the input.

The idea is to use a set of rules, for example:

• an int is composed exclusively of digits, optionally prefixed by -
• a double is composed exclusively of digits, with at most one . and optionally prefixed by -
• a string can be anything, therefore is our catch-all

Then we can write the recognition part of the Parse method:

static bool isInt(std::string const& s) {
    if (s.empty()) { return false; }
    
    // The first character may be among digits and '-'
    char const first = s.at(0);
    if (not isdigit(first) and first != '-') { return false; }

    // Subsequent characters may only be digits
    for (char c: s.substr(1)) {
        if (not isdigit(c)) { return false; }
    }

    // Looks like it is an int :)
    return true;
} // isInt

// Note: any int could be interpreted as a double too
static bool maybeDouble(std::string const& s) {
    if (s.empty()) { return false; }

    // The first character may be among digits, '.' and '-'
    char const first = s.at(0);
    if (not isdigit(first) and first != '.' and first != '-') { return false; }

    // There may only be one dot
    bool hasSeenDot = s.at(0) == '.';

    // Subsequent characters may only be digits and a dot now
    for (char c: s.substr(1)) {
        if (not isdigit(c) and c != '.') { return false; }

        if (c == '.') {
            if (hasSeenDot) { return false; } // no second dot allowed
            hasSeenDot = true;
        }
    }

    // Looks like it could be a double
    return true;
} // maybeDouble

static Input::Type guessType(std::string const& s) {
    if (isInt(s)) { return Input::Int; }

    // Test double after we ensured it was not an int
    if (maybeDouble(s)) { return Input::Double; }

    return Input::String;
} // guessType

And with the guessing logic together, finally the parse comes:

Input Input::Parse(std::string const& s) {
    Input result;

    result._type = guessType(s);

    switch(result._type) {
    case Input::Int: {
        std::istringstream stream(s);
        s >> result._int;
        return result;
    }
    case Input::Double: {
        std::istringstream stream(s);
        s >> result._double;
        return result;
    }
    case Input::String:
        result._string = s;
        return result;
    }

    // Unreachable (normally)
    abort();
} // Input::Parse

Phew!

So ? Almost there. Now we need to determine how to compare two inputs. It's easy if they all have the same type, if not you will need to determine an arbitrary logic. You can transform an input Int in an input Double easily enough, but for string it's a bit weirder.

// define < for comparing two instance of "Input",
// assuming they both have the same type
bool operator<(Input const& left, Input const& right) {
    assert(left.type() == right.type() && "Different Types!");

    switch(left.type()) {
    case Input::Int: return left.asInt() < right.asInt();
    case Input::Double: return left.asDouble() < right.asDouble();
    case Input::String: return left.asString() < right.asString();
    }
} // operator<

And finally, the program:

int main(int argc, char* argv[]) {
    // parse command line
    std::vector<Input> inputs;

    // by convention argv[0] is the program name, it does not count!
    for (int i = 1; i != argc; ++i) {
        inputs.push_back(Input::Parse(argv[i]));

        // Detect that the type is the same as the first input
        if (inputs.size() >= 2) {
            if (inputs.back().type() != inputs.front().type()) {
                std::cerr << "Please only use one type among Int, Double and String\n";
                return 1; // non-0 is an error
            }
        }
    }

    // sort
    std::sort(inputs.begin(), inputs.end());

    // echo back to the user
    for (Input const& i: inputs) {
        switch(i.type()) {
        case Input::Int: std::cout << i.asInt() << "\n"; break;
        case Input::Double: std::cout << i.asDouble() << "\n"; break;
        case Input::String: std::cout << i.asString() << "\n"; break;
        }
    }

    // End of the program
    return 0;
}

Of course as I don't know the types you wish to deal with.. I've decided an arbitrary set ;) However this should give you a skeleton to base yourself on.