Ввод уникальных данных в вектор

У меня есть следующие данные:

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, каждый раз) в

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

Но в настоящее время, вставляя данные в имя так, как у меня есть 3 экземпляра Name1, 2 Name2 и 3 Name3, что ожидается от моего кода. Как мне исправить это, чтобы иметь только уникальные имена.


person user1155299    schedule 29.04.2012    source источник
comment
Как бы вы выбрали, какой экземпляр включить?   -  person juanchopanza    schedule 30.04.2012
comment
Обязательно ли иметь vector имен? Вместо этого я бы предложил использовать set имен. Если вам нужен вектор, вы все равно можете сначала вставить в набор, а затем переместить объекты в vector с помощью перегрузки конструктора, которая занимает iterators.   -  person Chad    schedule 30.04.2012
comment
@juanchopanza, я бы выбрал первый экземпляр каждого, поэтому, если вектор уже содержит (Name1, Name2, Name3), то, когда он достигает 4-й записи, он определяет, что запись уже существует, поэтому пропускает ее и переходит к следующая запись.   -  person user1155299    schedule 30.04.2012
comment
@Chad, можешь опубликовать пример кода   -  person user1155299    schedule 30.04.2012


Ответы (5)


Поскольку вы хотите сохранить первый экземпляр для заданного имени, в какой-то момент вам придется выполнить поиск имени. Простой алгоритм, включающий только ваш вектор, может проверить, существует ли уже запись, используя std ::найти

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( Н) общая сложность.

#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());

Если у вас нет С++ 11, альтернативы хэш-карты — boost::hash_map и tr1::hash_map.

person juanchopanza    schedule 29.04.2012
comment
ага, похоже, что это может сделать это. Можете ли вы опубликовать пример кода о том, как я буду его использовать. - person user1155299; 30.04.2012
comment
алгоритм художника Шлемиэля. т.е. O(N*N). Это работает, но решение Чеда масштабируется гораздо лучше. - person MSalters; 30.04.2012
comment
@MSalters, возможно, вы можете объяснить, почему вы классифицируете это так, как делаете. Решение Чада тоже работает, но в чем ошибка вышеизложенного. - person user1155299; 30.04.2012
comment
@ user1155299 проблема в том, что этот алгоритм не очень эффективен, т. Е. Его сложность излишне высока. Я привел лучший пример с некоторыми пояснениями. - person juanchopanza; 30.04.2012
comment
@MSalters очень верно. Решение Чада не решает реальной проблемы, но очень близко к ней. Я обновил свой ответ некоторыми пояснениями. - person juanchopanza; 30.04.2012
comment
Здесь есть что-то, что ускользает от понимания. Почему в 1-м и 2-м блоках кода оператор != вместо ==? Разве мы не должны вставлять в случае, если его еще нет в коллекции? - person sergiol; 25.06.2015
comment
@sergiol Хороший улов! Я также злоупотреблял набором. Теперь все исправлено. - person juanchopanza; 25.06.2015
comment
@user1155299 user1155299 как это могло работать, когда у вас был оператор, который ведет себя прямо противоположно тому, что вы хотели? - person sergiol; 26.06.2015

Вы просили пример кода, вот как бы я это сделал:

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());
person Chad    schedule 29.04.2012

Если вам все равно, какой экземпляр вы хотите ввести в свою структуру данных, std:: set будет служить вашей цели

person Abhijit    schedule 29.04.2012

Возможно, вам следует использовать другую карту вместо вектора, чтобы иметь уникальные имена.

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

person phantasmagoria    schedule 29.04.2012

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/

person Jim Michaels    schedule 30.04.2012
comment
Вы захотите переместить вызовы sort и unique вниз, за ​​пределы цикла. Теперь они вызываются один раз в NODE. Кстати, штука typedef struct не нужна уже 20 лет. - person MSalters; 01.05.2012