C ++: как сравнить несколько векторов, а затем создать новый отсортированный вектор, содержащий ВСЕ элементы всех векторов

Question

Обновление : у меня есть пара глупых вопросов об ответе комментатора 6502 (ниже). Если бы кто-нибудь мог помочь, я был бы очень признателен.

1) Я понимаю, что данные 1 и данные 2 являются картами, но я не понимаю, для чего allkeys . Кто-нибудь может объяснить?

2) Я знаю, что: data1 [vector1 [i] .name] = vector1 [i] .value; означает присвоить значение карте интереса, где правильная метка ... Но я не понимаю этого: vector1 [i] .name и vector1 [i] .value, Разве «имя» и «значение» не являются двумя отдельными векторами меток и значений? Так что же они делают на vector1? Разве это не должно читаться, name [i] и value [i] вместо этого?

Спасибо всем.

---

Я написал код для выполнения расчета. Код использует данные из других источников. Код расчета в порядке, но мне не удается манипулировать данными.

Данные существуют в виде наборов векторов. Каждый набор имеет один вектор меток (имена, это строки) и соответствующий набор значений (двойные или целые).

Проблема в том, что каждый набор данных должен иметь такое же имя / метку в том же столбце, что и другие наборы данных. Эта проблема не то же самое, что сортировка данных в векторах (что я знаю, как делать), потому что иногда имена / метки могут отсутствовать в некоторых векторах.

Например:

Набор данных 1:

vector names1 = Джим, Том, Мэри

векторные значения1 = 1 2 3

Набор данных 2:

vector names2 = Том, Мэри, Джоан

векторные значения2 = 2 3 4

Я хочу (псевдокод) ОДИН вектор имен, который имеет все возможные имена. Я также хочу, чтобы каждый соответствующий вектор чисел сортировался одинаково:

vector namesUniversal = Джим, Джоан, Мэри, Том

векторные значенияUniversal1 = 1 0 3 2

векторные значенияUniversal2 = 0 4 3 2

Я хочу создать универсальный вектор, содержащий ВСЕ метки / имена, отсортированные в алфавитном порядке, и все соответствующие числовые данные, также отсортированные.

Может кто-нибудь сказать мне, есть ли элегантный способ сделать это в C ++? Я думаю, я мог бы сравнить каждый элемент каждого вектора имен с каждым элементом каждого вектора имен, но это кажется довольно неуклюжим, и я бы не знал, как получить данные в правильные столбцы в соответствующих векторах данных. Спасибо за любой совет.

Answer 1

Алгоритм, который вы ищете, обычно называется «объединением».По сути, вы сортируете два набора данных, а затем просматриваете данные попарно: если ключи равны, то вы обрабатываете и выводите пару, в противном случае вы обрабатываете и продвигаете только самый маленький из них.

Вы также должны обработать регистргде один из двух списков заканчивается перед другим (этого можно избежать, используя специальные значения флага, которые гарантированно будут выше любого значения, которое вам нужно обработать).

Ниже приведен псевдокод для объединения

1. Сортировка vector1
2. Сортировка vector2
3. Установка index1 = index2 = 0;
4. Цикл до обоих index1 >= vector1.size() и index2 >= vector2.size() (другими словамипока оба вектора не будут исчерпаны)
5. Если index1 == vector1.size() (т.е., если vector1 был обработан), то выведите vector2[index2++]
6. В противном случае, если index2 == vector2.size() (то есть, если vector2 былообработано), затем выведите vector1[index1++]
7. В противном случае, если vector1[index1] == vector2[index2], выведите объединенные данные и увеличьте значения index1 и index2
8. В противном случае, если vector1[index1] < vector2[index2], выведите vector1[index1++]
9. В противном случае выведите vector2[index2++]

Однако в C ++ вы можете реализоватьНамного проще написать решение, которое, вероятно, все еще достаточно быстрое (предупреждение: непроверенный код!):

std::map<std::string, int> data1, data2;
std::set<std::string> allkeys;

for (int i=0,n=vector1.size(); i<n; i++)
{
    allkeys.insert(vector1[i].name);
    data1[vector1[i].name] = vector1[i].value;
}

for (int i=0,n=vector2.size(); i<n; i++)
{
    allkeys.insert(vector2[i].name);
    data2[vector2[i].name] = vector2[i].value;
}

for (std::set<std::string>::iterator i=allkeys.begin(), e=allkeys.end();
     i!=e; ++i)
{
   const std::string& key = *i;
   std::cout << key << data1[key] << data2[key] << std::endl;
}

Идея состоит в том, чтобы просто построить две карты data1 и data2 от имени к значениям,и в то же время собирает все ключи, которые появляются в std::set ключей с именем allkeys (многократное добавление одного и того же имени к набору ничего не дает).

После фазы сбора этот набор может затемвыполнить итерацию, чтобы найти все обнаруженные имена, и для каждого имени значение можно извлечь из карт data1 и data2 (std::map<std::string, int> вернет 0 при поиске значения имени, которое не было добавлено ккарта).

Технически это своего рода избыточное убийство (использует три сбалансированных дерева для обработки, для которой потребовалось бы всего две операции сортировки), но при этом меньше кода и, вероятно, в любом случае приемлемо.

Answer 2

На первый взгляд решение

6502 выглядит отлично. Вы, вероятно, должны использовать std::merge для сливающейся части.

РЕДАКТИРОВАТЬ:

Я забыл упомянуть, что теперь существует также расширение multiway_merge STL, доступное в версии STL для GNU. Это часть параллельного режима, поэтому он находится в пространстве имен __gnu_parallel. Если вам нужно выполнить многопоточное объединение, будет очень сложно придумать что-нибудь столь же быстрое или простое в использовании, как это.

Answer 3

Быстрый способ, который приходит на ум, - это использовать map<pair<string, int>, int>, и для каждого значения сохраняйте его на карте с помощью правильного ключа.(Например (Tom, 2) в первом наборе значений будет находиться под ключом (Tom, 1) со значением 2). Когда карта будет готова, выполните итерацию по ней и создайте любую структуру данных, которую вы хотите (Предполагая, что карты недостаточно длявы).

Answer 4

Я думаю, вам нужно изменить способ хранения этих данных.Похоже, вы говорите, что каждое число логически связано с именем в одной и той же позиции: Джим = 1, Мэри = 3 и т. Д.

Если это так, и вы хотите придерживаться vector изВ некотором роде вы можете переделать свою структуру данных следующим образом:

typedef std::pair<std::string, int> NameNumberPair;
typedef std::vector<NameNumberPair> NameNumberVector;

NameNumberVector v1;

Вам нужно написать свой собственный operator<, который возвращает на основе порядка сортировки базовых имен.Однако, как указывает Наваз, map был бы лучшим способом для представления связанного характера данных.