The wonderfully named SitOrSquat.com is a website and mobile application that has mapped over 25,000 public restrooms. In their own words SitOrSquat "is dedicated to telling you where the closest public restroom is and whether or not that restroom is worthy of your bare bottom."
The over 25,000 mapped bathrooms include gas stations/rest stops, restaurants, bars, cafés and health clubs. As well as finding nearby restrooms users can rate them, view photos and read other users' reviews. SitorSquat.com also say that members can create a list of their favourite toilets and share them with friends, co-workers and acquaintances.
SitorSquat.com's iPhone application can be downloaded from the iTunes App Store for free.
NYRestroom.com - A map of New York restrooms