// # set
//
// Implemented with Red Black trees in GCC 6.4:
// https://stackoverflow.com/questions/2558153/what-is-the-underlying-data-structure-of-a-stl-set-in-c/51944661#51944661
//
// A hashtable would be unlikely because it is sorted and can be efficiently iterated.
//
// Unique elements: inserting twice does nothing.
//
// Immutable elements: it is not possible to modify an object, one must first remove it and resinsert.
// This is so because modification may mean reordering.
#include "common.hpp"
// Non key searches.
class MemberKey {
public:
// Note that there is _no_ conversion constructor,
// everything is done at the template level without
// intermediate object creation.
//MemberKey(int key) : key(key) {}
MemberKey(int key, int notkey) : key(key), notkey(notkey) {}
int key;
int notkey;
};
bool operator<(const MemberKey& c, const int key) { return c.key < key; }
bool operator<(const int key, const MemberKey& c) { return key < c.key; }
bool operator<(const MemberKey& c, const MemberKey& d) {
return c.key < d.key;
}
//bool operator<(const std::unique_ptr& c, int key) { return *c < key; }
//bool operator<(int key, const std::unique_ptr& c) { return key < *c; }
// Works but not very cool as it hides the default unique_ptr::operator<,
// which is meaningful for arrays like regular pointers are.
//bool operator<(const std::unique_ptr& c, const std::unique_ptr& d) {
//return c->key < d->key;
//}
struct PointerCmp {
// Required for the heterogeneous searches to be found by compiler.
// Value does not seem to matter, only presence, but std::true_type is a good choice semantically.
typedef std::true_type is_transparent;
typedef std::unique_ptr T;
bool operator()(const T& c, int key) const { return *c < key; }
bool operator()(int key, const T& c) const { return key < *c; }
bool operator()(const T& lhs, const T& rhs) const {
return lhs->key < rhs->key;
}
};
int main() {
// C++11 initializer list
{
{
std::set s{1, 2, 0, 1};
std::set s2{0, 1, 2};
assert(s == s2);
}
{
std::set s = {"a", "c", "b", "a"};
std::set s1 = {"a","b", "c"};
assert(s == s1);
}
}
// You can modify objects if you store pointers.
{
int i = 0;
std::set s;
s.insert(&i);
std::set::iterator it = s.find(&i);
*(*it) = 1;
assert(i == 1);
}
// # insert
//
// Return is a pair containing:
//
// - if the item was not present, an iterator to the item inserted and true
// - if the item was present, an iterator to the existing item inserted and false
{
std::set s;
auto ret = s.insert(1);
assert(ret.first == s.find(1));
assert(ret.second == true);
ret = s.insert(2);
assert(ret.first == s.find(2));
assert(ret.second == true);
ret = s.insert(0);
assert(ret.first == s.find(0));
assert(ret.second == true);
// Item already present:
// nothing is done and returns false on the pair.
ret = s.insert(1);
assert(ret.first == s.find(1));
assert(ret.second == false);
std::set s1 = {0, 1, 2};
assert(s == s1);
}
// # erase
//
// Remove element from set.
//
// Returns number of elements removed (either 0 or 1).
{
std::set s = {0, 1, 2};
assert(s.erase(1) == 1);
std::set s2 = {0, 2};
assert(s == s2);
assert(s.erase(1) == 0);
}
// ERROR no random access since it uses bidirection iterator.
{
//cout << s[0] << endl;
}
// size
{
std::set s;
assert(s.size() == 0);
s.insert(0);
assert(s.size() == 1);
}
// # iterate
//
// Biderectional iterator.
//
// Always sorted by key:
// http://stackoverflow.com/questions/8833938/is-the-stdset-iteration-order-always-ascending-according-to-the-c-specificat/41424755#41424755
//
// This basically forces a balanced tree implementation instead of hash set,
// and requires < > operators to be implemented on the value.
//
// Sorted by insertion order does not exist:
// http://stackoverflow.com/questions/7801109/does-the-c-standard-library-have-a-set-ordered-by-insertion-order
{
std::set s;
s.insert(2);
s.insert(1);
auto it = s.begin();
assert(*it == 1);
it++;
assert(*it == 2);
it++;
assert(it == s.end());
}
// # find
//
// If found, returns an iterator pointing to the element.
// Else, returns `map::end()`
//
// find is `log n` time since the container is ordered.
{
std::set s = {0, 1, 2};
std::set::iterator it;
it = s.find(1);
assert(*it == 1);
it = s.find(3);
assert(it == s.end());
}
// # count
//
// Count how many times an item is in the set.
//
// Can only return 1 or 0.
//
// Equivalent to doing a find.
{
std::set s = {1, 2, 0, 1};
assert(s.count(1) == 1);
assert(s.count(3) == 0);
}
// # Modify a key
//
// Impossible without either:
//
// - remove and re-insert (possibly with hint), which is the right way
// - hacks like `mutable`
//
// Because `std::set::iterator` is actually `const` by the standard:
//
// - http://stackoverflow.com/questions/908949/what-happens-when-you-modify-an-element-of-an-stdset
// - http://stackoverflow.com/questions/2217878/c-stl-set-update-is-tedious-i-cant-change-an-element-in-place
// - http://stackoverflow.com/questions/7340434/how-to-update-an-existing-element-of-stdset
// - http://stackoverflow.com/questions/6068167/is-this-safe-mutability-and-sets
//
// # Hint
//
// If an iterator is given, it serves as a hint to where the new value is likely to be inserted.
//
// This is speciall useful if you want to update a value,
// but expect the new result to be in the same position.
{
class C {
public:
C(int i) : i(i) {}
bool operator<(const C& other) const { return this->i < other.i; }
bool operator==(const C& other) const { return this->i == other.i; }
bool operator>(const C& other) const { return this->i > other.i; }
mutable int i;
};
std::set s;
s.insert(C(1));
s.insert(C(2));
auto it = s.find(C(1));
//*it = C(3);
// Almost certainly bad, but I can't find the C++ quote that says so.
it->i = 3;
}
// Search by non-key comparable
//
// - http://stackoverflow.com/questions/17375780/is-it-possible-to-use-elements-of-a-different-type-than-contained-in-a-stdset
// - http://stackoverflow.com/questions/20317413/what-are-transparent-comparators
{
// Member is key, operators injected as comparisions with memeber make sense.
// http://stackoverflow.com/questions/13827973/c-map-container-where-key-is-part-of-value/41624995#41624995
{
std::set> s;
s.insert(MemberKey(1, -1));
s.insert(MemberKey(2, -2));
s.insert(MemberKey(0, 0));
s.insert(MemberKey(3, -3));
assert(s.find(0)->notkey == 0);
assert(s.find(1)->notkey == -1);
assert(s.find(2)->notkey == -2);
assert(s.find(3)->notkey == -3);
assert(s.find(MemberKey(1, 1234))->notkey == -1);
}
// unique_ptr
//
// - http://stackoverflow.com/questions/18939882/raw-pointer-lookup-for-sets-of-unique-ptrs
// - http://stackoverflow.com/questions/17851088/using-a-stdunordered-set-of-stdunique-ptr
{
#if 0
// Less good solution with a hidden operator<.
{
std::set, std::less<>> s;
s.insert(std::make_unique(1, -1));
s.insert(std::make_unique(2, -2));
s.insert(std::make_unique(0, 0));
s.insert(std::make_unique(3, -3));
assert((*s.find(0))->notkey == 0);
assert((*s.find(1))->notkey == -1);
assert((*s.find(2))->notkey == -2);
assert((*s.find(3))->notkey == -3);
}
#endif
// Better solution with a custom comparator.
{
std::set, PointerCmp> s;
s.insert(std::make_unique(1, -1));
s.insert(std::make_unique(2, -2));
s.insert(std::make_unique(0, 0));
s.insert(std::make_unique(3, -3));
assert((*s.find(0))->notkey == 0);
assert((*s.find(1))->notkey == -1);
assert((*s.find(2))->notkey == -2);
assert((*s.find(3))->notkey == -3);
}
}
}
}