Iterator

Upper Bound

Note that std::upper_bound(x.begin(), x.end(), val) finds an element which is greater than the val. However, std::lower_bound(x.begin(), x.end(), val), finds an element which is greater or equal to the val.

#include <iostream>
#include <deque>
#include <algorithm>

int main(int argc, char *argv[]) {
  std::deque<int> v{1,2,3,4,5,7,10};

  auto x = 5;
  auto pos1 = std::upper_bound(v.begin(), v.end(), x);
  std::cout << *pos1 << "\n";

  auto pos2 = std::lower_bound(v.begin(), v.end(), x);
  std::cout << *pos2 << "\n";

  // 7
  // 5
}

Insert an Element into a Sorted List

#include <iostream>
#include <deque>
#include <algorithm>
#include <range/v3/view/all.hpp>


int main(int argc, char *argv[]) {
  std::deque<int> v{1,2,3,4,5,7,10};

  auto x = 8;
  auto pos = std::upper_bound(v.begin(), v.end(), x);
  v.insert(pos, x);
  std::cout << ranges::views::all(v) << "\n";
  // [1,2,3,4,5,7,8,10]
}

Erase an Element in a Sorted List

#include <iostream>
#include <deque>
#include <algorithm>
#include <range/v3/view/all.hpp>


int main(int argc, char *argv[]) {
  std::deque<int> v{1,2,3,4,5,7,10};

  auto x = 7;
  auto pos = std::lower_bound(v.begin(), v.end(), x);
  v.erase(pos);
  std::cout << ranges::views::all(v) << "\n";
  // [1,2,3,4,5,10]
}

Reverse Range-based for Loop

// via boost
// $ g++ --std=c++14 -Wall -Werror -g -O3 reverse.cpp
// $ ./a.out
// dlrow olleh

#include <iostream>
#include <string>
#include <boost/range/adaptor/reversed.hpp>

using namespace boost;

int main(int argc, char *argv[]) {
  std::string in = "hello world";
  std::string out;
  for (const auto &c : adaptors::reverse(in)) {
      out += c;
  }
  std::cout << out << "\n";
}

Customize an Iterator

// $ g++ -std=c++17 -Wall -Werror -g -O3 a.cc

#include <iostream>
#include <memory>

template <typename T>
class Array
{
 public:
  class iterator
  {
    public:
      iterator(T *ptr) : ptr_{ptr} {}
      iterator operator++() { auto i = *this; ++ptr_; return i; }
      iterator operator++(int) { ++ptr_; return *this;};
      T &operator*() { return *ptr_; }
      T *operator->() { return ptr_; }
      bool operator==(const iterator &rhs) { return ptr_ == rhs.ptr_; }
      bool operator!=(const iterator &rhs) { return ptr_ != rhs.ptr_; }
    private:
      T *ptr_;
  };

  class const_iterator
  {
    public:
     const_iterator(T *ptr) : ptr_{ptr} {}
     const_iterator operator++() { auto i = *this; ++ptr_; return i; }
     const_iterator operator++(int) { ++ptr_; return *this; }
     const T &operator*() const { return *ptr_; }
     const T *operator->() const { return ptr_; }
     bool operator==(const const_iterator &rhs) { return ptr_ == rhs.ptr_; }
     bool operator!=(const const_iterator &rhs) { return ptr_ != rhs.ptr_; }
    private:
     T *ptr_;
  };

  Array(size_t size) : size_(size), data_{std::make_unique<T[]>(size)} {}
  size_t size() const { return size_; }
  T &operator[](size_t i) { return data_[i]; };
  const T &operator[](size_t i) const { return data_[i]; }
  iterator begin() { return iterator(data_.get()); }
  iterator end() { return iterator(data_.get() + size_); }
  const_iterator cbegin() const { return const_iterator(data_.get()); }
  const_iterator cend() const { return const_iterator(data_.get() + size_); }

 private:
  size_t size_;
  std::unique_ptr<T[]> data_;
};



int main(int argc, char *argv[])
{
  Array<double> points(2);
  points[0] = 55.66;
  points[1] = 95.27;
  for (auto &e : points) {
    std::cout << e << "\n";
  }
  for (auto it = points.cbegin(); it != points.cend(); ++it) {
    std::cout << *it << "\n";
  }
}

Iterate an Internal Vector

#include <iostream>
#include <utility>
#include <vector>

template<typename T>
class Vector {
 public:
  using iterator = typename std::vector<T>::iterator;
  using const_iterator = typename std::vector<T>::const_iterator;

  inline iterator begin() noexcept {return v.begin();}
  inline iterator end() noexcept {return v.end();}
  inline const_iterator cbegin() const noexcept {return v.cbegin();}
  inline const_iterator cend() const noexcept {return v.cend();}

  template<class... Args>
  auto emplace_back(Args&&... args) {
      return v.emplace_back(std::forward<Args>(args)...);
  }
 private:
  std::vector<T> v;
};


int main(int argc, char *argv[]) {
  Vector<int> v;
  v.emplace_back(1);
  v.emplace_back(2);
  v.emplace_back(3);

  for (auto &it : v) {
      std::cout << it << std::endl;
  }
  return 0;
}

Iterate a file

// $ g++ -std=c++17 -Wall -Werror -g -O3 a.cc
// $ ./a.out file

#include <iostream>
#include <iterator>
#include <fstream>
#include <string>

class line : public std::string {};

std::istream &operator>>(std::istream &is, line &l)
{
  std::getline(is, l);
  return is;
}

class FileReader
{
 public:
  using iterator = std::istream_iterator<line>;
  inline iterator begin() noexcept { return begin_; }
  inline iterator end() noexcept { return end_; }

 public:
  FileReader(const std::string path) : f_{path}, begin_{f_} {}
  friend std::istream &operator>>(std::istream &, std::string &);

 private:
  std::ifstream f_;
  iterator begin_;
  iterator end_;
};

int main(int argc, char *argv[])
{
  FileReader reader(argv[1]);
  for (auto &line : reader) {
    std::cout << line << "\n";
  }
}

Position after Erasing

// deque
    #include <iostream>
    #include <deque>
    #include <range/v3/view/all.hpp>

    int main(int argc, char *argv[]) {
      std::deque<int> q{1, 2, 3, 4, 5};
      auto it = q.begin() + 2;

      std::cout << *it << "\n";
      std::cout << ranges::views::all(q) << "\n";

      q.erase(it);
      std::cout << *it << "\n";
      std::cout << ranges::views::all(q) << "\n";

      // output
      //   3
      //   [1,2,3,4,5]
      //   4
      //   [1,2,4,5]
    }

#include <iostream>
#include <vector>
#include <range/v3/view/all.hpp>

int main(int argc, char *argv[]) {
  std::vector<int> v{1, 2, 3, 4, 5};
  auto it = v.begin() + 2;

  std::cout << *it << "\n";
  std::cout << ranges::views::all(v) << "\n";

  v.erase(it);
  std::cout << *it << "\n";
  std::cout << ranges::views::all(v) << "\n";

  // output
  //   3
  //   [1,2,3,4,5]
  //   4
  //   [1,2,4,5]
}

#include <iostream>
#include <list>
#include <range/v3/view/all.hpp>

int main(int argc, char *argv[]) {
  std::list<int> l{1, 2, 3, 4, 5};
  auto it = l.begin();
  ++it;

  std::cout << *it << "\n";
  std::cout << ranges::views::all(l) << "\n";

  // Note that Iterators, pointers and references referring to elements
  // removed by the function are invalidated. This is an example to show
  // that an iterator do not point to the next element after erasing.
  l.erase(it);
  std::cout << *it << "\n";
  std::cout << ranges::views::all(l) << "\n";
  // output
  //   2
  //   [1,2,3,4,5]
  //   2
  //   [1,3,4,5]
}

Vector Comparision

Note that the comparision operators are removed in C++20 (see [doc](https://en.cppreference.com/w/cpp/container/vector)). Therefore, using a lambda function as compare function is better than using default comparision when elements are not builtin types or has its own comparision operators.

#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
    std::vector<int> v1{5,2};
    std::vector<int> v2{2,3,4};
    std::cout << (v1 < v2) << "\n";
    // output: 0
}