Каков наилучший способ найти конкретную строку в векторе?

Question

Например. У меня есть структура:

s_Some{
  std::string lable;
  s_some_junk some_junk;
};

И вектор:

std::vector<s_Some> mSome;

А потом я заполняю этот вектор большим количеством s_Somes.

Мне нужно найти итератор для одного s_Some в этом векторе, который имеет конкретную метку. Пока что я просто перебираю весь этот мусор и сопоставляю каждую этикетку с желаемой. Это выглядит немного глупо для меня. Есть ли лучший способ сделать это?

Answer 1

Вариант 1) Если вы вынуждены использовать std :: vector, но как только вектор заполнен, он остается неизменным, тогда вы можете отсортировать вектор и использовать бинарный поиск. Единственной стоимостью будет сортировка, и никаких дополнительных затрат не будет. Время поиска логарифмическое O (logN).

Вариант 2) Если у вас есть свобода и вы можете выбрать другую структуру данных, рассмотрите возможность использования карты (также логарифмической) или unordered_map (ожидаемое O (1), худшее O (n)).

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

Answer 2

Если вы будете искать только несколько раз или если ваш вектор будет иметь разное содержимое каждый раз, когда вы будете искать, к сожалению, альтернативы нет; вам придется перебирать весь вектор.

Если, однако, ваш вектор не будет изменен после создания, и вам придется выполнить большое количество поисков, сделайте следующее:

1. Сортировка вектора в порядке возрастания строк (то есть, как они лежат в словаре).
2. После сортировки используйте алгоритм двоичного поиска для всех поисков.

Это будет намного быстрее.

Answer 3

Используйте

std::multimap< string, s_Some > mSome;

и

mSome.insert( std::make_pair( aSome.lable, aSome ) );

Найдите первый экземпляр значения метки, который вы хотите, по

mSome.find( lable_you_want );

Следующий экземпляр будет найден путем увеличения итератора.

ср. http://www.cppreference.com/wiki/stl/multimap/start

То есть, если вам не требуется использовать std :: vector.

Answer 4

Вы можете найти алгоритм для этого. Определите предикат примерно так:

struct isEqual
{
    isEqual(const std::string& s): m_s(s)
    {}
    bool operator()(S_Some& l)
    {
        return l.lable == m_s;
    }

    std::string m_s;
};

А при поиске вы можете использовать

std::vector<S_Some>::iterator iter = std::find_if(mSome.begin(),
                                                  mSome.end(),
                                                  isEqual(std::string("AAAA"));

Answer 5

Вы также можете использовать Карта из Списки