Using templates with variable class instance storage

Summary: I want to pre-parse a data once, and specialize the parsing and retrieval based a compile time type in a system that is already heavily templated. I do not know what to look for to get the final bits to hook up, connecting the storage of void * or however I store the item.

I've already identified the continual parsing of data as a performance issue, I just want to learn how to do this correctly hopefully using as many compile time actions.

---

I have the basic following code that works to get access to a std::string using std=c++11

class DataHolder {

    int value;
    bool value2;
    std::string longDataUnformated;    

};

class SearchThing{

    enum {        
        ENUM_A = 0x0,
        ENUM_B = 0x1,
        ENUM_C = 0x2    
    }          

    template<int MODE>
    T Find(const linkedList* head, int nodeIndex) {       
    return Find(KeyTemplate<MODE>(head->value, nodeIndex));
    }

    template<int MODE>
    DataHolder Find(const KeyTemplate<MODE>& Key) {        

        return someIterator = FindMatches(Key).TraverseMatches();                
    }
    PrimaryStorage * storage;
}

I can do this by calling:

auto type1data = 
    SearchThingInstanceType1.Find<SearchThing::ENUM_A>(linkedListHead, index)->longDataUnformated;
auto type2data = 
    SearchThingInstanceType2.Find<SearchThing::ENUM_B>(linkedListHead, index)->longDataUnformated;

And take the returned data and process it using accessValue or accessValueOther

As the DataHolder is unique, I'd love to be able to prevent repeatedly parsing the data and store it inside as genericClass.

void * genericClass;  // can be Type1 or Type2

As primarily a C developer who is attempting to learn more cpp, I understand void * are heavily discouraged. I could also have both Type1 and Type2 be a derived class but I really need to avoid virtual functions and as this behavior is defined at compile time I should use templates.

I'd like to create k classes, but for this example I have two, both with different return types. Eventually to include user defined types.

class Type1 {    
    std::vector<bool> parsedValues;
    int defaultValue; /* 0 */

    bool accessWith(int value){         
        return parsedValues[value];        
    }    

    bool performParsing(std::string, int value) {
        // build the vector of bools from std::string                  
    } 

};

class Type2 {
    std::unordered_map<int, int> parsedValues;
    int defaultValue; /* 0 */

    int accessWith(int value){         
        auto it= parsedValues.find(value);
        if (it) {return it.second();}        
        return defaultValue; 
    }

    int performParsing(std::string, int value) {
        // build the map from std::string
        // return parsed value
    }    
};

And then add a new method and template interface to my SearchThing class to encapsulate the parsing and storage:

// want to return type T which can be user defined or primitive. 
template<int MODE, typename T>
T CacheFind(const linkedList* head, int nodeIndex, int otherSpecifier) { 
    return CacheFind(KeyTemplate<MODE>(head->value, nodeIndex), otherSpecifier);
}

template<int MODE, typename T>
T CacheFind(const KeyTemplate<MODE>& Key, int someValue) {        

    DataHolder someIterator = FindMatches(Key).TraverseMatches();        
    if (someIterator && someIterator->genericClass){

        return someIterator->genericClass->accessWith(someValue);
    }

    // construct the object of type "T"
    someIterator->genericClass = (void*) new T();  // shouldn't use void *
    return someIterator->genericClass->performParsing(someIterator->longDataUnformated, someValue);
}

This would then allow me to do without wasteful parsing.

auto type1parsedData = 
    SearchThingInstanceType1.CacheFind<SearchThing::ENUM_A>(linkedListHead, index, accessValue);    
auto type2parsedData = 
    SearchThingInstanceType2.CacheFind<SearchThing::ENUM_B>(linkedListOtherHead, indexOther, accessValueOther);