ищет конкретный шаблон проектирования в C ++, который решает эту проблему

Question

Я ищу определенный шаблон проектирования в C ++, который решает эту проблему.

Я хочу создать раскадровку. Наша версия раскадровки содержит произвольное количество заметок (представьте, что вы делаете заметки на доске) Каждая заметка имеет заголовок, текст и набор тегов. Например. - название: «Тестовый Traceplayer» - текст: «Реализовать юнит-тест для класса Traceplayer фреймворка Spark Core». - теги: {"юнит тест", "трассировщик", "тестирование", "искровое ядро"}

Наша раскадровка должна позволять нам искать заметки по заголовку, тексту и тегам. Например.: searchByTitle ("Test Traceplayer") searchByTag ({"testing", "unit test"}) searchByText («Внедрить модульный тест для класса Traceplayer платформы ядра ядра».) Для простоты мы не хотим делать какое-либо подобие или сопоставление префиксов, когда поиск заголовка, тега или текста. Только точное совпадение должно дать результаты.

У меня есть ряд решений, которые решают эту проблему O (1) сложность поиска, но может ли кто-нибудь предложить какой-либо «Шаблон проектирования», который решает эту проблему.

Решите эту проблему с тремя картами STL и получите сложность поиска в постоянном времени

Поиск конкретного шаблона проектирования, который решает эту проблему.

Я решил эту проблему, используя 3 STL Map, и решение получило O (1) сложность поиска

#include <iostream>
#include <vector>
#include <map>

#define INPUT 8 

class Note {
public:
    string Tital;
    string Text;
    vector<string> vec;
    Note(){
        Tital = "\0";
        Text = "\0";
    }
};

class storyBoard{
public:
    void AddNote(string Tital,string Text,vector<string> vec );
    void RemoveByTital(string &tital);
    void PrintStoredData();
    Note* searchByTitle(string titleSearch);

    Note* searchByText(string text_);
    vector<Note*> searchByTag(string titleSearch);

    void printSlip(Note *tm);
    storyBoard(){}
private:

    std::map<string,Note *> TitalMap;
    std::map<string,Note *> TextMap;
    std::map<string,std::vector<Note *> > TagsMap;
};


Note* storyBoard::searchByTitle(string titleSearch){
    auto it_v = TitalMap.find(titleSearch);
    if (it_v != TitalMap.end()){
        cout<< "Tital search result is below:-"<<endl;
        return it_v->second;
    } else {
        cout <<"data "<<titleSearch << "  Not found"<<endl;
        return NULL;
    }
}

Note* storyBoard::searchByText(string titleSearch){
    auto it_v = TextMap.find(titleSearch);
    if (it_v != TextMap.end()){
        cout<< "Text search result is below:-"<<endl;
        return it_v->second;
    } else {
        cout <<"data "<<titleSearch << "  Not found"<<endl;
        return NULL;
    }
}

vector<Note*> storyBoard::searchByTag(string tagSearch){
    auto it_v = TagsMap.find(tagSearch);
    if (it_v != TagsMap.end()){
        cout<< "Tag search result is below:-"<<endl;
        return it_v->second;
    } else {
        cout <<"data "<<tagSearch << "  Not found"<<endl;
        vector<Note*> del;
        return del;
    }
}


void storyBoard::AddNote(string Tital, string Text, vector<string> v){
   Note *note = new Note;
   note->Tital = Tital;
   note->Text = Text;
   note->vec = v;

   TitalMap[note->Tital] = note;
   TextMap[note->Text] = note;

   for (auto it = note->vec.begin(); it != note->vec.end(); ++it){
       //check that is tags already 
       auto it_v = TagsMap.find(*it);
       if (it_v != TagsMap.end()){
           it_v->second. push_back(note);
       } else {
           vector<Note *> &v = TagsMap[*it];
           v.push_back(note);
       }
    }   
}

void storyBoard::printSlip(Note *tm){
    cout << "Tital=" << tm->Tital <<endl 
        << "Text=" <<  tm->Text <<endl
        << "Tags = ";
    for (auto it = tm->vec.begin(); it != tm->vec.end(); ++it){
        cout<< *it<<"\t";
    }    
    cout<<endl<<endl;
}

void storyBoard::PrintStoredData(){
    for(auto tm : TitalMap){
        printSlip(tm.second);
    }
    cout<<endl; 
}

void feed_data_for_testing(storyBoard &Sb);
void TestCase(storyBoard &Sb);

int main() {
    storyBoard Sb;
    feed_data_for_testing(Sb);

    Sb.PrintStoredData(); /*Print all contain data */
    cout<<"************* From Here start searching ************"<<endl;
    TestCase(Sb);
    return 0;
}

void TestCase(storyBoard &Sb){    
    Note* obj = Sb.searchByTitle("Tital-3");
    if(obj != NULL){
        Sb.printSlip(obj);
    }

    obj = Sb.searchByText("Text-4");
    if(obj != NULL){
        Sb.printSlip(obj);
    }

    vector<Note *> vec = Sb.searchByTag("tag-3");
    if(vec.size() !=0){
        for (auto it = vec.begin(); it != vec.end(); ++it){
            //cout<<(*it)->Tital << "\t";
            Sb.printSlip(*it);
        } 
    }   
}

void feed_data_for_testing(storyBoard &Sb){
    vector<string> tags ;
    int count =INPUT;
    for(int i =1;i<=count;i++){
        string tital = "Tital-" + std::to_string(i);
        string text = "Text-" + std::to_string(i);
        tags.clear();
        for(int j =1;j<=i;j++){
            string tag_ = "tag-" +  std::to_string(j);
            tags.push_back(tag_);
        }
        Sb.AddNote(tital,text,tags);
    }
}

Я ищу шаблон проектирования, который решает эту проблему.

Answer 1

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

Основная проблема с вашим кодом (и может бытьпричина отклонения) обработка памяти с использованием классических идиом c ++:

• использование интеллектуальных указателей для управления временем жизни ваших заметок
• правило3 (или 5) для обработки копирования / назначения (/ перемещения) вашего StoryBoard объекта

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

• арена заметок и ссылки на заметки с арены внутри ваших хэш-карт
• ...

После этой проблемырешено, у вас есть незначительные проблемы:

• возвращая указатели вместо ссылок, StoryBoard является владельцем памяти, вы не должны возвращать указатель, который вызывающий мог непреднамеренно освободить.
• нет доступа к константам (возвращая ссылки на константы)
• повторяющийся код, который может быть учтен

Если я не ошибаюсь в интерпретации сказанного интервьюером, этот вопрос следует перенести в просмотр кода.stackexhange.com

Answer 2

Я обновляю ваш код в следующей точке: -

1. конвертирует класс в синглтон, чтобы данные поддерживали единую карту для каждого типа
2. изменить карту на unorder_map

#define INPUT 8 
using namespace std;

/*use class to store single slip data*/
class Note {
public:
    string Tital;
    string Text;
    vector<string> vec;
    Note(){ //constructor to initialize data zero
        Tital = "\0";
        Text = "\0";
    }
};
/*create a singalton pattern class so that create only one data storage*/
class storyBoard{
public:
    static storyBoard* getInstance(){
        storyBoard* Instance= instance.load();
        if ( !Instance ){
            std::lock_guard<std::mutex> myLock(lock);
            Instance= instance.load();
            if( !Instance ){
              Instance= new storyBoard();
              instance.store(Instance);
            }
        }   
        return Instance;
    }

    void AddNote(string Tital,string Text,vector<string> vec );
    void RemoveByTital(string &tital);
    void PrintStoredData();
    Note* searchByTitle(string titleSearch);

    Note* searchByText(string text_);
    vector<Note*> searchByTag(string titleSearch);

    void printSlip(Note *tm);
private:
    storyBoard()= default;
    ~storyBoard()= default;
    storyBoard(const storyBoard&)= delete;
    storyBoard& operator=(const storyBoard&)= delete;

    static std::atomic<storyBoard*> instance;
    static std::mutex lock;
    std::unordered_map<string,Note *> TitalMap;
    std::unordered_map<string,Note *> TextMap;
    std::unordered_map<string,std::vector<Note *> > TagsMap;
};


std::atomic<storyBoard*> storyBoard::instance;
std::mutex storyBoard::lock;

Note* storyBoard::searchByTitle(string titleSearch){
    auto it_v = TitalMap.find(titleSearch);
    if (it_v != TitalMap.end()){
        cout<< "Tital search result is below:-"<<endl;
        return it_v->second;
    } else {
        cout <<"data "<<titleSearch << "  Not found"<<endl;
        return NULL;
    }
}

Note* storyBoard::searchByText(string titleSearch){
    auto it_v = TextMap.find(titleSearch);
    if (it_v != TextMap.end()){
        cout<< "Text search result is below:-"<<endl;
        return it_v->second;
    } else {
        cout <<"data "<<titleSearch << "  Not found"<<endl;
        return NULL;
    }
}

vector<Note*> storyBoard::searchByTag(string tagSearch){
    auto it_v = TagsMap.find(tagSearch);
    if (it_v != TagsMap.end()){
        cout<< "Tag search result is below:-"<<endl;
        return it_v->second;
    } else {
        cout <<"data "<<tagSearch << "  Not found"<<endl;
        vector<Note*> del;
        return del;
    }
}


void storyBoard::AddNote(string Tital, string Text, vector<string> v){
   Note *note = new Note;
   note->Tital = Tital;
   note->Text = Text;
   note->vec = v;

   TitalMap[note->Tital] = note;
   TextMap[note->Text] = note;

   for (auto it = note->vec.begin(); it != note->vec.end(); ++it){
       //check that is tags already 
       auto it_v = TagsMap.find(*it);
       if (it_v != TagsMap.end()){
           it_v->second. push_back(note);
       } else {
           vector<Note *> &v = TagsMap[*it];
           v.push_back(note);
       }
    }   
}

void storyBoard::printSlip(Note *tm){
    cout << "Tital=" << tm->Tital <<endl 
        << "Text=" <<  tm->Text <<endl
        << "Tags = ";
    for (auto it = tm->vec.begin(); it != tm->vec.end(); ++it){
        cout<< *it<<"\t";
    }    
    cout<<endl<<endl;
}

void storyBoard::PrintStoredData(){
    for(auto tm : TitalMap){
        printSlip(tm.second);
    }
    cout<<endl; 
}
/**temporary function only use for testing*/
void TestCase(){    
    storyBoard *Sb = storyBoard::getInstance();
    Note* obj = Sb->searchByTitle("Tital-3");
    if(obj != NULL){
        Sb->printSlip(obj);
    }

    obj = Sb->searchByText("Text-4");
    if(obj != NULL){
        Sb->printSlip(obj);
    }

    vector<Note *> vec = Sb->searchByTag("tag-3");
    if(vec.size() !=0){
        for (auto it = vec.begin(); it != vec.end(); ++it){
            //cout<<(*it)->Tital << "\t";
            Sb->printSlip(*it);
        } 
    }   
}
/**temporary function only use for testing*/
void feed_data_for_testing(){
    storyBoard *Sb = storyBoard::getInstance();
    vector<string> tags ;
    int count =INPUT;
    for(int i =1;i<=count;i++){
        string tital = "Tital-" + std::to_string(i);
        string text = "Text-" + std::to_string(i);
        tags.clear();
        for(int j =1;j<=i;j++){
            string tag_ = "tag-" +  std::to_string(j);
            tags.push_back(tag_);
        }
        Sb->AddNote(tital,text,tags);
    }
}

int main() {
    storyBoard *Sb = storyBoard::getInstance();
    feed_data_for_testing();

    Sb->PrintStoredData(); /*Print all contain data */
    cout<<"************* From Here start searching ************"<<endl;
    TestCase();
    return 0;
}