(Art. 13b ANAG), hat sich ergeben:
A.- Der ursprünglich nach eigenen Angaben aus Uganda stammende nigerianische Staatsangehörige O._ (geb.
1977) reiste am 14. September 2000 illegal in die Schweiz ein und ersuchte hier um Asyl. Am 22. August 2001 verurteilte ihn das Strafeinzelgericht 13 des Gerichtskreises VIII Bern-Laupen wegen mehrfacher Widerhandlungen gegen das Betäubungsmittelgesetz zu 60 Tagen Gefängnis (unbedingt); gleichzeitig verwies es ihn für fünf Jahre des Landes (ebenfalls unbedingt).
B.- Am 15. Oktober 2001 verfügte der Regierungsstatthalter I von Bern, dass die gegen O._ angeordnete Landesverweisung auf dessen Entlassung aus dem Strafvollzug hin vollstreckt werde. Für den Fall, dass dies nicht fristgerecht geschehen könne, nahm er O._ in Ausschaffungshaft.
Das Haftgericht III Bern-Mittelland (Haftrichter 4) prüfte und bestätigte diese an seiner Sitzung vom 22. Oktober 2001 (mit schriftlicher Begründung vom 26. Oktober 2001).
C.- O._ hat hiergegen am 17. November 2001 beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht mit dem Antrag, ihn freizulassen. Die Haft sei unverhältnismässig und entbehre eines Haftgrunds; im Übrigen entsprächen die Haftbedingungen nicht den gesetzlichen Anforderungen.
Das Haftgericht III Bern-Mittelland (Haftrichter 4) und der Regierungsstatthalter I von Bern beantragen, die Beschwerde abzuweisen. Das Bundesamt für Ausländerfragen hat sich nicht vernehmen lassen.
O._ hat von der Möglichkeit, ergänzend Stellung zu nehmen, keinen Gebrauch gemacht.

Das Bundesgericht zieht in Erwägung:
1.- Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen bzw. in dieser belassen, soweit die Voraussetzungen von Art. 13b des Bundesgesetzes über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid bzw. eine strafrechtliche Landesverweisung vorliegt (Urteil des Bundesgerichts vom 28. Januar 1999 i.S. Sara, E. 2), deren Vollzug noch nicht möglich, jedoch absehbar ist. Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 3a S. 374, 377 E. 3a S. 381; <ref-ruling> E. 1 S. 3). Die Ausschaffung hat rechtlich und tatsächlich möglich zu sein (Art. 13c Abs. 5 lit. a ANAG; vgl. dazu <ref-ruling> E. 2 S. 220, 377 E. 5 S. 384; <ref-ruling> E. 3 S. 152 ff.). Ihr Vollzug muss mit dem nötigen Nachdruck verfolgt werden (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.) und die Haft als Ganzes verhältnismässig erscheinen (vgl. <ref-ruling> E. 4; <ref-ruling> E. 4 S. 383; <ref-ruling> E. 2c S. 198 f.).
2.- a) Der Beschwerdeführer ist am 22. August 2001 in Anwendung von <ref-law> des Landes verwiesen worden.
Der Regierungsstatthalter I von Bern hat diese Entfernungs- und Fernhaltemassnahme am 15. Oktober 2001 für vollstreckbar erklärt (vgl. hierzu <ref-ruling> ff.; <ref-ruling> E. 4 S. 112 ff. insb. S. 115). Deren Durchsetzung konnte trotz des hängigen Asylverfahrens mit Ausschaffungshaft sichergestellt werden, da sie absehbar war (unveröffentlichte Urteile vom 23. Januar 1998 i.S. Simic, E. 2, und vom 30. Januar 1997 i.S. Sy, E. 2b; Philip Grant, Les mesures de contrainte en droit des étrangers, Bern 2001, S. 13).
Das Bundesamt für Flüchtlinge hatte dem Beschwerdeführer bereits am 9. Oktober 2001 mitgeteilt, dass es sich bei ihm nicht um einen ugandischen, sondern einen nigerianischen Staatsangehörigen handeln dürfte und er somit falsche Angaben gemacht habe. Am 19. Oktober 2001 trat es dementsprechend auf das Asylgesuch nicht ein, womit bei der Haftprüfung auch insofern ein erstinstanzlicher Wegweisungsentscheid vorlag und eine Vorbereitungshaft nicht mehr in Frage kam (vgl. BGE <ref-ruling> E. 2b S. 380). Hieran ändert nichts, dass der Asylentscheid dem Haftrichter erst unmittelbar nach der Verhandlung zuging bzw. dass er am 15. Oktober 2001 bei Anordnung der Ausschaffungshaft durch den zuständigen Regierungsstatthalter (vgl. das unveröffentlichte Urteil vom 19. September 2001 i.S. Bouderbala, E. 2) noch nicht ergangen war. Der Beschwerdeführer befand sich - trotz der missverständlichen Formulierung in der Vollstreckungsverfügung, wonach der "Verwiesene in Ausschaffungshaft versetzt" werde, wenn die "Landesverweisung am 17. Oktober 2001" nicht vollzogen werden könne - bis zum 21. Oktober 2001 im Strafvollzug (vgl. die entsprechenden Mitteilungen der Abteilung Straf- und Massnahmenvollzug vom 29. August und 7. September 2001). Die am 15. Oktober 2001 angeordnete Ausschaffungshaft entfaltete ihre Wirkung erst ab diesem Zeitpunkt (vgl. Art. 13c Abs. 5 lit. c ANAG; unveröffentlichtes Urteil vom 29. Mai 1997 i.S. Alatrash, E. 3; Grant, a.a.O., S. 48), womit auch die haftrichterliche Prüfung innerhalb der vom Gesetz vorgeschriebenen 96 Stunden erfolgte (Art. 13c Abs. 2 ANAG).
b) Nach Art. 13b Abs. 1 lit. c ANAG kann Ausschaffungshaft verfügt werden, wenn konkrete Anzeichen befürchten lassen, dass sich der Ausländer der Ausschaffung entziehen will (Untertauchensgefahr). Dies ist hier der Fall:
Der Beschwerdeführer hat falsche Angaben zu seiner Herkunft gemacht, indem er sowohl vor dem Bundesamt für Flüchtlinge als auch noch vor dem Haftrichter behauptete, aus Uganda zu stammen. Er ist zudem hier straffällig geworden. Am 17. Februar 2001 wurde er von der Kantonspolizei Aargau wegen Widerhandlung gegen das Betäubungsmittelgesetz verzeigt und mit Strafbefehl des Bezirksamts Lenzburg vom 23. April 2001 zu einer Gefängnisstrafe von 30 Tagen (bedingt) verurteilt. Am 17. April 2001 grenzte ihn das Amt für öffentliche Sicherheit des Kantons Solothurn aus dem Kanton aus, nachdem er in der dortigen Drogenszene aufgegriffen worden war. Am 22. August 2001 wurde er vom Strafeinzelgericht 13 des Gerichtskreises VIII Bern-Laupen wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz (Handel mit Kokain, begangen am 21. August 2001) zu einer unbedingten Gefängnisstrafe von 60 Tagen sowie einer unbedingten Landesverweisung von fünf Jahren verurteilt. Am 10. Oktober 2001 grenzte ihn schliesslich der Migrationsdienst des Kantons Bern ebenfalls aus dem Kantonsgebiet aus. Mit Blick auf sein bisheriges Verhalten und die Tatsache, dass inzwischen auf sein Asylgesuch nicht eingetreten wurde, bietet der Beschwerdeführer damit keine Gewähr dafür, dass er sich ohne Haft zu gegebener Zeit den Behörden für den Vollzug der Ausschaffung zur Verfügung halten wird (<ref-ruling> E. 2a; <ref-ruling> E. 2b S. 198; Grant, a.a.O., S. 14 ff.). Hieran ändert seine Zusicherung nichts, bis zur Ausschaffung bei einer Freundin zu wohnen, macht er doch gleichzeitig geltend, sich allenfalls auch illegal in ein anderes Land absetzen zu wollen. Im Übrigen wäre der Haftgrund von Art. 13b Abs. 1 lit. b in Verbindung mit Art. 13a lit. e ANAG (Gefährdung von Leib und Leben durch Aktivitäten als Kleindealer) ebenfalls erfüllt (<ref-ruling> E. 3b/bb S. 375 f.).
c) Nach Art. 13b Abs. 3 ANAG sind die für den Vollzug der Weg- oder Ausweisung erforderlichen Vorkehrungen umgehend zu treffen. Befindet sich der Ausländer in Untersuchungshaft oder im Strafvollzug, müssen bei klarer fremdenpolizeilicher Ausgangslage bereits während dieser Zeit Abklärungen mit Blick auf die Ausschaffung erfolgen. Das Bundesgericht geht davon aus, dass das Beschleunigungsgebot verletzt ist, wenn während rund zwei Monaten keinerlei Vorkehren getroffen werden, ohne dass die Verzögerung in erster Linie auf das Verhalten ausländischer Behörden oder des Betroffenen selber zurückzuführen ist (<ref-ruling> E. 3a S. 51). Der Beschwerdeführer wurde zu einer Gefängnisstrafe von 60 Tagen und einer unbedingten Landesverweisung von fünf Jahren verurteilt. Die Papierbeschaffung ist erst nach Abschluss des Strafvollzugs eingeleitet worden. Hierin liegt dennoch keine Verletzung des Beschleunigungsgebots:
Einerseits stand der Papierbeschaffung während des Strafvollzugs das noch hängige Asylverfahren entgegen (<ref-law>; SR 142. 31; Mario Gattiker, Das Asyl- und Wegweisungsverfahren, Bern 1999, S. 29), anderseits behauptete der Beschwerdeführer, aus Uganda zu stammen, womit er die Abklärungen nach Vorliegen des Entscheids des Bundesamts für Flüchtlinge seinerseits erschwerte; im Übrigen erging der Entscheid über die Vollstreckung der Landesverweisung erst am 15. Oktober 2001. Die Abklärungen bei der nigerianischen Botschaft verzögerten sich, da diese ihre Zusammenarbeit mit den schweizerischen Behörden nach dem Tod eines Auszuschaffenden vorübergehend eingestellt hatte. Inzwischen ist dem Beschwerdeführer ein Laissez-passer erteilt worden. Sein Rückflug ist für den 2. Dezember 2001 geplant.
d) Der Beschwerdeführer wendet erstmals vor Bundesgericht ein, seine Haftbedingungen genügten in verschiedener Hinsicht nicht den gesetzlichen Anforderungen. Auf die entsprechenden Vorbringen kann nicht eingegangen werden: Das Bundesgericht prüft den Haftentscheid aufgrund der Sachlage, wie sie sich dem Haftrichter präsentiert hat. Was der Ausländer dort nicht ausdrücklich vortrug oder was sich nicht offensichtlich aus den dannzumal bekannten Akten ergab, kann es bei seinem Entscheid nicht berücksichtigen (<ref-ruling> E. 3a S. 221, mit Hinweisen). Soweit der Beschwerdeführer kritisiert, er sitze in einer zu kleinen Zelle, habe keinen Kontakt zur Aussenwelt und könne nicht telefonieren, hat er dies im Rahmen eines Haftentlassungsgesuchs zu rügen (<ref-ruling> E. 3a S. 221). Es wird auf ein entsprechendes Gesuch hin gegebenenfalls am Haftrichter sein, dafür zu sorgen, dass den bundesrechtlichen Minimalanforderungen an den Vollzug der Ausschaffungshaft (vgl. <ref-ruling> ff.; <ref-ruling> ff.) nachgelebt wird, andernfalls der Betroffene aus der Haft zu entlassen ist.
3.- a) Die Verwaltungsgerichtsbeschwerde erweist sich somit als unbegründet und ist deshalb abzuweisen, soweit darauf eingetreten wird. Der Regierungsstatthalter I von Bern wird ersucht, dafür besorgt zu sein, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und verständlich gemacht wird.
b) Dem Verfahrensausgang entsprechend würde der unterliegende Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 OG). Es rechtfertigt sich indessen, von der Erhebung einer Gerichtsgebühr abzusehen (Art. 154 Abs. 2 OG). Parteientschädigungen sind nicht geschuldet (vgl. Art. 159 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, dem Regierungsstatthalter I von Bern, dem Haftgericht III Bern-Mittelland (Haftrichter 4) sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 27. November 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: