Получение подсчета строк в векторе C++

У меня есть этот векторПолучение подсчета строк в векторе C++

vector <string> data 

data = ["this is", "data that", "is in", "this is", "vector", "vector", "vector"]

как я получаю вектор (или 2D массив), который удаляет дубликаты и вместо этого имеет счетчики для каждой записи-го?

т.е.

results = [("this is", 2), ("data that", 1), ("is in", 1), ("vector", 3)]

источник

2012-05-23 CyberShot

Xeo, я пробовал много подходов. то есть для каждой строки s в данных, посмотрите остальные элементы в данных и количество инкрементов для каждого совпадения s. похоже, что это O (n^2), но я ищу что-то более эффективное – CyberShot

Возможно, вы захотите попробовать 'std :: map ' ... вы можете индексировать по строке и увеличивать счетчик как необходимо. 'map' сортируются по ключу (здесь строка) и не могут иметь дубликатов. Чтобы взять несортированный список/вектор строк и заполнить карту, это операция O (N x log2N). –

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

Прямое решение будет накапливать уникальные значения и их подсчета в карту:

std::map<std::string, std::size_t> results; 
std::for_each(begin(data), end(data), [&](std::string const& s) 
{ 
    ++results[s]; 
});

Это linearithmic (п Л.Г. п) сложности, хотя из-за него должен сделать копию каждого отдельного строкового значения, это может быть довольно дорого. Вы также можете отсортировать список на месте, а затем подсчитать количество каждого значения, которое, вероятно, будет работать лучше, если у вас есть реализация с поддержкой перемещения std::string.

источник

2012-05-23 23:59:25

Вы также можете просто использовать ключ 'std :: reference_wrapper '. – Xeo

как насчет таблицы хэшей? http://en.wikipedia.org/wiki/Hash_table (сложность O (n)) –

@MihaiTodor: Просто измените 'std :: map' на' std :: unordered_map' – Blastfurnace

Получение подсчета строк в векторе C++

ответ

Смежные вопросы