The specifics of this is very much dependent upon location, however the chances are good that your employer is in the wrong here.
UK:
The Workplace (Health, Safety and Welfare) Regulations 1992 cover this and the key take-aways are:
If you employ anyone (however short the period) you must ‘so far as is reasonably
practicable’, provide adequate and appropriate welfare facilities for them while they
are at work. This means you must provide such facilities unless it is clearly
unreasonable in terms of time, trouble, cost and physical difficulty
and:
where possible, separate facilities for men and women. Failing that, rooms with
lockable doors;
Which basically means that if they can't provide separate facilities for you they have to designate the one existing facility as mixed use and provide lockable door(s)
US:
OSHA mandates that:
Except as otherwise indicated in this paragraph (c)(1)(i), toilet facilities, in toilet rooms separate for each sex, shall be provided in all places of employment in accordance with table J-1 of this section. The number of facilities to be provided for each sex shall be based on the number of employees of that sex for whom the facilities are furnished. Where toilet rooms will be occupied by no more than one person at a time, can be locked from the inside, and contain at least one water closet, separate toilet rooms for each sex need not be provided. Where such single-occupancy rooms have more than one toilet facility, only one such facility in each toilet room shall be counted for the purpose of table J-1.
With additional info here
Australia:
Pretty much the same again:
In most cases, employers are expected to provide toilet facilities for employees, rather than relying on access to external public toilets.
and if they can't (or the workplace is temporary):
Sometimes, when workplaces are temporary, remote or mobile, employers are unable to provide toilets for employees. In these cases employers need to provide the amenity by ensuring employees have access to other toilets, such as public toilets or toilets at client premises. Clear directions on where the toilets are located also need to be provided.
If you aren't in one of the above locales then different rules may apply.