c++ - 将未知类型的元素输入到向量中

Question

我正在开发一个程序，该程序从用户那里获取元素并对它们进行排序。对于这个程序，我必须使用向量，因为在用户输入之前元素列表的大小是未知的。我们的指示是：

用 C++ 编写一个程序来实现对元素列表的排序。元素可以是任何类型，但都是相同的类型，例如所有整数或所有浮点数或所有字符或所有字符串（字符串应像在字典中一样排序）。您可以实现您选择的任何排序算法。

询问用户会有多少元素

要求用户输入元素

要求用户选择排序顺序：升序或降序或两者

打印输入和输出列表

用户不会提供有关元素类型的任何信息

我对向量不是很熟悉（老师在课堂上基本上是略读主题），而且我的书并没有给我提供关于该主题的大量信息。我遇到的问题是在用户开始输入之前我不知道元素列表的类型。到目前为止，我已经尝试过：

创建一个 void 类型向量（现在我已经研究过了，显然不允许，哎呀）
通过将第一个元素发送给函数并让函数根据第一个元素的类型确定要创建的向量类型来重载一个函数insertInVector（当我想到它时，这似乎是我的最佳选择，除了我需要访问向量在函数终止之后，所以最终也是不行的）
#include <typeinfo>在程序中，找到第一个元素的类型，然后使用创建一个向量vector<typeid(firstElement).name()>，老实说，我不确定为什么这不起作用，但它没有。

就像我说的那样，我对向量的经验非常有限，因为这是我第一次使用它们。我也是一个相当新的程序员，所以我在这方面所做的很多研究都超出了我的想象。任何可以在这方面提供的帮助将不胜感激！

score 5 · Accepted Answer

C++ 是一种静态类型的语言。这意味着所有类型都应该在编译期间确定：在运行程序时不能引入新类型。

创建一个 void 类型向量（现在我已经研究过了，显然不允许，哎呀）

void实际上是一个很奇怪的类型，主要是一个占位符，当你期望一个类型（比如一个函数返回类型）并且没有提供时。void*被用作指向未知类型的指针（主要在 C 中），但这是一个相当黑客，因为有关原始信息的信息被丢弃（就语言而言）所以这会导致问题实际上用值做事情所以获得。

通过将第一个元素发送到函数并让函数根据第一个元素的类型确定要创建的向量类型来重载名为 insertInVector 的函数

#include <typeinfo>在程序中，找到第一个元素的类型，然后使用创建一个向量vector<typeid(firstElement).name()>，老实说，我不确定为什么这不起作用，但它没有。

不幸的是，两者都不可能：既然你不能声明一个没有类型的变量，那么以什么firstElement开头的类型是什么？

你所描述的问题一般来说是困难的。基本上，这意味着您必须接受一串字符，然后编写一组规则来确定如何解释这些字符。这通常是通过使用语法对这些规则进行编码来完成的；但是对于可能是一项简单的任务，语法可能会很复杂。

让我举一个小例子：

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;
};

显然，真正的挑战是正确Parse输入。

这个想法是使用一组规则，例如：

anint仅由数字组成，可选前缀-
adouble仅由数字组成，最多有一个.，并且可以选择前缀-
astring可以是任何东西，因此是我们的包罗万象

然后我们可以编写方法的识别部分Parse：

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

再加上猜测逻辑，最后解析出来了：

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

呸！

所以？差不多好了。现在我们需要确定如何比较两个输入。如果它们都具有相同的类型，这很容易，否则您将需要确定任意逻辑。您可以很容易地在输入 Double 中转换输入 Int，但对于字符串来说它有点奇怪。

// 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<

最后，程序：

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;
}

当然，因为我不知道您希望处理的类型.. 我已经决定了一个任意的集合；）但是，这应该给您一个基础的骨架。

score 3 · Accepted Answer

查看评论中所述问题的实际要求，我建议您将所有输入存储在 an 中并使用std::sortstd::vector<std::string>对向量进行排序。因此，您不必担心不同的类型，而是可以根据您解释向量中要表示的字符串的内容来指定排序逻辑。所以

根据字符串表示的内容为字符串实现排序功能（稍后会详细介绍）
将输入作为字符串存储在向量中。
确定字符串代表的类型
选择基于此类型的排序功能
std::sort使用和适当的排序函数对向量进行排序。

关于排序函数，std::sort接受一个二进制函子或对两个元素应用“小于”比较的函数，所以你的函子或函数应该看起来像

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

编辑：查看最近的评论，似乎练习的主要目的可能是为不同类型实现排序算法。在这种情况下，我建议遵循 C++ 标准库采用的方法，即在两种类型之间实现术语排序或小于比较，从而将排序逻辑与要排序的类型解耦。因此，您需要一个模板排序函数，以迭代器类型和比较函数/函子为模板。

score 1 · Accepted Answer

如果您知道用户可能输入的类型，您可以使用模板和继承：

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
}

这只是一个想法（Input不能这样实现，您需要使用从用户那里获取某些内容并确定其类型的逻辑来更改该部分），但它具有将类型屏蔽为泛型类的好处，因此您可以考虑您的代码围绕由Generic.

另一个想法（可能更简单）是使用 astd::vector<void*>和 anenum来告诉您存储在向量中的数据的类型是什么。当您需要在将来某个地方处理该数据时，您可以打开枚举以将向量元素适当地转换为正确的类型并将它们分派给适当的代码。

编辑：另一个想法是定义一个模板化函数，该函数接受输入并使用标准比较器对数组进行排序：

#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;
}

确定第一个输入类型的逻辑取决于您（也许您可以打开另一个问题）；）

score 1 · Accepted Answer

这个问题有两个方面：解析和排序。

您可以使用正则表达式来检查用户输入的数据类型。
您可以使用cin来解析数据。

首先：意识到在收到所有用户输入之前，您不一定知道用户输入的类型〜例如：考虑用户名列表：

728278243
390349346
495045594
elizabeth

因此，最好不要假设最了解传入数据（可能导致令人沮丧的用户体验），而是更愿意将所有内容视为潜在的字符串。将所有原始输入存储为字符串，以便您可以以与输入相同的格式输出。您可以使用枚举类型在排序比较器内部进行切换，或者考虑使用mutliset/multimap. 在这里，您将构建一个有序集。所以不需要排序。NB：构造一个有序集合的 N 个元素的复杂度，或者对于 N 个未排序的列表元素进行单一排序，其复杂度大致相等 ~> NlogN

对于您手头的任务，这几乎不重要，但实际上取决于列表的使用方式，在性能方面，一种或其他方法将更合适。

如果你已经使用过std::vectorthen之类的std::multimap应该不会太吓人。松散地说，它是一个关联的键值对数组。这里的multi意味着它可以使用相同的键存储多个元素（在这里，你想要）。

在这个例子中，我使用boost regex 库来确定一些时髦的输入数据类型。
（例如sudo apt-get install libboost-regex1.46-dev：）

这个正则表达式可能看起来晦涩难懂，但 i/web 上有许多示例，几乎适用于所有可以想象的模式。[注意：C++11 正则表达式几乎是 boost 正则表达式的替代品。即：boost regex 应该与新兴的 C++11 标准前向兼容]

废话.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;
}

示例在 Ubuntu 上编译和运行。命令行的东西：

$
$ 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
$

注意：这是示例代码：

这里可以进行许多优化。您显然不需要像stl我使用的那么多容器。
我没有严格处理排序的方向（但展示了几种可能实现的方法）。
将特定于类型的功能封装在 C++ 对象中也可能很好；对于您希望支持的每种类型都有一个基类和派生类~但是这个作业对吗？- 所以可能不值得过火；）

c++ - 将未知类型的元素输入到向量中

4 回答 4

Related

Reference