Поиск элементов с несколькими соответствиями

Question

У меня есть vector пар ключ-значение, где каждая пара ключ-значение также помечена кодом типа ввода. Возможные коды типа ввода:

enum Type
{
  tData = 0,
  tSeqBegin = 1,  // the beginning of a sequence
  tSeqEnd = 2     // the end of a sequence
};

Таким образом, сама пара ключ-значение выглядит следующим образом:

struct KeyVal
{
  int key_;
  string val_;  
  Type type_;
};

Внутри вектора находятся под-массивы дополнительных пар ключ-значение. Эти подмассивы называются «последовательностями». Последовательности могут быть вложены на любой уровень. Таким образом, последовательности могут иметь (необязательные) подпоследовательности различной длины. Комбинация Ключа и Type уникальна в элементе последовательности . То есть внутри одного элемента последовательности может быть только одна строка данных 269, но другие элементы последовательности могут иметь свои собственные строки данных 269.

Вот графическое представление некоторых выборочных данных, чрезмерно упрощенное (если столбец «Тип» пустой, он имеет тип tData):

Row#            Type            Key     Value      
----            -------------   -----   --------   
1                               35      "W"
2                               1181    "IBM"
3               tSeqBegin       268     "3"
4                               269     "0"
5                               270     "160.3"
6               tSeqEnd         0 
7                               269     "0"
8                               290     "0"
9               tSeqBegin       453     "1"      <-- subsequence
10              tSeqEnd         0                <-- end of subsequence
11              tSeqEnd         0
12                              269     "0"
13                              290     "1"
14                              270     "160.4"
15              tSeqEnd         0 
16                              1759    "ABC"

[РЕДАКТИРОВАТЬ: примечание на выше. Есть один tSeqBegin, который отмечает начало всей последовательности. Конец каждой последовательности элемент помечен tSeqEnd. Но не существует специального tSeqEnd, который также отмечает конец всей последовательности. Таким образом, для последовательности вы увидите 1 tSeqBegin и n tSeqEnd s, где n - количество элементов в последовательности.

Другое примечание: в приведенной выше последовательности, начинающейся в строке № 3 и заканчивающейся в строке № 15, во 2-м элементе есть одна подпоследовательность (строки 7–11). Подпоследовательность пуста и занимает строки 9 и 10.]

Я пытаюсь найти элемент последовательности, который имеет множественное значение Key-Value, соответствующее определенным критериям. Например, предположим, что я хочу найти элемент последовательности, который имеет как 269="0" , так и 290="0". В этом случае он не должен найти элемент # 0 (начиная со строки 3), потому что этот элемент вообще не имеет строки 290=.... Вместо этого он должен найти элемент, начинающийся с строки № 7. В конечном итоге я извлеку другие поля из этого элемента, но это выходит за рамки этой проблемы, поэтому я не включил эти данные выше.

Я не могу использовать std::find_if(), потому что find_if() будет оценивать каждую строку отдельно, а не весь элемент последовательности как единое целое. Поэтому я не могу построить функтор, который оценивает что-то вроде if 269=="0" &&* 290=="0", потому что ни одна строка никогда не оценит это как true.

Я думал реализовать свою собственную функцию find_sequence_element(...). Но это предполагает довольно сложную логику. Сначала я должен был бы идентифицировать begin() и end() всей последовательности, отмечая, где каждый элемент begin() и end(). Тогда мне нужно было бы построить какую-то структуру оценки, которую я мог бы связать вместе, как этот псевдокод:

Condition cond = KeyValueMatch(269, "0") + KeyValueMatch(290, "0");

Но это тоже сложно. Я не могу просто построить find_sequence_element(), который принимает ровно 2 параметра, один для совпадения 269 и другой для совпадения 290, потому что я хочу использовать этот алгоритм и для других последовательностей, с большим или меньшим количеством условий .

Более того, похоже, я должен быть в состоянии использовать уже существующие STL <algorithm>. Хотя я достаточно хорошо знаю STL, я не могу найти способ использовать find_if() каким-либо простым способом.

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

Некоторые условия:

• Я не могу изменить одну квартиру vector на vector of vectors или что-либо подобное. Причины этого сложны.

• (Заполнитель для большего количества условий :))

(Если все согласны с тем, что это должен быть CW, я отмечу это так)

Answer 1

Я хотел бы обработать в режиме онлайн. Есть тип, который отслеживает:

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

В вашем примере требования могут быть представлены как map<int,string>. В общем, они могут быть последовательностью двоичных предикатов или чем-то полиморфным, если вам нужно использовать разные функторы для разных условий в одном и том же наборе, а для эффективности эффективность может быть представлена ​​в виде последовательности логических значений, "этот предикат уже встречался? «

Когда вы видите tSeqEnd, вы очищаете набор удовлетворенных требований и начинаете снова. Если ваш счет достигает количества требований, все готово.

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

template<typename DataIterator, typename PredIterator>
DataIterator find_matching_sequence(
  DataIterator dataFirst,
  DataIterator dataLast,
  PredIterator predFirst,
  PredIterator predLast) {
    DataIterator sequence_start = dataFirst;
    size_t required = std::distance(predFirst, predLast);
    size_t sofar = 0;
    while (dataFirst != dataLast) {
        if (dataFirst->type == SeqEnd) {
            count = 0;
            ++dataFirst;
            sequence_start = dataFirst;
            continue;
        }
        sofar += std::count(predFirst, predLast, Matches(*dataFirst));
        if (sofar == required) return sequence_start;
        ++dataFirst;
    }
}

Если один и тот же предикат может соответствовать нескольким строкам в подпоследовательности, то вместо счетчика можно использовать vector<bool> или, возможно, valarray<bool>.

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

Так что не стоит серьезно использовать алгоритмы STL, если только вы не хотите std::copy вашего начального диапазона в выходной итератор, который выполняет онлайн-обработку; -)

Answer 2

Надеюсь, я правильно понимаю вашу настройку, я бы продолжил как двухэтапный способ, вложив алгоритмы поиска вдоль строк:

template<typename It, typename Pr>
It find_sequence_element ( It begin, It end, Pr predicate );

за исключением того, что Pr здесь есть предикат, который принимает1005 * sequence и возвращается, если эта последовательность совпадает, да или нет.Примером одного совпадения может быть:

class HasPair
{
    int key_; string value_;
public:
    Hasmatch ( int key, string value);
    template<typename It>
    bool operator() ( It begin, It end ) const {
        return (std::find_if(begin, end, item_predicate(key_, value_));
    } 
};

Где item_predicate() подходит для поиска пары (key_,value_) в [begin,end).

Если вы заинтересованы в поискеВ последовательности с двумя парами напишите предикат HasPairs, который дважды вызывает std::find_if, или более оптимизированную версию поиска двух элементов.