Differenzzulage, hat sich ergeben: A.- Die Beamten der Stadtpolizei Zürich werden grundsätzlich nach der städtischen Besoldungsverordnung vom 15. Juli 1993 (mit seitherigen Änderungen) besoldet. Seit 1972 wurde ihnen zusätzlich zur Besoldung eine sogenannte Differenzzulage ausgerichtet, um die Besoldungsdifferenzen gegenüber den entsprechenden Funktionen der Kantonspolizei zu reduzieren. Diese Zulage beruhte auf besonderen Beschlüssen und wurde 1988 letztmals angepasst. Am 1. Oktober 1997 beschloss der Gemeinderat (Parlament) der Stadt Zürich, den Stadtrat zu ermächtigen, die Differenzzulage für das Jahr 1998 festzulegen; zugleich hob er seine Beschlüsse über die Differenzzulage für das Jahr 1998 auf den Zeitpunkt auf, an welchem die vom Stadtrat festgelegten neuen Ansätze in Kraft treten. Gestützt darauf legte der Stadtrat am 5. November 1997 die Differenzzulage für das Jahr 1998 fest. Dabei wurden für die meisten Angehörigen der Stadtpolizei die Zulagen im Umfang von maximal Fr. --.-- gekürzt. Der Polizei-Beamten-Verband der Stadt Zürich, der Verband der Detektive der Stadtpolizei Zürich sowie einzelne Beamtinnen und Beamte erhoben gegen den Beschluss des Gemeinderats vom 1. Oktober 1997 sowie gegen den Beschluss des Stadtrats vom 5. November 1997 Beschwerde bzw. Rekurs an den Bezirksrat Zürich, der die Rechtsmittel am 23. April 1998 abwies. Der Polizei-Beamten-Verband der Stadt Zürich, der Verband der Detektive der Stadtpolizei Zürich sowie einzelne Beamtinnen und Beamte erhoben gegen den Entscheid betreffend den Gemeinderatsbeschluss Beschwerde an den Regierungsrat und zudem gegen beide Entscheide Beschwerde an das Verwaltungsgericht des Kantons Zürich. Am 7. September 1998 trat das Verwaltungsgericht auf die Beschwerde betreffend den Gemeinderatsbeschluss nicht ein und sistierte die Beschwerde betreffend den Stadtratsbeschluss bis zum Entscheid des Regierungrates im Rechtsmittelverfahren gegen den Gemeinderatsbeschluss. Der Regierungsrat wies die Beschwerde betreffend den Gemeinderatsbeschluss am 23. Dezember 1998 ab. Das Verwaltungsgericht nahm daraufhin das Verfahren betreffend den Stadtratsbeschluss wieder auf und wies die Beschwerde am 23. Juni 1999 ab. B.- Der Polizei-Beamten-Verband der Stadt Zürich, der Verband der Detektive der Stadtpolizei Zürich sowie sieben Beamtinnen und Beamte erheben staatsrechtliche Beschwerde mit dem Antrag, das Urteil des Verwaltungsgerichts vom 23. Juni 1999 sowie die Beschlüsse vom 1. Oktober 1997 und vom 5. November 1997 seien aufzuheben. Sie rügen eine Verletzung von Art. 4 aBV und von Art. 6 Ziff. 1 EMRK. C.- Der Stadtrat von Zürich beantragt im Auftrag des Gemeinderates Abweisung der staatsrechtlichen Beschwerde. Die Direktion der Justiz und des Innern des Kantons Zürich im Namen des Regierungsrats sowie das Verwaltungsgericht beantragen, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. D.- Mit Verfügung des Präsidenten der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 12. Oktober 1999 wurde der Beschwerde aufschiebende Wirkung beigelegt. 