Alternative of map, as checking in map takes time

BOOL A::AddCounter(CounterInfo* Info)
{
    if (Info!= NULL)
    {
        m_mapCounters[Info->Id] = Info->CounterName;
    }
    return TRUE;
}

void B::AddCounterList(char** CounterNames, int NumCounters)
{
    for(int i=0; i<NumCounters; i++)
    {
        long id = InterlockedIncrement(&x);
        m_Info[id].CounterName= CounterName[i];
        m_Info[id].Id = id;
        AObj->AddCounter(&m_Info[id]);
    }
}

Class B
{
    Info m_Info;
    volatile long x;
    void AddCounterList(char** CounterNames, int NumCounters);
    B()
    {
         x = 0;
    }
}

Class A
{
    map< int, char* > m_mapCounters;
    BOOL AddCounter(CounterInfo* Info);
}

typedef struct
{
    char* CounterName;
    int Id;
}CounterInfo;

typedef std::map<const int, CounterInfo> Info;

Here one instance of class A is created and multiple instances of class B are created each running in separate thread. Here challenge is if same counter from different Objects of class A is sent with different Id then there is mismatch. Even if I move Id creation to AddCounter function and return id to AddCounterList function to assign value in m_Info in Object B then mismatch can be removed if before adding counter map is checked if counter already exists but if thousands of counter are already existing in m_mapCounters then checking will take huge time.