What is the most convenient way to provide the public loo?

This article from the BBC on the provision of public toilets struck me as an interesting talking point for students of economics (okay, you may not agree!).

The research carried out by the BBC suggests that there has been a considerable fall in the number of loos provided by local councils. The reason, unsurprisingly, is that councils are looking to make cuts in their costs and there is no compulsion on them to provide public conveniences. The article explains that, in many cases, the toilets have been handed over to local communities or parish councils - they haven't necessarily been closed down.

The question for students of economics, therefore, is why do we bother with public toilets at all? As a frequent visitor of major cities including London, I've found that the use of toilets at train stations usually comes at a price (30p - not always a deal-breaker) and use of toilets in coffee shops is often restricted to customers only (using a pin-enabled lock on doors). Why not allow the provision to become completely free-market? Why not hand over the guardianship of the porcelain to profit-maximising firms? Why don't businesses who already have toilet facilities try and make a profit from those desperate to spend a penny?

An interesting way to start the debate about market failure, externalities and government intervention!