Assuming that you are working with cubic cells, you can create a vector called point2cell, such that point2cell[iPoint] gives you the indeces of the cells sharing the point iPoint. This can be done by looping over the cells vector. Take a look at the following pseudo-code:

for iCell = 1:nCell
  for iPointLoc = 1:8
     iPoint = cells[iCell][iPointLoc]
     point2cell[iPoint].insert( iCell )

Next, you can loop over the faces, take one point, take all the cells sharing that point, and looking at the matching between a face and a cell:

for iFace = 1:nFace
  for iPointLoc = 1:4
    iPoint = faces[iFace][iPointLoc]
    for iCellLoc = 1:8
       iCell = point2Cell[iPoint][iCellLoc]
       if( iCell matches faces[iFace])
         face2cell[iFace].insert( iCell ) 

The first loop is linear in the number of cells while the second is linear in the number of faces.

Assuming that you are working with cubic cells, you can create a vector called point2cell, such that point2cell[iPoint] gives you the indeces of the cells sharing the point iPoint. This can be done by looping over the cells vector. Take a look at the following pseudo-code:

for iCell = 1:nCell
  for iPointLoc = 1:8
     iPoint = cells[iCell][iPointLoc]
     point2cell[iPoint].insert( iCell )

Next, you can loop over the faces, take one point, take all the cells sharing that point, and looking at the matching between a face and a cell:

for iFace = 1:nFace
  for iPointLoc = 1:4
    iPoint = faces[iFace][iPointLoc]
    for iCellLoc = 1:8
       iCell = point2Cell[iPoint][iCellLoc]
       if( cells[iCell] matches faces[iFace])
         face2cell[iFace].insert( iCell ) 

The first loop is linear in the number of cells while the second is linear in the number of faces.