Подтвердить что ты не робот

STL-карта с вектором для ключа

Я работаю с некоторыми двоичными данными, которые я сохранил в произвольно больших массивах беззнаковых int. Я обнаружил, что у меня есть дублирование данных, и я стараюсь игнорировать дубликаты в краткосрочной перспективе и удалять все ошибки, вызывающие их в долгосрочной перспективе.

Я смотрю на вставку каждого набора данных на карту, прежде чем хранить его, но только если он не был найден на карте. Моя первоначальная мысль состояла в том, чтобы иметь карту строк и использовать memcpy в качестве молотка, чтобы заставить ints в массив символов, а затем скопировать это в строку и сохранить строку. Это не удалось, потому что многие мои данные содержат несколько байтов 0 (aka NULL) в начале соответствующих данных, поэтому большинство очень реальных данных были выброшены.

Моя следующая попытка планируется std::map<std::vector<unsigned char>,int>, но я понимаю, что я не знаю, будет ли работать функция вставки карты.

Возможно ли это, даже если это не рекомендуется, или есть лучший способ подойти к этой проблеме?

Изменить

Итак, было отмечено, что я не уточнил, что я делаю, поэтому здесь, надеюсь, лучшее описание.

Я работаю над созданием минимального связующего дерева, учитывая, что у меня есть несколько деревьев, содержащих фактические конечные узлы, с которыми я работаю. Цель состоит в том, чтобы придумать выбор деревьев с наименьшей длиной и охватывает все конечные узлы, где выбранные деревья разделяют друг с другом не более одного node и все связаны. Я основываю свой подход на двоичном дереве решений, но внесение нескольких изменений, надеюсь, позволит увеличить parallelism.

Вместо того, чтобы использовать подход с двоичным деревом, я решил сделать бит-вектор из целых без знака для каждого набора данных, где 1 в битовой позиции указывает на включение соответствующего дерева.

Например, если только дерево 0 было включено в набор данных дерева 5, я бы начал с

00001

Отсюда я могу сгенерировать:

00011

00101

01001

10001

Каждый из них может обрабатываться параллельно, поскольку ни один из них не зависит друг от друга. Я делаю это для всех одиночных деревьев (00010, 00100 и т.д.) И должен, я не нашел времени, чтобы официально доказать это, иметь возможность генерировать все значения в диапазоне (0,2 ^ n) один раз и только один раз.

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

4b9b3361

ОТВЕТЫ

Ответ 2

Требования для того, чтобы быть ключевым в std::map удовлетворяются std::vector, так что да, вы можете это сделать. Похоже на хорошее временное решение (легко кодировать, минимум хлопот), но вы знаете, что они говорят: "нет ничего более постоянного, чем временное".

Ответ 3

Это должно работать, как отмечает Ренан Грейнер, vector<> соответствует требованиям, которые будут использоваться в качестве ключа map.

Вы также говорите:

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

Обычно это не то, что вы хотите сделать, поскольку это будет связано с выполнением find() на карте, а если оно не будет найдено, выполните операцию insert(). Эти две операции по существу должны были бы сделать поиск дважды. Лучше просто попытаться вставить элементы на карту. Если ключ уже существует, операция не будет выполнена по определению. Таким образом, ваш код будет выглядеть так:

#include <vector>
#include <map>
#include <utility>

// typedefs help a lot to shorten the verbose C++ code
typedef std::map<std::vector<unsigned char>, int> MyMapType;

std::vector<unsigned char> v = ...; // initialize this somehow
std::pair<MyMapType::iterator, bool> result = myMap.insert(std::make_pair(v, 42));
if (result.second)
{
   // the insertion worked and result.first points to the newly 
   // inserted pair
}
else
{
   // the insertion failed and result.first points to the pair that
   // was already in the map
}

Ответ 4

Зачем вам нужен std::map? Возможно, я пропустил какой-то момент, но как насчет использования std::vector вместе с алгоритмом find, как показано здесь?

Это означает, что вы добавляете свой unsigned int к вектору и затем ищите его, например.

std::vector<unsigned int> collector; // vector that is substituting your std::map
for(unsigned int i=0; i<myInts.size(); ++i) {  // myInts are the long ints you have
    if(find(collector.begin(), collector.end(), myInts.at(i)==collector.end()) {
         collector.push_back(myInts.at(i));
    }
}