I cannot really express how much praise I have for Organic Maps. It has got me out of the mire a couple of times due to the complete offline capability and paper maps being completely wrong. The OSM base layer is better than a lot of native maps out there.
Not only that, you can search for a toilet almost anywhere, including in the middle of nowhere in central Asia, and it found one!
Not only that, you can search for a toilet almost anywhere, including in the middle of nowhere in central Asia, and it found one!