Entering elements of an unknown type in a vector

Question

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

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

• Ask the user how many items will be there.
• Ask user to enter items
• Ask the user to select a sort order: ascending or descending or both
• Print Input and Output Lists
• User will not provide item type information

I am not very familiar with vectors (the teacher mainly shoots the topic in the classroom), and my book does not give me much information on this subject. The problem that I am facing is that I do not know the type of list of items until the user starts to enter data. So far I have tried:

• creating a vector of type void (obviously now it is not allowed that I examined it, oops)
• overloading a function named 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 to be my best option when I thought about it, except I need access to the vector after the function finishes , so that in the end there was no way out either)
• #include <typeinfo> in the program, finding the type of the first element and then creating a vector using vector<typeid(firstElement).name()> and, frankly, I'm not sure why this didn't work, but it doesn't.

As I said, I have EXTREMELY limited experience with vectors, as this is my first time I use them. I am also a fairly new programmer, so many of the studies that I have done on this subject have gone through my head. Any help that can be given in this would be a GREAT appreciation!

Answer 1

C ++ is a statically typed language. This means that all types must be defined at compile time: you cannot enter new types at program startup.

• creating a vector of type void (obviously now it is not allowed that I examined it, oops)

void is actually a rather strange type, basically a placeholder, when you expect a type (like the return type of a function) and should not provide it. void* used as a pointer to an unknown type (mainly in C), but this is quite a hack, because the information about the original is discarded (as far as language is concerned), so this leads to the fact that the problem really got the value.

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

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

Unfortunately, this is not possible: since you cannot declare a variable without a type, where would the firstElement type firstElement ?

---

The problem you are describing is generally complex. This basically means that you need to accept a string of characters and then encode a set of rules to determine how to interpret these characters. This is done in general terms, using grammar to encode these rules; but grammars can be tricky for what is probably an easy task.

Let me make 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 enter the Parse input.

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

• a int consists solely of numbers, optionally with a prefix -
• a double consists exclusively of numbers, not more than one . and optionally with a prefix -
• a string can be anything, so our catch-all

Then we can record 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 along with the guessing logic, parsing finally appears:

 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 ready. Now we need to determine how to compare the two inputs. This is easy if they all have the same type, if not, you will need to define arbitrary logic. You can convert an Int input to a Double input quite easily, but for a string it is a bit more 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, since I don't know the types you want to deal with. I decided an arbitrary set;) However, this should give you a skeleton to be based on it.

Answer 2

Considering the actual requirements of the problem outlined in the comments, I suggest that you store all the inputs in std::vector<std::string> and sort the vector using std :: sort . Thus, instead of worrying about the different types, you can specify the sorting logic depending on what you interpret in your vector for the view. So

• Implementing sorting functions for rows depending on what the rows represent (later)
• store inputs as strings in vector.
• Determine what type of string represent
• select a sorting function based on this type
• Sort a vector using std::sort and the corresponding sort function.

As for the sort function, std::sort accepts a binary functor or function that applies a “smaller” comparison with two elements, so your functors or functions should look something like this:

 bool foo(const std::string& rhs, const std::string& lhs) { // implement the logic } 

Change Looking at more recent comments, it seems that the main goal, if this exercise, may have been to implement sorting algorithms for different types. In this case, I would like to propose the approach used by the standard C ++ library, that is, implement sorting in terms of or less than a comparison between the two types, thereby decoupling the sorting logic with the sortable types. Thus, you need a template sorting function, one that is iterator type, and a comparison function / functor.

Answer 3

If you know what types a user can enter, you can use templates and inheritance:

 class Generic { public: virtual void process_input() = 0; // Handles the next input from user virtual void process_output() = 0; // Processes the data inserted }; template <typename T> class HandleInput : public Generic { private: std::vector<T> storage; public: HandleInput(T first) { storage.push_back(first); } void process_input() { // do whatever you want } void process_output() { // do whatever you want } }; int main(int argc, char **argv) { // Get first input Input i = input(); Generic *g; // Instantiate the "right" generic with a switch switch (i.type) { case T: g = new HandleInput<T>(i.value); } // Use Generic from here onwards } 

That is just an idea ( Input cannot be implemented like that, you need to change this part using logic that receives something from the user and determines its type), but it has the advantage of masking the type into a general class, so you can code the code via the interface provided by Generic .

Another idea (easier, perhaps) is to use std::vector<void*> and enum , which tell you what type of data is stored in the vector. When you need to process this data somewhere in the future, you can enable the enumeration to appropriately pass the vector elements to the correct type and send them to the appropriate code.

EDIT : Another idea is to define a templated function that takes input and sorts the array using standard comparators:

 #include <iostream> #include <vector> #include <algorithm> #include <boost/lexical_cast.hpp> template <typename T> void print_v(std::vector<T> &v) { typename std::vector<T>::iterator it; for (it = v.begin(); it != v.end(); it++) std::cout << *it << " "; std::cout << std::endl; } template <typename T> void sort_and_print(T first, size_t n, bool asc) { std::vector<T> v; v.push_back(first); for (size_t i = 0; i < n; i++) { std::string s; std::cin >> s; T e = boost::lexical_cast<T>(s); v.push_back(e); } print_v(v); if (asc) std::sort(v.begin(), v.end(), std::greater<T>()); else std::sort(v.begin(), v.end()); print_v(v); } int main(int argc, char **argv) { std::string s = "test"; sort_and_print(s, 2, true); unsigned int j = 3; sort_and_print(j, 2, true); return 0; } 

The logic of determining the type of the first input is up to you (maybe you can open another question);)

Answer 4

There are two aspects to this question: parsing and sorting.

• You can use regular expressions to validate custom data types.
• You can use cin to analyze the data.

First: understand that you can’t know what type your users are entering until you get it all ~ for example: consider a list of usernames:

 728278243 390349346 495045594 elizabeth 

Therefore, it is better not to assume that it is better to know about the input data (this can lead to user frustration), but instead they prefer to consider everything as a potential string. Store all the source data as strings so you can output them in the same format as the input. you can use, say, an enumerated type to switch inside a sorting comparator, or consider using mutliset/multimap . here you will be building an ordered set. therefore there is no need to sort. NB: the difficulty of constructing an ordered set of N elements or, for one sort on N unsorted list elements, is roughly equivalent to ~> NlogN

For your task in your hand, this does not matter much, but in fact, depending on how this list is used, this or that approach will be much more suitable in terms of performance.

If you have already used similar std::vector , then std::multimap should not be too scary. Clearly, this is an associated array of key-value pairs. multi here means that it can store several elements with the same key (which is here, you want).

In this example, I use the regex boost library to define some funky input data types.
(e.g. sudo apt-get install libboost-regex1.46-dev )

This regular expression may seem cryptic, but there are many examples on i / web for almost all possible patterns. [NB: C ++ 11 regex is a pretty significant replacement for re-expressing boost. that is: boost regex should be compatible with the new version of C ++ 11]

blah.cpp:

 #include <iostream> #include <sstream> #include <string> #include <list> #include <map> #include <set> #include <boost/regex.hpp> //NB: GNU gcc added *experimental support for regular expressions in TR1 v 4.3.0. // compile with: -std=c++0x using namespace std; using namespace boost; //some example input data-types (perhaps notably missing a date!) const regex re_char("[^0-9]", regex_constants::extended); //non numeric chars const regex re_digit("[[:digit:]]+", regex_constants::extended); //a string of only digits in range [0..9] ~ie: Z+ const regex re_xdigit("0[xX][[:xdigit:]]+", regex_constants::extended); //support hex iff starts with '0x' or '0X' const regex re_float("[-+]?[0-9]*\\.?[0-9]+([eE][-+]?[0-9]+)?", regex_constants::extended); //all kinds of numbers int main(int argc, char** argv) { int i, countc=0; double d; string str; int element_count; do { cout << "how many elements will there be? "; if (cin >> element_count) break; cin.clear(); cin >> str; cout << "\033[A\033[2K" << flush; } while(13); cin.ignore(128,'\n'); multimap<double, string> list_num; multimap<double, string> list_fp; //NB: below, by way of example, construction using the 'greater<int>' comparison class achieves _descending_ order multimap<int, string, greater<int> > list_int; list<string> list_str; for (int next=0; next < element_count; next++) { cout << "\033[A\033[2K" << flush; cout << "enter next element in list ["<< next+1 << "/" << element_count << "] : "; getline (cin,str); if (regex_match(str, re_xdigit)) { //see all about manipulators here: //http://www.cplusplus.com/reference/iostream/istream/operator%3E%3E/ stringstream(str) >> hex >> i; list_int.insert(pair<int, string>(i, str)); list_num.insert(pair<double, string>(i, str)); } else if (regex_match(str, re_digit)) { stringstream(str) >> i; list_int.insert(pair<int, string>(i, str)); list_num.insert(pair<double, string>(i, str)); } else if (regex_match(str, re_float)) { stringstream(str) >> d; list_fp.insert(pair<double, string>(d, str)); list_num.insert(pair<double, string>(d, str)); } if (regex_match(str, re_char)) countc++; list_str.push_back(str); } cout << "\033[A\033[2K" << flush; cout << "input: unsorted list:" << endl; for (list<string>::iterator it=list_str.begin(); it!=list_str.end(); it++) cout << *it << endl; if (list_int.size() == element_count) { cout << endl << "output: sorted list of Z+ types:" << endl; for (multimap<int, string>::iterator it=list_int.begin() ; it != list_int.end(); it++ ) cout << (*it).second << endl; } else if (list_fp.size() == element_count) { cout << endl << "output: sorted list of fp types:" << endl; for (multimap<double, string>::iterator it=list_fp.begin() ; it != list_fp.end(); it++ ) cout << (*it).second << endl; } else if (list_num.size() == element_count) { cout << endl << "output: sorted list of numeric types:" << endl; for (multimap<double, string>::iterator it=list_num.begin() ; it != list_num.end(); it++ ) cout << (*it).second << endl; } else //output as sorted strings ~but in _descending_ order, using reverse iterator, by way of example { list_str.sort(); //but best to use list_str.sort(greater<string>()); with forward iterators cout << endl << "output: sorted list of " << (countc == element_count ? "non numeric char" : "string") << " types:" << endl; for (list<string>::reverse_iterator it=list_str.rbegin(); it!=list_str.rend(); ++it) cout << *it << endl; } return 0; } 

The example was compiled and run on Ubuntu. Command Line Material:

 $ $ lsb_release -d Description: Ubuntu 11.10 $ g++ --version g++ (Ubuntu/Linaro 4.6.1-9ubuntu3) 4.6.1 $ g++ --pedantic -oblah blah.cpp -lboost_regex $ ./blah input: unsorted list: 4.77 2.0e+2 -.3 11 0x10 output: sorted list of numeric types: -.3 4.77 11 0x10 2.0e+2 $ 

NB: This is a sample code:

• There are many optimizations you can do here. You clearly do not need as many stl containers as I use.
• I do not strictly understand this kind of direction (but I will show a couple of ways in which this can be achieved).
• It may also be convenient to encapsulate type-specific functions in C ++ objects; have a base class and then derived classes for each type you want to support ~, but is this homework right? -Therefore, it is probably not worth going overboard, then;)