binary-search-tree: left() and right() return modifiable subtree
Dieses Issue hat noch niemand übernommen.
Bewertung
- Schwierigkeit
- 5/5
- Geschätzter Aufwand
- Über eine Woche
- Anfängerfreundlichkeit
- 25/100
Rechercherichtung
Beginne mit der Übung zum binären Suchbaum und untersuche example.h, wobei du dich auf binary_tree::left(), binary_tree::right() und insert() konzentrierst. Vergleiche deren Ownership und Constness mit den aktuellen Tests, die im Issue gezeigt werden. Erledigt ist die Aufgabe, wenn Beispiel und Tests mit einer const-sicheren Subtree-API übereinstimmen, die die Invariante des Baums nicht verletzen kann.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Beschreibung
In the exercise "binary-search-tree" the methods left() and right() are hard to implement correctly. The example implementation itself is IMHO incorrect.
The tests look like this:
template<typename T>
using tree_ptr = typename std::unique_ptr<binary_tree::binary_tree<T>>;
template<typename T>
static void test_leaf(const tree_ptr<T> &tree, const T& data, bool has_left, bool has_right)
//...
test_leaf<uint32_t>(tested->left(), 2, false, false);
That forces implementations of binary_tree::left() (and binary_tree::right()) to return a tree_ptr reference or rvaue which points to a non-const subtree.
Remember: const std::unique_ptr<some_type> means that the unique_ptr itself is const, not the object it points to.
Somebody could take the example implementation (example.h) and write
auto tree = binary_tree::binary_tree<int>(100);
tree.insert(50);
tree.left()->insert(150);
and thus invalidate the invariant of tree.
I consider any implementation of a binary search tree that can be corrupted that way as faulty. I came up with three alternatives that avoid this issue and pass the current tests:
binary_treecould have a member variableallow_insertthat istruefor the root andfalsefor all subtreesbinary_treecould have a parent pointer andinsert()could check for each of its parents if the new value violates that parent's invariantleft()andright()could copy the subtree and return aunique_ptrto that copy.
But IMHO none of those alternatives feels right.
The easiest solution would be if left() and right() could return const raw pointers. But one could argue that raw pointers result in unclear ownership.
- Vorherrschende Sprache
- C++
- Sterne
- 291
- Forks
- 244
- Ø Merge
- 17 Min.
- Gemergte PRs (30 T.)
- 1
Beitragsleitfaden
Für dieses Repository ist kein Beitragsleitfaden indexiert
Erste Schritte
- Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
- Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
- Forken Sie das Repository und arbeiten Sie in einem Branch.
- Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.
Mehr aus exercism/cpp
-
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 35/100
-
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 48/100
-
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 45/100
-
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 35/100
-
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 35/100
Ähnliche Issues
-
[CI] Nightly Clang build broken: structured binding captured in a lambda in FileDataSource.cpp Offenbug build
Schwierigkeit 1/5 Unter einer Stunde Anfängerfreundlichkeit 91/100
facebookincubator/velox#19194 ·
-
JIT-compiled number -> Decimal conversion silently overflows instead of raising DECIMAL_OVERFLOW Offenfuzz
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 82/100
ClickHouse/ClickHouse#122114 ·
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 84/100
-
module/agent platform/macos type/bug/regression
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 88/100
-
enhancement PyCDE
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 78/100