examples

Toy examples in single C files.
git clone git://henryandlizzy.uk/examples
Log | Files | Refs

flat-set.cpp (2335B)

      1 #include <vector>
      2 #include <iostream>
      3 #include <iterator>
      4 #include <algorithm>
      5 
      6 template <typename T>
      7 struct flat_set
      8 {
      9     using const_iterator = std::vector<T>::const_iterator;
     10     using iterator = const_iterator;
     11     using size_type = std::vector<T>::size_type;
     12 
     13     flat_set() = default;
     14 
     15     bool empty(void) const noexcept { return storage.empty(); }
     16     size_type size(void) const noexcept { return storage.size(); }
     17     size_type max_size(void) const noexcept { return storage.max_size(); }
     18 
     19     void clear(void) noexcept { storage.clear(); }
     20 
     21     const_iterator begin() const noexcept { return storage.begin(); }
     22     const_iterator end() const noexcept { return storage.end(); }
     23     const_iterator rbegin() const noexcept { return storage.rbegin(); }
     24     const_iterator rend() const noexcept { return storage.rend(); }
     25 
     26     std::pair<iterator, bool> insert(int v)
     27     {
     28         if (auto it = lower_bound(v); it != storage.end() && *it == v)
     29             return {it, false};
     30         else
     31             return {storage.insert(it, v), true};
     32     }
     33     template <typename I>
     34     void insert(I first, I last)
     35     {
     36         while (first != last)
     37             insert(*first++);
     38     }
     39     void insert(std::initializer_list<T> ilist)
     40     {
     41         insert(ilist.begin(), ilist.end());
     42     }
     43 
     44     const_iterator erase(const_iterator pos) { return storage.erase(pos); }
     45     const_iterator erase(const_iterator first, const_iterator last) { return storage.erase(first, last); }
     46     size_type erase(T const& key)
     47     {
     48         if (auto it = find(key); it != end())
     49         {
     50             erase(it);
     51             return 1;
     52         }
     53         return 0;
     54     }
     55 
     56     size_type count(T const& key) const noexcept { return std::binary_search(begin(), end(), key); }
     57 
     58     const_iterator lower_bound(T const& key) const { return std::lower_bound(begin(), end(), key); }
     59     const_iterator upper_bound(T const& key) const { return std::upper_bound(begin(), end(), key); }
     60 
     61     const_iterator find(T const& key) const { return std::find(begin(), end(), key); }
     62 
     63 private:
     64     std::vector<T> storage;
     65 };
     66 
     67 int main()
     68 {
     69     flat_set<int> ints;
     70 
     71     ints.insert({5,5,6,3,5,10});
     72 
     73     ints.insert(4);
     74     ints.erase(6);
     75 
     76     std::copy(ints.begin(), ints.end(), std::ostream_iterator<int>(std::cout, "\n"));
     77 
     78     return !std::is_sorted(ints.begin(), ints.end());
     79 }