C ++ установить поиск пары элементов? - PullRequest
Новая
       62

C ++ установить поиск пары элементов?

5 голосов
/ 23 марта 2012

Итак, у меня есть набор pairs<string ,string>

И я хочу использовать find() для поиска единственной строки, которая будет в «первой» пары, затем, если я найду эту строку первой, я хочу вернуть вторую из этой функции.

Моя текущая попытка .. 

myList::iterator i;

i = theList.find(make_pair(realName, "*"));

return i->second;

Ответы [ 3 ]

6 голосов
/ 31 мая 2013

C ++ 11 приемлем? 

auto it = find_if(theList.begin(), theList.end(),
    [&](const pair<string, string>& val) -> bool {
        return val.first == realName;
    });

return it->second;

Или в C ++ 03 сначала определите функтор: 

struct MatchFirst
{
        MatchFirst(const string& realName) : realName(realName) {}

        bool operator()(const pair<string, string>& val) {
                return val.first == realName;
        }

        const string& realName;
};

тогда назовите это так: 

myList::iterator it = find_if(a.begin(), a.end(), MatchFirst(realName));
return it->second;

Это вернет только первый матч, но из вашего вопроса похоже, что это все, что вы ожидаете.

2 голосов
/ 23 марта 2012

Для этого вы можете использовать std::set<std::pair<std::string, std::string> >, но для этого вам понадобится специальный объект сравнения, потому что реляционный оператор пары принимает для этого оба элемента.Тем не менее, кажется, что вы на самом деле должны использовать std::map<std::string, std::string> вместо.

1 голос
/ 24 марта 2012

Определение < для std::pair реализует лексикографический порядок, а "" является минимальным элементом для строк.Комбинируя это, мы получаем: 

 typedef std::pair<std::string, std::string> StringPair;
 typedef std::set<StringPair> Set;

 std::string const* find_first(Set const& s, std::string const& key) {
   Set::const_iterator const it = s.lower_bound(std::make_pair(key, ""));

   // Check that it actually points to a valid element whose key is of interest.
   if (it == s.end() or it->first != key) { return 0; }

   // Yata!
   return &it->second;
 }

Трюк использует lower_bound соответственно.

Возвращает итератор, указывающий на первый элемент, который сравнивается не менее чем value.

  • Если он возвращает end(), то он не нашел ничего интересного.
  • В противном случае it->first >= key, поэтому мы избавляемся от случая > (изнас это не интересует)

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

typedef std::pair<Set::const_iterator, Set::const_iterator> SetItPair;

SetItPair equal_range_first(Set const& s, std::string const& key) {
  StringPair const p = std::make_pair(key, "");
  return std::make_pair(s.lower_bound(p), s.upper_bound(p));
}

Это вернет полный диапазон узлов в s, чей первый элемент равен key.Затем вам просто нужно перебрать этот диапазон: 

for (Set::const_iterator it = range.first; it != range.second; ++it) {
  // do something
}

И вам даже не нужно беспокоиться о том, закончился ли возврат lower_bound или upper_bound или нет.

  • если lower_bound возвращает end(), то upper_bound и цикл пропускаются
  • , если lower_bound указывает на узел, для которого it->first > key, то upper_bound будет указыватьк тому же узлу, и цикл пропускается

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

...