c++ - ベクトルへの未知の型の要素の入力

Question

ユーザーから要素を取得して並べ替えるプログラムに取り組んでいます。このプログラムでは、要素リストのサイズがユーザー入力前に不明であるため、ベクトルを使用する必要があります。私たちの指示は次のとおりです。

C++ でプログラムを作成して、要素のリストの並べ替えを実装します。要素は任意の型にすることができますが、すべて整数、すべて浮動小数点、すべて文字、またはすべて文字列のように、すべて同じ型になります (文字列は辞書のように並べ替えられます)。任意のソート アルゴリズムを実装できます。

1. そこにいくつの要素があるかをユーザーに尋ねます
2. ユーザーに要素の入力を求める
3. 昇順、降順、またはその両方の並べ替え順序をユーザーに選択してもらいます
4. 入力リストと出力リストの両方を印刷する
5. ユーザーは要素のタイプに関する情報を提供しません

私はベクトルにあまり詳しくなく (先生は基本的にクラスでトピックをざっと読みました)、私の本はこの主題に関する多くの情報を提供してくれません。私が直面している問題は、ユーザーが入力を開始するまで要素リストの型がわからないことです。これまでのところ、私は試しました：

• void型ベクトルの作成（私が調査した今では明らかに許可されていません、おっと）
• insertInVector最初の要素を関数に送信し、関数に最初の要素の型に基づいて作成するベクトル型を決定させることによって呼び出される関数をオーバーロードします(これは、ベクトルにアクセスする必要があることを除いて、考えたときに私の最良の選択肢のように思えました)関数が終了した後、それもダメになった）
• #include <typeinfo>プログラムでは、最初の要素の型を見つけてからベクトルを作成しvector<typeid(firstElement).name()>、正直に言って、なぜそれがうまくいかなかったのかわかりませんが、うまくいきませんでした。

私が言ったように、ベクターを使用するのはこれが初めてなので、ベクターの経験は非常に限られています。私はかなり新しいプログラマーでもあるので、これについて行った多くの調査は頭を悩ませています。これで与えられるどんな助けでも大歓迎です!

Answer 1

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は数字だけで構成され、最大で 1 つ.、オプションでプレフィックス-
• 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

ふぅ！

そう ？もうすぐです。次に、2 つの入力を比較する方法を決定する必要があります。それらがすべて同じ型であれば簡単ですが、そうでない場合は任意のロジックを決定する必要があります。入力 Int を入力 Double に簡単に変換できますが、文字列の場合は少し奇妙です。

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

もちろん、あなたが対処したいタイプがわからないので..私は任意のセットを決めました;)しかし、これはあなた自身の基礎となるスケルトンを与えるはずです.

Answer 2

コメントに記載されている問題の実際の要件を見て、すべての入力を に格納し、std::sortstd::vector<std::string>を使用してベクトルをソートすることをお勧めします。したがって、さまざまな型について心配する代わりに、ベクター内の文字列を解釈して何を表現するかに応じて、並べ替えロジックを指定できます。そう

1. 文字列が表すものに応じて、文字列の並べ替え関数を実装します (後で詳しく説明します)。
2. 入力を文字列としてベクトルに格納します。
3. 文字列が表す型を判別する
4. このタイプに基づいてソート関数を選択します
5. std::sort適切なソート関数を使用してベクトルをソートします。

Concerning the sorting function, std::sort accepts a binary functor or function that applies a "less-than" comparison to two elelemts, so your functors or functions should look something like

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

Edit: Looking at more recent comments, it seems that the main purpose if the exercise might have been to implement sorting algorithms for different types. In that case, I would suggest following the approach taken by the C++ standard library, that is, to implement sorting in terms or a less-than comparison between two types, thereby decoupling the sorting logic from the types to be sorted. So you would want a template sorting function, templated on iterator type and comparison function/functor.

Answer 3

ユーザーが入力できるタイプがわかっている場合は、テンプレートと継承を使用できます。

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*>と anを使用することです。enum将来そのデータを処理する必要がある場合は、列挙型をオンにして、ベクター要素を正しい型に適切にキャストし、適切なコードにディスパッチできます。

編集: 別のアイデアは、入力を受け取り、標準のコンパレータを使用して配列をソートするテンプレート化された関数を定義することです。

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

最初の入力のタイプを決定するロジックはあなた次第です（別の質問を開くことができるかもしれません）;）

Answer 4

この質問には、解析と並べ替えという 2 つの側面があります。

• 正規表現を使用して、ユーザー入力のデータ型を確認できます。
• を使用cinしてデータを解析できます。

最初に:すべてのユーザー入力を受け取るまで、必ずしもユーザー入力のタイプを知ることはできないことを理解してください~eg: ユーザー名のリストを検討してください:

728278243
390349346
495045594
elizabeth

したがって、受信データについて最もよく知っていると仮定しないでください (イライラするユーザーエクスペリエンスにつながる可能性があります)。代わりに、すべてを潜在的な文字列として扱うことを好みます。入力と同じ形式で出力できるように、すべての生の入力を文字列として保存します。たとえば、列挙型を使用して並べ替えコンパレータ内で切り替える か、mutliset/multimap. ここでは、順序付きセットを作成します。したがって、並べ替える必要はありません。注意: N 個の要素の順序付けられたセットを構築するための複雑さ、またはN個の並べ替えられていないリスト要素の単一の並べ替えの場合、おおよそ同等です ~> NlogN

手元のタスクではほとんど問題になりませんが、実際には、リストの使用方法に応じて、パフォーマンスの観点から、いずれかのアプローチがはるかに適切になります。

のようなものをすでに使用している場合は、std::vectorそれほどstd::multimap怖くないはずです。大まかに言えば、これはキーと値のペアの関連配列です。ここでのmultiは、同じキーを持つ複数の要素を格納できることを意味します (ここでは必要です)。

この例では、ファンキーな入力データ型 を特定するために、ブースト正規表現ライブラリを使用しています。(例: )
sudo apt-get install libboost-regex1.46-dev

この正規表現は難解に思えるかもしれませんが、考えられるほぼすべてのパターンについて i/web に多くの例があります。[注意: C++11 正規表現は、ほとんどブースト正規表現のドロップイン代替品です。つまり、ブースト正規表現は、新しい 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++ オブジェクトにカプセル化するのもよいでしょう。サポートしたいタイプごとに基本クラスと派生クラスがありますが、この宿題は正しいですか？-そのため、おそらく船外に出る価値はありません;）