Ordenar vetor de objetos para pesquisa binária

Eu tenho a seguinte classe:

struct EdgeExtended {
    int neighborNodeId;
    int weight;
    int arrayPointer;
    bool isCrossEdge;

};

Eu quero ter um vetor de tais objetos, classificá-lo por neighborNodeId. Então eu quero procurar por um vizinho particularNodeId e retornar uma referência ao objeto encontrado dentro do vetor por busca binária. Anteriormente eu usava um mapa para isso, então era algo assim:

map<int, EdgeExtended> neighbours;
.....

auto it = neighbours.find(dnodeId);
if (it != neighbours.end()) {
    edgeMap = it->second; 
}

Ao invés de

map<int, EdgeExtended> neighbours;

eu quero ter

vector<EdgeExtended> neighbours;

e reter tanto quanto o código antigo da mesma.

Eu quero fazer benchmark se o vetor for mais rápido que o mapa, já que estou construindo milhares de vetores (ou mapas) e cada vetor (mapa) é relativamente pequeno (~ 10 itens). Eu não sei como a) fazer objetos classificáveis ​​por neighborNodeId e b) como usar pesquisa binária que procura por um membro específico da classe (neighborNodeId). Desculpe pela pergunta noob. Eu estou contando com sua ajuda.