struct Point { int x, y; }; // для начала, зафиксируем тип точки
// в будущем можно его сделать произвольным - а алгоритм, соответственно, полиморфным

// для тех, кому нравится работать с произвольными контейнерами:
template<class InIter, class OutIter>
OutIter convex_hull(InIter begin, InIter end, OutIter dst)
{
  std::vector<Point> points(begin, end);
  do_convex_hull(points);
  std::copy(points.begin(), points.end(), dst);
}

// нешаблонная функция - реализацию можно вынести в отдельный .cpp
// тип рабочего контейнера зафиксирован - vector<Point>
// (в будущем можно сделать произвольным - например, vector<void*>
//  плюс передавать стратегию для работы с точками: функции
//  get_x(void const*), get_y(void const*), remove(void*)
// )
void do_convex_hull(std::vector<Point>& points)
{
  // отсортировать в полярных координатах
  // удалить точки, образующие вогнутые углы
}

struct ConvexHullBuilder
{
  std::vector<Point> left, right;
  void add(Point pt);
};

I read about the problem of finding Convex Hull in Algorithm Design Manual and knew that the complexity should be N for points sorted by one coordinate. Before reading about existing solutions I determined to find my own. “Invent the wheel” in other words. I spent hours thinking about a solution. In the end I found one:

template<typename RanIt,typename InIt>
RanIt monotone_chain(InIt first_point,InIt last_point, RanIt first,RanIt last)
{
    while(first_point!=last_point)
    {
        while
        (
            (last-first)>=2 &&
            cross(last[-2], last[-1], *first_point)<=0
        )
            --last;
        *last++ = *first_point++;
    }
    return last;
}
 
template<typename RanItIn,typename RanItOut>
RanItOut convex_hull(RanItIn first_point,RanItIn last_point, RanItOut first)
{
    typedef reverse_iterator<RanItIn> RevIn;
    if(first_point==last_point)
        return first;
    sort(first_point,last_point);
    first = monotone_chain(first_point,last_point, first,first);
    --first;
    return monotone_chain(RevIn(last_point),RevIn(first_point), first,first);
}
 
template<typename RanIt>
vector<value_type<RanIt>> convex_hull(RanIt first_point,RanIt last_point)
{
    vector<value_type<RanIt>> result(2*distance(first_point,last_point));
    result.erase
    (
        convex_hull(first_point,last_point,begin(result)),
        end(result)
    );
    return result;
}

К>"Выпуклая оболочка", дорогой Ватсон!

К>struct Point { int x, y; };

class PointQueue
{
public:
  SharedPoint NextPoint()
  {
    return NextPointInternal();
  }
};

К>struct ConvexHullBuilder
К>{
К>  std::vector<Point> left, right;
К>  void add(Point pt);
К>};
К>

К>4. shared_ptr'ы нигде не нужны. Откройте для себя передачу аргументов по ссылке

К>То есть, моё мнение: код нужно переделать вдребезги пополам

  is_white = find_if(
    data_ + position_, 
    end, 
    [](unsigned char p){return p != 0xFF;}) == end;

EP>>В плане твоей личной практики это безусловно полезно, но все остальным это ∥

G>Я не хотел передавать Point по значению, потому, что мой поинт был с двумя double — 16 байт.

Coding Standards 101 Rules Sutter and Alexandresku
59. Don't write namespace usings in a header file or before an #include
...
In short: You can and should use namespace using declarations and directives liberally in your implementation files after #include directives and feel good about it. Despite repeated assertions to the contrary, namespace using declarations and directives are not evil and they do not defeat the purpose of namespaces. Rather, they are what make namespaces usable.

In short: You can and should use namespace using declarations and directives liberally in your implementation files after #include directives and feel good about it. Despite repeated assertions to the contrary, namespace using declarations and directives are not evil and they do not defeat the purpose of namespaces. Rather, they are what make namespaces usable.

Namespaces deliver the powerful advantage of unambiguous name management. Most of the time, different programmers don't choose the very same name for a type or function; but on the off chance that they do so, and that the two pieces of code end up being used together, having those names in separate namespaces prevents them from colliding. (We don't, after all, want the global namespace pollution experienced by default in languages like C.) In the rare case when there is such an actual ambiguity, calling code can explicitly qualify a name to say which one it wants. But the vast majority of the time there is no ambiguity: And that is why namespace using declarations and directives are what make namespaces usable, because they greatly reduce code clutter by freeing you from having to tediously qualify every name every time (which would be onerous, and frankly people just won't put up with it) and still letting you qualify names only in those rare cases when you need to resolve an actual ambiguity.

Coding Standards 101 Rules Sutter and Alexandresku
44. Prefer writing nonmember nonfriend functions
Avoid membership fees: Where possible, prefer making functions nonmember nonfriends.

...
Since then, I've been battling programmers who've taken to heart the lesson that being object-oriented means putting functions inside the classes containing the data on which the functions operate. After all, they tell me, that's what encapsulation is all about.

They are mistaken.
...

10.3.2 Helper Functions
Typically, a class has a number of functions associated with it that need not be defined in the class itself because they don’t need direct access to the representation. For example:

int diff(Date a,Date b); // number of days in the range [a,b) or [b,a)
bool leapyear(int y);
Date next_weekday(Date d);
Date next_saturday(Date d);

Defining such functions in the class itself would complicate the class interface and increase the number of functions that would potentially need to be examined when a change to the representation was considered. How are such functions "associated" with class Date? Traditionally, their declarations were simply placed in the same file as the declaration of class Date, and users who needed Dates would make them all available by including the file that defined the interface.

While we could make a member function to return length, it is better to make it a global friend function. If we do that, we will be able eventually to define the same function to work on built-in arrays and achieve greater uniformity of design. I made size into a member function in STL in an attempt to please the standard committee. I knew that begin, end and size should be global functions but was not willing to risk another fight with the committee. In general, there were many compromises of which I am ashamed. It would have been harder to succeed without making them, but I still get a metallic taste in my mouth when I encounter all the things that I did wrong while knowing full how to do them right. Success, after all, is much overrated. I will be pointing to the incorrect designs in STL here and there: some were done because of political considerations, but many were mistakes caused by my inability to discern general principles.)

EP>То есть так: "Я не изучил существующие алгоритмы, не ждите сравнений и подчёркивание различий, а тем более устоявшейся терминологии. Так как я не знал уже готовые алгоритмы, отныне и навеки нарекаю приведённый алгоритм НОВЫМ ПРИДУМАННЫМ МНОЙ, ибо clean room design. Любые совпадения с реальными существующими алгоритмами являются чистой случайностью"

79. Store only values and smart pointers in containers

EP>Я показал реализацию без shared_ptr выше

G>class PointQueue
G>{
G>public:
G>  SharedPoint NextPoint()
G>  {
G>    return NextPointInternal();
G>  }
G>};
G>

class AlgoServer
{
public:
  void init();
  void step(Point);
  void done();
  void somehow_utilize_results(.....);
};

void algo_client()
{
  AlgoServer a;
  a.init();

  while(!end_of_file) { a.step(read_point()); }
  // на деле, там может быть вот такое
  for(current_point.x = ....) for(current_point.y = ......)
  {
    if(color(current_point) == what_we_need)
      a.step(current_point);
  }

  a.done();
  a.somehow_utilize_results(.....);
}

class AlgoClient
{
  bool eof() const;
  Point read();
};

void algo_server(AlgoClient& client)
{
  my_init();
  while(!client.eof()) my_step(client.read());
  // здесь сложно представить, что цикл будет затейливым (в отличие от предыдущего)
  // но может оказаться наоборот: что он банальный - например, просто прочитать точки во внутренний контейнер,
  // а вся жирная логика переедет в my_done()

  my_done();
  somehow_utilize_results();
}

void algo_conveyor(SourceOfPoints& src, Algorithm& alg, DestinationOfPoints& dst)
{
  alg.init();
  while(!src.eof()) alg.write(src.read());
  alg.done();
  Algorithm::Result res = alg.result();
  while(!res.eof()) dst.write(res.read());
}

К>>// для тех, кому нравится работать с произвольными контейнерами:
К>>template<class InIter, class OutIter>
К>>OutIter convex_hull(InIter begin, InIter end, OutIter dst)
К>>{
К>>  std::vector<Point> points(begin, end);
К>>  do_convex_hull(points);
К>>  std::copy(points.begin(), points.end(), dst);
К>>}

G>Я думаю все плюсники эту книжку должны любить пламенной любовью.

К>>4. shared_ptr'ы нигде не нужны. Откройте для себя передачу аргументов по ссылке

G>Я не хотел передавать Point по значению, потому, что мой поинт был с двумя double — 16 байт. Копировать их при передаче значения было бы долго. Использовать референсы можно было бы, но у меня они уже должны были быть обернутыми в shared_ptr, из-за Александреску с его правилами (см. выше)

К>>То есть, моё мнение: код нужно переделать вдребезги пополам

G>блин, ты бы видел какой пишут код тут у нас. Поубивал бы.