Ordenar vector de objetos para búsqueda binaria

Tengo la siguiente clase:

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

};

Quiero tener un vector de tales objetos, ordenarlos por neighborNodeId. Luego quiero buscar un vecino en particular ID de nodo y devolver una referencia al objeto encontrado dentro del vector mediante la búsqueda binaria. Anteriormente usé un mapa para eso, así que fue algo así:

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

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

En lugar de

map<int, EdgeExtended> neighbours;

quiero tener

vector<EdgeExtended> neighbours;

Y retener tanto como el antiguo código lo mismo.

Quiero comparar si el vector es más rápido que el mapa, ya que estoy creando miles de vectores (o mapas) y cada vector (mapa) es relativamente pequeño (~ 10 elementos). No sé cómo a) hacer que los objetos se puedan ordenar por el vecinoNodeId yb) cómo utilizar la búsqueda binaria que busca un miembro particular de la clase (neighbourodeNd). Lo siento por la pregunta de noob. Cuento con tu ayuda.

Respuestas a la pregunta(2)

Su respuesta a la pregunta