AHO-CORASICK C ++ 17 Implementación -- ++ campo con algorithm campo con c++17 camp codereview Relacionados El problema

Aho-Corasick C++17 implementation


5
vote

problema

Español

Recientemente implementé el algoritmo, que puede encontrar todos los patrones que pueden contener "?" como "cualquier personaje". Por ejemplo, si el texto es "Abracadabra" y el patrón es "A? A", entonces mi algoritmo encuentra patrones como "ACA" y "ADA". Para ese propósito, estaba usando el algoritmo AHO-CORASICK para detectar "subtemplos", y funcionó. Sin embargo, quería usar algunas técnicas C ++ 17 para que mi código moderno. Pero me temo que pudiera usar mal algunos de ellos. ¿Podrías darme algunas sugerencias en mi código?

P.s. Intento apegarme a Google Codestyle

  #include <algorithm> #include <iostream> #include <iterator> #include <unordered_map> #include <vector> #include <memory>  class TemplateFinder { private:     /* Trie node */     struct Node {         bool terminal_ = false;         size_t word_size_ = 0;         char parent_char_ = 0;          std::shared_ptr<Node> parent_;         std::shared_ptr<Node> suffix_;         std::shared_ptr<Node> shrink_suffix_;          std::vector<size_t> word_bias_; //Subtemplate bias. Subtemplates can be repeated -> several biases         std::unordered_map<char, std::shared_ptr<Node>> transitions_;         std::unordered_map<char, std::shared_ptr<Node>> delta_function_;     };      size_t subpattern_count_ = 0;     size_t pattern_size_;      std::shared_ptr<Node> root_;     char splitter_;      void AddSubTemplate(const std::string& subtemplate, size_t word_bias);     void ProcessShrunk(const std::shared_ptr<Node>& current_p, size_t char_pos, std::vector<size_t>& pattern_entries);      std::shared_ptr<Node> GetSuffix(const std::shared_ptr<Node>& current_p);     std::shared_ptr<Node> GoDelta(const std::shared_ptr<Node>& current_p, char c);     std::shared_ptr<Node> GetShrunkSuffix(const std::shared_ptr<Node>& current_p);      static void UpdateEntries(const std::shared_ptr<Node>& current_p, size_t char_position,                               std::vector<size_t>& pattern_entries);      static auto Split(const std::string& text, char splitter)         -> std::pair<std::vector<std::string>, std::vector<size_t>>; public:     explicit TemplateFinder(const std::string& pattern, char splitter);      template<typename OutputIterator>     void FindEntries(const std::string& text, OutputIterator& out); };  /* Adding subtemplate to trie */ void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {     auto p_current = root_;     for (char c : subtemplate) {         if (p_current->transitions_.find(c) == p_current->transitions_.end()) {             p_current->transitions_[c] = std::make_shared<Node>();             p_current->transitions_[c]->parent_ = p_current;             p_current->transitions_[c]->parent_char_ = c;         }         p_current = p_current->transitions_[c];     }     p_current->terminal_ = true;     p_current->word_bias_.push_back(word_bias);     p_current->word_size_ = subtemplate.size();     ++subpattern_count_; }  TemplateFinder::TemplateFinder(const std::string& pattern, char splitter) : pattern_size_(pattern.size()),                                                                             splitter_(splitter) {     root_ = std::make_shared<Node>();     auto [split_text, bias] = Split(pattern, splitter_);     for (size_t i = 0; i < split_text.size(); ++i) {         AddSubTemplate(split_text[i], bias[i]);     } }  /* Splitting the template to subtemplates */ auto TemplateFinder::Split(const std::string &text, char splitter)     -> std::pair<std::vector<std::string>, std::vector<size_t>> {     std::vector<std::string> split_text;     std::vector<size_t> bias; //Position of subtemplates in the template     std::string buffer;      size_t counter = 0;     for (char c : text) {         if (c == splitter && !buffer.empty()) {             bias.push_back(counter - buffer.size());             split_text.push_back(buffer);             buffer = "";         } else if (c != splitter) {             buffer += c;         }         ++counter;     }     if (!buffer.empty()) {         bias.push_back(counter - buffer.size());         split_text.push_back(buffer);     }     return std::make_pair(split_text, bias); }  /* Getting suffix link of the node */ auto TemplateFinder::GetSuffix(const std::shared_ptr<Node>& current_p)     -> std::shared_ptr<Node> {     if (!current_p->suffix_) {         if (current_p == root_ || current_p->parent_ == root_) {             current_p->suffix_ = root_;         } else {             current_p->suffix_ = GoDelta(GetSuffix(current_p->parent_), current_p->parent_char_);         }     }     return current_p->suffix_; }  /* Delta function of automata */ auto TemplateFinder::GoDelta(const std::shared_ptr<Node>& current_p, char c)     -> std::shared_ptr<Node> {     if (current_p->delta_function_.find(c) == current_p->delta_function_.end()) {         if (current_p->transitions_.find(c) != current_p->transitions_.end()) {             current_p->delta_function_[c] = current_p->transitions_[c];         } else if (current_p == root_) {             current_p->delta_function_[c] = root_;         } else {             current_p->delta_function_[c] = GoDelta(GetSuffix(current_p), c);         }     }     return current_p->delta_function_[c]; }  /* Getting shrunk suffix link of the node */ auto TemplateFinder::GetShrunkSuffix(const std::shared_ptr<Node>& current_p)     -> std::shared_ptr<Node> {     if (!current_p->shrink_suffix_) {         std::shared_ptr<Node> suffix_link = GetSuffix(current_p);         if (suffix_link->terminal_) {             current_p->shrink_suffix_ = suffix_link;         } else if (suffix_link == root_) {             current_p->shrink_suffix_ = root_;         } else {             current_p->shrink_suffix_ = GetShrunkSuffix(suffix_link);         }     }     return current_p->shrink_suffix_; }  /* Main algorithm function - finding pattern in the text  */ template<typename OutputIterator> void TemplateFinder::FindEntries(const std::string &text, OutputIterator& out) {     std::shared_ptr<Node> current_p = root_;     std::vector<size_t> pattern_entries(text.size());          for (size_t char_pos = 0; char_pos < text.size(); ++char_pos) {         current_p = GoDelta(current_p, text[char_pos]);         ProcessShrunk(current_p, char_pos, pattern_entries);          if (current_p->terminal_) {             UpdateEntries(current_p, char_pos, pattern_entries);         }     }      for (size_t char_pos = 0; char_pos < pattern_entries.size(); ++char_pos) {         if (pattern_entries[char_pos] == subpattern_count_ && char_pos + pattern_size_ < text.size() + 1) {             *out = char_pos;             ++out;         }     } }  /* Shrunk suffix traversal */ auto TemplateFinder::ProcessShrunk(const std::shared_ptr<Node>& current_p, size_t char_pos,                                    std::vector<size_t> &pattern_entries) -> void {     for (auto shrunk_p = GetShrunkSuffix(current_p); shrunk_p != root_; shrunk_p = GetShrunkSuffix(shrunk_p)) {         UpdateEntries(shrunk_p, char_pos, pattern_entries);     } }  auto TemplateFinder::UpdateEntries(const std::shared_ptr<Node> &current_p, size_t char_pos,                                    std::vector<size_t> &pattern_entries) -> void {     auto update_entries = [current_p, char_pos, &pattern_entries](size_t bias) {         auto pattern_pos = static_cast<int64_t>(char_pos - bias - current_p->word_size_ + 1);         if (pattern_pos >= 0 && pattern_pos < static_cast<int64_t>(pattern_entries.size())) {             ++pattern_entries[static_cast<size_t>(pattern_pos)];         }     };     std::for_each(current_p->word_bias_.begin(), current_p->word_bias_.end(), update_entries); }  int main() {     std::string text_template;     std::string text;     std::cin >> text_template >> text;      TemplateFinder finder(text_template, '?');      auto out_iter = std::ostream_iterator<size_t>(std::cout, " ");     finder.FindEntries(text, out_iter);      std::cout << std::endl;     return 0; } ```   
Original en ingles

Recently I implemented the algorithm, that can find all the patterns which may contain "?" as "any character". For example, if the text is "abracadabra" and the pattern is "a?a", then my algorithm finds patterns like "aca" and "ada". For that purpose, I was using the Aho-Corasick algorithm for "subtemplates" detection, and it worked out. Nevertheless, I wanted to use some c++17 techniques to make my code modern. But I am afraid that I could kind of misuse some of them. Could you give me some suggestions on my code?

P.S. I try to stick to Google codestyle

#include <algorithm> #include <iostream> #include <iterator> #include <unordered_map> #include <vector> #include <memory>  class TemplateFinder { private:     /* Trie node */     struct Node {         bool terminal_ = false;         size_t word_size_ = 0;         char parent_char_ = 0;          std::shared_ptr<Node> parent_;         std::shared_ptr<Node> suffix_;         std::shared_ptr<Node> shrink_suffix_;          std::vector<size_t> word_bias_; //Subtemplate bias. Subtemplates can be repeated -> several biases         std::unordered_map<char, std::shared_ptr<Node>> transitions_;         std::unordered_map<char, std::shared_ptr<Node>> delta_function_;     };      size_t subpattern_count_ = 0;     size_t pattern_size_;      std::shared_ptr<Node> root_;     char splitter_;      void AddSubTemplate(const std::string& subtemplate, size_t word_bias);     void ProcessShrunk(const std::shared_ptr<Node>& current_p, size_t char_pos, std::vector<size_t>& pattern_entries);      std::shared_ptr<Node> GetSuffix(const std::shared_ptr<Node>& current_p);     std::shared_ptr<Node> GoDelta(const std::shared_ptr<Node>& current_p, char c);     std::shared_ptr<Node> GetShrunkSuffix(const std::shared_ptr<Node>& current_p);      static void UpdateEntries(const std::shared_ptr<Node>& current_p, size_t char_position,                               std::vector<size_t>& pattern_entries);      static auto Split(const std::string& text, char splitter)         -> std::pair<std::vector<std::string>, std::vector<size_t>>; public:     explicit TemplateFinder(const std::string& pattern, char splitter);      template<typename OutputIterator>     void FindEntries(const std::string& text, OutputIterator& out); };  /* Adding subtemplate to trie */ void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {     auto p_current = root_;     for (char c : subtemplate) {         if (p_current->transitions_.find(c) == p_current->transitions_.end()) {             p_current->transitions_[c] = std::make_shared<Node>();             p_current->transitions_[c]->parent_ = p_current;             p_current->transitions_[c]->parent_char_ = c;         }         p_current = p_current->transitions_[c];     }     p_current->terminal_ = true;     p_current->word_bias_.push_back(word_bias);     p_current->word_size_ = subtemplate.size();     ++subpattern_count_; }  TemplateFinder::TemplateFinder(const std::string& pattern, char splitter) : pattern_size_(pattern.size()),                                                                             splitter_(splitter) {     root_ = std::make_shared<Node>();     auto [split_text, bias] = Split(pattern, splitter_);     for (size_t i = 0; i < split_text.size(); ++i) {         AddSubTemplate(split_text[i], bias[i]);     } }  /* Splitting the template to subtemplates */ auto TemplateFinder::Split(const std::string &text, char splitter)     -> std::pair<std::vector<std::string>, std::vector<size_t>> {     std::vector<std::string> split_text;     std::vector<size_t> bias; //Position of subtemplates in the template     std::string buffer;      size_t counter = 0;     for (char c : text) {         if (c == splitter && !buffer.empty()) {             bias.push_back(counter - buffer.size());             split_text.push_back(buffer);             buffer = "";         } else if (c != splitter) {             buffer += c;         }         ++counter;     }     if (!buffer.empty()) {         bias.push_back(counter - buffer.size());         split_text.push_back(buffer);     }     return std::make_pair(split_text, bias); }  /* Getting suffix link of the node */ auto TemplateFinder::GetSuffix(const std::shared_ptr<Node>& current_p)     -> std::shared_ptr<Node> {     if (!current_p->suffix_) {         if (current_p == root_ || current_p->parent_ == root_) {             current_p->suffix_ = root_;         } else {             current_p->suffix_ = GoDelta(GetSuffix(current_p->parent_), current_p->parent_char_);         }     }     return current_p->suffix_; }  /* Delta function of automata */ auto TemplateFinder::GoDelta(const std::shared_ptr<Node>& current_p, char c)     -> std::shared_ptr<Node> {     if (current_p->delta_function_.find(c) == current_p->delta_function_.end()) {         if (current_p->transitions_.find(c) != current_p->transitions_.end()) {             current_p->delta_function_[c] = current_p->transitions_[c];         } else if (current_p == root_) {             current_p->delta_function_[c] = root_;         } else {             current_p->delta_function_[c] = GoDelta(GetSuffix(current_p), c);         }     }     return current_p->delta_function_[c]; }  /* Getting shrunk suffix link of the node */ auto TemplateFinder::GetShrunkSuffix(const std::shared_ptr<Node>& current_p)     -> std::shared_ptr<Node> {     if (!current_p->shrink_suffix_) {         std::shared_ptr<Node> suffix_link = GetSuffix(current_p);         if (suffix_link->terminal_) {             current_p->shrink_suffix_ = suffix_link;         } else if (suffix_link == root_) {             current_p->shrink_suffix_ = root_;         } else {             current_p->shrink_suffix_ = GetShrunkSuffix(suffix_link);         }     }     return current_p->shrink_suffix_; }  /* Main algorithm function - finding pattern in the text  */ template<typename OutputIterator> void TemplateFinder::FindEntries(const std::string &text, OutputIterator& out) {     std::shared_ptr<Node> current_p = root_;     std::vector<size_t> pattern_entries(text.size());          for (size_t char_pos = 0; char_pos < text.size(); ++char_pos) {         current_p = GoDelta(current_p, text[char_pos]);         ProcessShrunk(current_p, char_pos, pattern_entries);          if (current_p->terminal_) {             UpdateEntries(current_p, char_pos, pattern_entries);         }     }      for (size_t char_pos = 0; char_pos < pattern_entries.size(); ++char_pos) {         if (pattern_entries[char_pos] == subpattern_count_ && char_pos + pattern_size_ < text.size() + 1) {             *out = char_pos;             ++out;         }     } }  /* Shrunk suffix traversal */ auto TemplateFinder::ProcessShrunk(const std::shared_ptr<Node>& current_p, size_t char_pos,                                    std::vector<size_t> &pattern_entries) -> void {     for (auto shrunk_p = GetShrunkSuffix(current_p); shrunk_p != root_; shrunk_p = GetShrunkSuffix(shrunk_p)) {         UpdateEntries(shrunk_p, char_pos, pattern_entries);     } }  auto TemplateFinder::UpdateEntries(const std::shared_ptr<Node> &current_p, size_t char_pos,                                    std::vector<size_t> &pattern_entries) -> void {     auto update_entries = [current_p, char_pos, &pattern_entries](size_t bias) {         auto pattern_pos = static_cast<int64_t>(char_pos - bias - current_p->word_size_ + 1);         if (pattern_pos >= 0 && pattern_pos < static_cast<int64_t>(pattern_entries.size())) {             ++pattern_entries[static_cast<size_t>(pattern_pos)];         }     };     std::for_each(current_p->word_bias_.begin(), current_p->word_bias_.end(), update_entries); }  int main() {     std::string text_template;     std::string text;     std::cin >> text_template >> text;      TemplateFinder finder(text_template, '?');      auto out_iter = std::ostream_iterator<size_t>(std::cout, " ");     finder.FindEntries(text, out_iter);      std::cout << std::endl;     return 0; } ``` 
        
 
 

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

Tipos de retorno de arrastre

Su uso de tipos de retorno de arrastre se ve muy inconsistente. Mirando la Guía de estilo de Google C ++, parece que lo recomiendan usarlos si los tipos de devolución líderes son "poco prácticos o mucho menos legibles". Por supuesto, eso es, por supuesto, una cuestión de gusto, pero recomendaría ser lo más consistente posible: primero, use el mismo tipo de tipo de retorno directo / finalizado en la Declaración de una función que en la definición de la función. En segundo lugar, si el tipo de retorno es tan bien agradable, tiene que usar el estilo de arrastre, quizás sea mejor crear un alias de tipo para él. Por ejemplo:

  using SubTemplateList = std::pair<std::vector<std::string>, std::vector<size_t>>;  static SubTemplateList Split(const std::string& text, char splitter);   

Par de vectores vs. Vector de pares

TemplateFinder::Split()1 devuelve un par de vectores, pero las entradas en cada vector siempre coinciden. Así que tiene más sentido devolver un vector de pares:

  using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) {     SubTemplateList result;     ...         result.push_back({buffer, counter - buffer.size()});     ...     return result; }   

Esto también simplificará a algunos usuarios de este vector.

Evite el almacenamiento temporal innecesario

Split()3 solo se llama una vez en el constructor, y los resultados se utilizan para llamar AddSubtemplate() . Esto desperdiciará la memoria creando primero el vector temporal. Podrías resolver esto de varias maneras. Primero, puede fusionar Split() en el constructor, ya que aparte de asignar el nodo raíz, es básicamente lo único que hace el constructor. Si desea mantener Split() una función separada, luego haga que se realice un parámetro de devolución de llamada que se le llama para cada subtemplate que se encuentra, como un tipo de FindEntries() toma un iterador de salida como un argumento.

Puntos inteligentes

Veo que solo usa std::shared_ptr en su código. Sin embargo, esto está haciendo conteo de referencia, que tiene un impacto en el rendimiento. Solo debe usarlo si realmente lo necesita. Debe usar std::unique_ptr En lugar de que solo necesite Un puntero de propiedad, y puede usar los punteros descalzos para los punteros que no son propietarios de objetos que sabe, no se eliminará antes del último uso de ese puntero que no sea propietario.

Por ejemplo, un 99887766555443310 tiene los punteros infantiles que posee, por lo que debe usar TemplateFinder::Split()1 para aquellos, pero el padre de un TemplateFinder::Split()2 siempre sobrevivirá a sus hijos, por lo que puede usar un puntero desnudo para TemplateFinder::Split()3 :

  TemplateFinder::Split()4  

La variable de miembro TemplateFinder::Split()5 ni siquiera tiene que ser un puntero en absoluto, podría ser un valor 9988777665555443316 . Pero para consistencia con los otros nodos asignados, puede usar un 99887776655443317 aquí. Tenga en cuenta que puede usar la inicialización del valor de Miembros:

  TemplateFinder::Split()8  

Tenga en cuenta que una vez que use TemplateFinder::Split()9 , no debe escribir código como este:

  using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) {     SubTemplateList result;     ...         result.push_back({buffer, counter - buffer.size()});     ...     return result; } 0  

Esto realmente robará la memoria de using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) { SubTemplateList result; ... result.push_back({buffer, counter - buffer.size()}); ... return result; } 1 . Ya que solo quieres obtener el puntero, escribe:

  using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) {     SubTemplateList result;     ...         result.push_back({buffer, counter - buffer.size()});     ...     return result; } 2  

Prácticamente todos los usos de using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) { SubTemplateList result; ... result.push_back({buffer, counter - buffer.size()}); ... return result; } 3 en su código se puede reemplazar con los punteros descalzos, excepto los punteros de propiedad using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) { SubTemplateList result; ... result.push_back({buffer, counter - buffer.size()}); ... return result; } 4 y using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) { SubTemplateList result; ... result.push_back({buffer, counter - buffer.size()}); ... return result; } 5 .

Considere agregar funciones de Miembros a using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) { SubTemplateList result; ... result.push_back({buffer, counter - buffer.size()}); ... return result; } 6

Hay operaciones que realiza en using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) { SubTemplateList result; ... result.push_back({buffer, counter - buffer.size()}); ... return result; } 7 S que podrían realizarse funciones de Miembros de using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) { SubTemplateList result; ... result.push_back({buffer, counter - buffer.size()}); ... return result; } 8 . Por ejemplo:

  using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) {     SubTemplateList result;     ...         result.push_back({buffer, counter - buffer.size()});     ...     return result; } 9  

y luego usalo así:

  Split()0  

Tenga cuidado al colocar enteros entre firmados y sin firmar

Veo este código:

  Split()1  

Esto funcionará correctamente en arquitecturas de 64 bits, pero ¿qué pasa con los de 32 bits donde 99887766555443332 es en realidad un 998877766554433333 ? Puede usar Split()4 o Split()5 aquí, pero quizás sea mejor evitar la necesidad de lanzar en total:

  Split()6  
 

Trailing return types

Your use of trailing return types looks very inconsistent. Looking at the Google C++ Style Guide, it seems that they recommend using them if leading return types are "impractical or much less readable". That is of course a matter of taste then, but I would recommend being as consistent as possible: first, use the same type of leading/trailing return type in the declaration of a function as in the definition of the function. Second, if the return type is so unwieldly you have to use the trailing style, perhaps it is better to create a type alias for it. For example:

using SubTemplateList = std::pair<std::vector<std::string>, std::vector<size_t>>;  static SubTemplateList Split(const std::string& text, char splitter); 

Pair of vectors vs. vector of pairs

TemplateFinder::Split() returns a pair of vectors, but the entries in each vector always match up. So it makes more sense to return a vector of pairs:

using SubTemplateList = std::vector<std::pair<std::string, size_t>>; ... SubTemplateList TemplateFinder::Split(const std::string &text, char splitter) {     SubTemplateList result;     ...         result.push_back({buffer, counter - buffer.size()});     ...     return result; } 

This will simplify some users of this vector as well.

Avoid unnecessary temporary storage

Split() is only called once in the constructor, and the results are used to call AddSubtemplate(). This will waste memory by first creating the temporary vector. You could solve this in several ways. First, you could merge Split() into the constructor, since apart from allocating the root node, that's basically the only thing the constructor does. If you want to keep Split() a separate function, then have it take a callback parameter that is called for each subtemplate it finds, kind of like how FindEntries() takes an output iterator as an argument.

Smart pointers

I see you only use std::shared_ptr in your code. However, this is doing reference counting, which has an impact on performance. You should only use it if you are really need it. You should use std::unique_ptr instead of you only need an owning pointer, and you can use bare pointers for non-owning pointers to object you know will not be deleted before the last use of that non-owning pointer.

For example, a Node has child pointers that it owns, so it should use std::unique_ptr for those, but the parent of a Node will always outlive its children, so you can use a bare pointer for parent_:

struct Node {     ...     Node *parent_;     Node *suffix_;     Node *shrink_suffix_;      std::unordered_map<char, std::unique_ptr<Node>> transitions_;     std::unordered_map<char, Node *> delta_function_; }; 

The member variable root_ doesn't even have to be a pointer at all, it could just be a Node value. But for consistency with the other allocated nodes, you could use a std::unique_ptr here. Note that you can use member value initialization:

std::unique_ptr<Node> root_ = std::make_unique<Node>(); 

Note that once you use std::unique_ptr, you shouldn't write code like this anymore:

auto p_current = root_; 

This will actually steal the memory from root_. Since you just want to get the pointer, write:

auto p_current = root_.get(); 

Virtually all uses of std::shared_ptr in your code can be replaced with bare pointers, except for the owning pointers root_ and Node::transitions_.

Consider adding member functions to struct Node

There are operations you do on Nodes that could be made member functions of struct Node. For example:

struct Node {     ...     Node(Node *parent, char parent_char): parent_(parent), parent_char_(parent_char) {}      Node *GetTransition(char c) {         if (transitions_.find(c) == transitions_.end()) {             transitions_[c] = std::make_unique<Node>(this, c);         }          return transitions_[c].get();     } }; 

And then use it like this:

void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {     ...     for (char c : subtemplate) {         p_current = p_current->GetTransition(c);     }     ... } 

Be careful when casting integers between signed and unsigned

I see this code:

auto pattern_pos = static_cast<int64_t>(char_pos - bias - current_p->word_size_ + 1); if (pattern_pos >= 0 && pattern_pos < static_cast<int64_t>(pattern_entries.size())) {     ... } 

This will work correctly on 64-bit architectures, but what about 32-bit ones where size_t is actually a uint32_t? You could use ssize_t or ptrdiff_t here, but perhaps better is to just avoid the need to cast altogether:

if (char_pos > bias + current_p->word_size) {     size_t pattern_pos = char_pos - bias - current_p->word_size_ + 1;     if (pattern_pos < pattern_entries.size()) {         ...     } } 
 
 
 
 

Relacionados problema

3  Implementar el rango de Fibonacci  ( Implement fibonacci range ) 
Estoy implementando una gama FIBONACCI en C ++ 17 de tal manera que admite #include "fib.h" #include <iostream> int main() { for (int x : Fibonacci())...

5  C ++ Elija entre funciones de implementación de tiempo de ejecución y tiempo de compilación  ( C choose between runtime and compile time implementation functions ) 
Escribí una pequeña función de envoltura para elegir entre Tiempo de ejecución (STD) 99887766555443318 y una versión de ConsexPR, como continuación de la cl...

20  Cree una cadena C ++ usando el formato de estilo de impresión  ( Create a c string using printf style formatting ) 
A menudo es conveniente usar cadenas de formato C-Style 998877766554433665544336 A menudo encuentro los modificadores mucho más sencillos para usar que los...

5  Leetcode 928: Minimice Malware Spread II  ( Leetcode 928 minimize malware spread ii ) 
Estoy publicando mi código para un problema de código leetcode. Si desea revisar, por favor hágalo. ¡Gracias por su tiempo! Problema (este problema es el ...

4  Implementar el servidor HTTP utilizando libevent  ( Implement http server using libevent ) 
#include "fmt/format.h" #include <cstdint> #include <cstdio> #include <event2/event-config.h> #include <event2/util.h> #include <evhttp.h> #include <memory> ...

2  Fusionar ocurrencias adyacentes de elementos idénticos en la recopilación de datos  ( Merge adjacent occurrences of identical elements in data collection ) 
Hay una pequeña Ejercicio de programación para fusionar elementos idénticos adyacentes en una colección. Aquí hay dos soluciones (Pasando las pruebas de...

8  Conversión de STD :: Chrono :: Time_Point to / from std :: string  ( Converting stdchronotime point to from stdstring ) 
Considere estas funciones que permitan convertir checkOnline.sh4 a / FROM checkOnline.sh5 Con un formato Fecha de fecha ". checkOnline.sh6 con uso:...

3  Eliminación de variables genéricos con múltiples puntos de entrada  ( Generic variable elimination with multiple entry points ) 
Tengo este algoritmo, llamado eliminación variable , que se usa con bastante frecuencia en mi código -Base (biblioteca). Es un algoritmo para los gráficos de...

5  Clase de registro de C ++  ( C logging class ) 
He creado una clase simple de registro de C ++. Produce varios loglas, y ajusta el color de la salida en consecuencia. Estoy interesado en cualquier consejo p...

2  "Multi" Guardia de alcance que usa la característica de Deducación de la plantilla  ( Multi scope guard using template argument deducing feature ) 
Uso de la función C ++ moderna Deducción del argumento de la plantilla para las plantillas de clase y Expresiones plegables Es posible implementar la...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos