Автоматическая кластеризация с хэшем / картой векторов в C ++

Question

У меня есть следующие значения, например:

0 0 0 1 3 2

Эти значения относятся к идентификаторам кластера, где членом кластера является индекс вектора. Следовательно, мы хотим получить такой вывод:

Cluster 0 -> 0,1,2
Cluster 1 -> 3
Cluster 2 -> 5
Cluster 3 -> 4

Я попробовал следующую конструкцию, но она не работает: Как это сделать?

#include <iostream>      
#include <vector>        
#include <fstream>
#include <sstream>
#include <map>
using namespace std;

int main  ( int arg_count, char *arg_vec[] ) {
    if (arg_count !=2 ) {
        cerr << "expected one argument" << endl;
        return EXIT_FAILURE;      
    }

    string line;
    ifstream myfile (arg_vec[1]);

    map <int, vector <int> > CCTagMap;

    if (myfile.is_open())
    {
        // Skip First Line        
        getline(myfile,line);     

        while (getline(myfile,line) )
        {
            stringstream ss(line);    
            int CcId;
            int TagId = -1;           



            vector <int> Temp;        

            while (ss >> CcId) {      
                TagId++;
                cout << CcId << "-" << TagId <<  endl; 

                # this way to cluster doesn't seem to work
                CCTagMap.insert(make_pair(CcId,Temp.push_back(TagId)));
            }


        }
        myfile.close();
    }
    else  { cout << "Unable to open file\n";} 
    return 0;
}

Answer 1

Я предполагал, что выложу решение для повышения производительности (помните, вы всегда должны стараться оптимизировать как можно скорее согласно Кнуту!, Если я не ошибаюсь;)).

CCTagMap[CcId].push_back(TagId);

Да, я действительно думал, что должен указать это решение ...

• сохрани набрав
• более производительный: только один поиск, вместо одного для поиска и одного для вставки. Нет временных (хотя они, вероятно, все равно будут оптимизированы).
• идиоматик?

Для разложенного представления о том, что здесь происходит:

std::vector<int>& CcVector = CcTagMap[CcId]; // [1]
CcVector.push_back(TagId);                   // [2]

1. map::operator[] является оператором мутации: он возвращает либо элемент, сохраненный для этого ключа, либо вставляет вновь созданный элемент по умолчанию, если его не было. Затем он возвращает ссылку на элемент (новый или нет).
2. Мы используем ссылку для прямого push_back, красиво и чисто.

Answer 2

Вы перезаписываете вектор каждый раз во время вставки. Что вы можете сделать, это что-то вроде:

map <int, vector <int> >::iterator iter = CCTagMap.find(CcId);
if(iter == CCTagMap.end())
{
  vector <int> Temp;  
  temp.push_back(TagId);
  CCTagMap[CcId] = temp;
}
else
{
  iter->second.push_back(TagId);
}

Answer 3

Как насчет этого? Вместо вашего CCTagMap определите:

std::vector<std::vector<int> > clusters;

затем для каждого TagId и CcId делайте:

if (clusters.size() <= CcId)
  clusters.resize(CcId + 1);
clusters[CcId].append(TagId);

Answer 4

То, что вы делаете неправильно, каждый раз переписывает векторы на карте.

Вместо:

CCTagMap.insert(make_pair(CcId,Temp.push_back(TagId)));

Попробуйте:

if ( CCTagMap.find( CcId ) == CCTagMap.end() )
{
    CCTagMap.insert(make_pair(CcId,vector<int>()));
}
CCTagMap[CcId].push_back( TagId );

Или даже лучше,

map <int, vector<int> >::iterator iter = CCTagMap.find(CcId);
if ( iter == CCTagMap.end() )
{
    CCTagMap.insert(make_pair(CcId,vector<int>())).first->second.push_back( TagId );
}
else
{
    iter->second.push_back( TagId );
}