Index: source/gui/CGUI.h
===================================================================
--- source/gui/CGUI.h
+++ source/gui/CGUI.h
@@ -24,6 +24,7 @@
 #define INCLUDED_CGUI
 
 #include "gui/GUITooltip.h"
+#include "gui/IGUIScrollBar.h"
 #include "gui/ObjectTypes/CGUIDummyObject.h"
 #include "gui/SettingTypes/CGUIColor.h"
 #include "gui/SGUIIcon.h"
@@ -35,6 +36,7 @@
 
 #include <map>
 #include <set>
+#include <unordered_map>
 #include <unordered_set>
 #include <vector>
 
@@ -44,7 +46,6 @@
 class CGUISprite;
 class IGUIObject;
 struct SGUIImageEffects;
-struct SGUIScrollBarStyle;
 
 /**
  * The main object that represents a whole GUI page.
@@ -596,21 +597,21 @@
 	 * IGUIObjects by name... For instance m_ObjectTypes["button"]
 	 * is filled with a function that will "return new CButton();"
 	 */
-	std::map<CStr, ConstructObjectFunction> m_ObjectTypes;
+	std::unordered_map<CStr, ConstructObjectFunction> m_ObjectTypes;
 
 	/**
 	 * Map from hotkey names to objects that listen to the hotkey.
 	 * (This is an optimisation to avoid recursing over the whole GUI
 	 * tree every time a hotkey is pressed).
 	 */
-	std::map<CStr, std::vector<IGUIObject*> > m_HotkeyObjects;
+	std::unordered_map<CStr, std::vector<IGUIObject*> > m_HotkeyObjects;
 
 	/**
 	 * Map from hotkey names to maps of eventNames to functions that are triggered
 	 * when the hotkey goes through the event. Contrary to object hotkeys, this
 	 * allows for only one global function per hotkey name per event type.
 	 */
-	std::map<CStr, std::map<CStr, JS::PersistentRootedValue>> m_GlobalHotkeys;
+	std::unordered_map<CStr, std::unordered_map<CStr, JS::PersistentRootedValue>> m_GlobalHotkeys;
 
 	/**
 	 * XML and JS can subscribe handlers to events identified by these names.
@@ -638,25 +639,25 @@
 	//--------------------------------------------------------
 
 	// Colors
-	std::map<CStr, const CGUIColor> m_PreDefinedColors;
+	std::unordered_map<CStr, const CGUIColor> m_PreDefinedColors;
 
 	// Sprites
 	std::map<CStr, const CGUISprite*> m_Sprites;
 
 	// Styles
-	std::map<CStr, const SGUIStyle> m_Styles;
+	std::unordered_map<CStr, const SGUIStyle> m_Styles;
 
 	// Scroll-bar styles
-	std::map<CStr, const SGUIScrollBarStyle> m_ScrollBarStyles;
+	std::unordered_map<CStr, const SGUIScrollBarStyle> m_ScrollBarStyles;
 
 	// Icons
-	std::map<CStr, const SGUIIcon> m_Icons;
+	std::unordered_map<CStr, const SGUIIcon> m_Icons;
 
 public:
 	/**
 	 * Stores all the IGUIObject which listen to a given event.
 	 */
-	std::map<CStr, std::set<IGUIObject*>> m_EventIGUIObjects;
+	std::unordered_map<CStr, std::set<IGUIObject*>> m_EventIGUIObjects;
 };
 
 #endif // INCLUDED_CGUI
Index: source/gui/CGUI.cpp
===================================================================
--- source/gui/CGUI.cpp
+++ source/gui/CGUI.cpp
@@ -41,7 +41,6 @@
 #include "scriptinterface/ScriptInterface.h"
 
 #include <string>
-#include <unordered_set>
 
 extern int g_yres;
 
@@ -105,7 +104,7 @@
 				ScriptException::CatchPending(rq);
 		}
 
-		std::map<CStr, std::vector<IGUIObject*> >::iterator it = m_HotkeyObjects.find(hotkey);
+		std::unordered_map<CStr, std::vector<IGUIObject*> >::iterator it = m_HotkeyObjects.find(hotkey);
 		if (it != m_HotkeyObjects.end())
 			for (IGUIObject* const& obj : it->second)
 			{
@@ -320,7 +319,7 @@
 
 IGUIObject* CGUI::ConstructObject(const CStr& str)
 {
-	std::map<CStr, ConstructObjectFunction>::iterator it = m_ObjectTypes.find(str);
+	std::unordered_map<CStr, ConstructObjectFunction>::iterator it = m_ObjectTypes.find(str);
 
 	if (it == m_ObjectTypes.end())
 		return nullptr;
@@ -440,7 +439,7 @@
 
 void CGUI::UnsetGlobalHotkey(const CStr& hotkeyTag, const CStr& eventName)
 {
-	std::map<CStr, std::map<CStr, JS::PersistentRootedValue>>::iterator it = m_GlobalHotkeys.find(hotkeyTag);
+	std::unordered_map<CStr, std::unordered_map<CStr, JS::PersistentRootedValue>>::iterator it = m_GlobalHotkeys.find(hotkeyTag);
 	if (it == m_GlobalHotkeys.end())
 		return;
 
@@ -452,7 +451,7 @@
 
 const SGUIScrollBarStyle* CGUI::GetScrollBarStyle(const CStr& style) const
 {
-	std::map<CStr, const SGUIScrollBarStyle>::const_iterator it = m_ScrollBarStyles.find(style);
+	std::unordered_map<CStr, const SGUIScrollBarStyle>::const_iterator it = m_ScrollBarStyles.find(style);
 	if (it == m_ScrollBarStyles.end())
 		return nullptr;
 
Index: source/ps/CStr.h
===================================================================
--- source/ps/CStr.h
+++ source/ps/CStr.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2019 Wildfire Games.
+/* Copyright (C) 2020 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -339,4 +339,16 @@
 	const u8* Deserialize(const u8* buffer, const u8* bufferend);
 };
 
+namespace std
+{
+template <>
+struct hash<CStr>
+{
+	std::size_t operator()(const CStr& str) const
+	{
+		return str.GetHashCode();
+	}
+};
+}
+
 #endif