Check out the upcoming Dyson 360 Eye - http://www.dyson360eye.com/

Disclaimer: I worked on it.

Edit: To answer your question directly, you have 3 choices:

1. Don't map (or somewhat guess it) - Roomba.

2. Map first, then clean - Neato.

3. Map as you clean - Dyson 360 Eye.

This is obviously a crude explanation but they get harder going down the list. If you are interested to know more, read up on SLAM (Simultaneous Localisation and Mapping) algorithms.