26

次のデータがあります。

FolioA Name1 100
FolioA Name2 110
FolioA Name3 100
FolioB Name1 100
FolioB Name3 106
FolioC Name1 108
FolioC Name2 102
FolioC Name3 110

一意の名前 (つまり、Name1、Name2、および Name3 をそれぞれ 1 回ずつ) だけ挿入したい

std::vector<std::string> name;

データを繰り返します。

したがって、test というマップにデータを保存した次のコードがあります。

std::map<std::string, std::map<std::string, double> >test;
std::map<std::string, std::map<std::string, double > >::iterator it1 = test.begin(), end1 = test.end();
    while (it1 !=end1) {
        std::map<std::string, double>::iterator it2 = it1->second.begin(), end2=it1->second.end();
        **name.push_back(it2->first);**
        ++it2;
    }
    ++it1;
}

しかし、現在、データを名前にプッシュすることで、コードから予想される Name1 の 3 つのインスタンス、Name2 の 2 つ、および Name3 の 3 つのインスタンスがあります。一意の名前のみを持つように修正するにはどうすればよいですか。

4

5 に答える 5

37

特定の名前の最初のインスタンスを保持したいので、ある時点で名前検索を実行する必要があります。ベクターのみを含む単純なアルゴリズムは、std::findを使用してエントリが既に存在するかどうかを確認することです。

std::vector<std::string> name;

....
if (std::find(name.begin(), name.end(), someName) == name.end()) {
  // someName not in name, add it
  name.push_back(someName);
}

しかし、ここでは、要素を挿入するたびに検索を実行しています。これは (それ自体で)O(N)複雑にO(N*N)なり、アルゴリズム全体に影響を与えます。std::setそのため、@Chad によって提案され、ルックアップがO(logN)複雑でO(N*logN)全体的に複雑な、または C++11 のstd::unordered_setなどのハッシュ コンテナーなど、高速なルックアップを備えた中間コンテナーを使用して最適化できます。一定時間のルックアップに近く、~O(N) 全体の複雑さを与えます。

#include <unordered_set>

std::unordered_set<std::string> name_set;
....

// still need to search, since you want to keep 
// the first instance of each name, and not the last.
// But unordered_set performs the look-up at insertion,
// only inserting if someName not already in the set
name_set.insert(someName);

そして、@Chadの例に従って、

std::vector<std::string> name(names_set.begin(), name_set.end());

C++11 がない場合、ハッシュ マップの代替手段はboost::hash_mapとtr1::hash_mapです。

于 2012-04-29T21:27:24.110 に答える
3

あなたはサンプルコードを求めたので、私がそれを行う方法は次のとおりです。

std::set<std::string> unique_names;

// ...
while (it1 !=end1)
{
    // ...
    // **name.push_back(it2->first);**
    unique_names.insert(it2->first);
}

std::vector<std::string> name(unique_names.begin(), unique_names.end());
于 2012-04-29T23:12:51.517 に答える
2

list には .sort() と .unique() の機能があり、.

イテレータで反復処理し、initializer_list で初期化できます。

そのデータは、実際には構造体のように見えます。

#include <iterator>
#include <list>
#include <string>
#include <fstream>

typedef struct NODE_S {
    string name1, name2;
    int n;
} NODE_S NODE;

bool compare_NODE (NODE first, NODE second)
{
    unsigned int i=0;
    if (first.name1 < second.name1) {
        return true;
    } else if (first.name2 < second.name2) {
        return true;
    } else if (first.n < second.n) {
        return true;
    } else { return false;}
}


bool readfile(list<NODE>& ln, string filepath) {
    std::ifstream filein;
    NODE n;
    filein.open(filepath.c_str(), std::iofstream::in);
    if (!filein.good()) {
        filein.close();
        std::cerr << "ERROR: unable to open file \"" << filepath << "\" or file is zero-length." << std::endl;
        return false;
    }
    do {
        filein >> n.name1 >> n.name2 >> n.name3 >> std::skipws;
        ln.push_back(n);
        ln.sort(compare_NODE);
        ln.unique();
        //add node to list

    } while (!filein.good()); //can use .eof here, but if bad disk blocks...
    filein.close();
    return true;
}


int main(int argc, char * argv[], char * envp[]) {
    string filepath="somefile.txt";
    if (!readfile(filepath)) {
        return 1;
    }
    list<NODE>::iterator lni;
    for (lni = ln.begin(); lni != ln.end(); lni++) {
        std::cout<<lni->name1<<' '<<lni->name2<<' '<<lni->n<<std::endl;
    }
    return 0;
}

http://www.cplusplus.com/reference/stl/list/sort/

http://www.cplusplus.com/reference/stl/list/unique/

于 2012-04-30T06:50:00.933 に答える
2

データ構造に入力するインスタンスを気にしない場合は、std::setが目的を果たします

于 2012-04-29T21:24:51.160 に答える
2

一意の名前を付けるには、ベクトルの代わりに別のマップを使用する必要があるかもしれません。

std::map < std::string, double > name;

于 2012-04-29T21:32:16.140 に答える