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

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

11 голосов
/ 18 января 2012

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

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

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

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

Редактировать

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

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

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

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

00001

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

00011

00101

01001

10001

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

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

Ответы [ 4 ]

14 голосов
/ 18 января 2012

У вас не будет проблем с этим, так как std :: vector предоставляет вам операторы "==", "<" и ">":

http://en.cppreference.com/w/cpp/container/vector/operator_cmp

6 голосов
/ 18 января 2012

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

2 голосов
/ 18 января 2012

Это должно сработать, как отмечает Ренан Грейнерт, 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
}
0 голосов
/ 18 января 2012

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

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

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