From 58a0d9119903d53470dce47142017d76aedb5e5e Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 19 Aug 2020 22:05:54 -0400
Subject: Store iterators to the positions in the list in a map

This saves me having to find() each element -- now I can jump right to
them. But I had to store the list in the opposite order since erase()
doesn't like reverse iterators.
---
 challenge-074/walt-mankowski/cpp/ch-2.cpp | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

(limited to 'challenge-074/walt-mankowski/cpp')

diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp
index efb1aa1225..01fb9a916b 100644
--- a/challenge-074/walt-mankowski/cpp/ch-2.cpp
+++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp
@@ -1,6 +1,6 @@
 #include <string.h>
 #include <iostream>
-#include <set>
+#include <map>
 #include <list>
 #include <algorithm>
 
@@ -8,7 +8,7 @@ using namespace std;
 
 int main(int argc, char *argv[]) {
     const char *s = argv[1];
-    set<char> seen;
+    map<char,list<char>::const_iterator> seen;
     list<char> nr;
     char *out = new char[strlen(s)+1];
     out[strlen(s)] = '\0';
@@ -18,17 +18,17 @@ int main(int argc, char *argv[]) {
         
         // have we seen c before?
         if (seen.find(c) == seen.end()) {
-            seen.insert(c);
-            nr.push_back(c);
+            nr.push_front(c);
+            seen[c] = nr.cbegin();
         } else
             // remove c from nr
-            nr.erase(find(nr.cbegin(), nr.cend(), c));
+            nr.erase(seen[c]);
 
         // now the FNR is either the last element of nr, or #
         if (nr.empty()) 
             out[i] = '#';
         else
-            out[i] = *(nr.crbegin());
+            out[i] = *(nr.cbegin());
     }
     cout << out << endl;                
 }
-- 
cgit