*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 24 февраля 2010 г.

Печать контейнера с разделителями

Иногда, при печати содержимого контейнера хочется избежать ненужного хвостового разделителя.

Простейшее решение выглядит так:

#include <iostream>
#include <vector>

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

  for (int i = 0; i < v.size(); ++i) {
    std::cout << v[i];
    if (i < v.size() - 1)
      std::cout << ", ";
  }
  std::cout << std::endl;

  return 0;
}

Условие в теле цикла решает поставленную задачу, но контейнеры лучше обходить через итераторы, поэтому следующая попытка может выглятеть так:

#include <iostream>
#include <vector>

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

  for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
    std::cout << *i;
    if (v.end() - i > 1)
      std::cout << ", ";
  }
  std::cout << std::endl;

  return 0;

Но такой подход не самый верный, ибо итераторы далеко не всех контейнеров поддерживают операцию вычетания. Например, при использовании std::list вместо std::vector будет ошибка компиляции (как, кстати, и для первого примера, но по другой причине). Поэтому правильнее было бы написать:

#include <iostream>
#include <vector>

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

  typedef std::vector<int>::const_iterator iterator;
  for (iterator i = v.begin(); i != v.end(); ++i) {
    std::cout << *i;
    if (std::distance<iterator>(i, v.end()) > 1)
      std::cout << ", ";
  }
  std::cout << std::endl;
  return 0;
}

Шаблонный класс std::distance умеет рассчитывать расстояние между итераторами, и даже для тех, которые не поддерживают операции сложения и вычетания. Для таких итераторов будет делаться пошаговый обход от одного к другому для подсчета расстояния. На первый взгляд получается, что вычислительная сложность такого простого цикла будет уже не линейной, а квадратической. Еше надо таскать за собой описание типа дважды — чтобы создать итератор цикла и экземпляр std::distance. Например, Visual Studio 2008 требует указывать тип итератора для шаблона std::distance и не может "угадать" его из параметров (другие компиляторы могут вести себя иначе). Получается, на ровном месте навернули какую-то ерунду.

Но есть весьма элегантный способ, который позволяет и использовать итераторы, и сохранить линейную сложность алгоритма для контейнеров, которые не умеют эффективно вычислять расстояние между элементами (например, std::list), и писать красиво и компактно:

#include <iostream>
#include <vector>

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

  for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
    std::cout << *i;
    if (i != --v.end())
      std::cout << ", ";
  }
  std::cout << std::endl;

  return 0;
}

Трюк с оператором "--" позволяет эффективно проверить на последний элемент контейнера.

8 комментариев:

  1. есть другой вариант, абсолютно универсальный и подходящий даже для си: печатать разделитель перед элементом, но не перед самым первым. Найти первый намного проще, правда ведь?

    ОтветитьУдалить
  2. bialix: Хм, ваша правда. Век живи, век учись.

    По идее, конечно, должно быть без разницы, сравнивать с первым или последним итератором, так как они оба известны на старте. Но из-за особенности итераторов в C++, когда end() указывает за последний элементы, а не на него, и надо вычислять один элемент назад (что и является темой упражнения), то прием с проверкой на первый элемент выглядит очень красиво.

    ОтветитьУдалить
  3. А вот, как это делается _не_ на C++:

    $ python
    >>> v = [1,2,3,4,5]
    >>> print ", ".join([str(x) for x in v])
    1, 2, 3, 4, 5
    >>>

    У С++ же сложности на пустом месте из-за бедной стандартной библиотеки.

    ОтветитьУдалить
  4. не все контейнеры двунаправленные, так что operator-- не всегда поможет

    есть boost::algorithm::join

    он как раз добавляет первый элемент, а потом джойнит все остальные через сепаратор:
    if(itBegin!=itEnd)
    {
    detail::insert(Result, ::boost::end(Result), *itBegin);
    ++itBegin;
    }

    for(;itBegin!=itEnd; ++itBegin)
    {
    // Add separator
    detail::insert(Result, ::boost::end(Result), ::boost::as_literal(Separator));
    // Add element
    detail::insert(Result, ::boost::end(Result), *itBegin);
    }

    return Result;

    ОтветитьУдалить
  5. Спасибо за пост.

    А можно небольшой оффтопик-вопрос? Как вы выделяете код как код, да еще и с подсветкой? А-то я тут немного новичек в жужл-блогах.

    ОтветитьУдалить
  6. Этот комментарий был удален автором.

    ОтветитьУдалить
  7. Green FiLin: Я использую highlight. В шаблоне блога надо добавить загрузку этого скрипта, и после этого все тэги code будут автоматически раскрашиваться.

    ОтветитьУдалить
  8. Если ставить разделитель перед элментами, то указатель не обязвтельно сравнивать с первым вообще. Нужно ввести bool, показывающий печатался ли первый элемент. Если да, выводим разделитель.

    bool first_writen = false;
    for (std::vector::const_iterator i = v.begin(); i != v.end(); ++i) {
    if (first_writen)
    std::cout << ", ";
    std::cout << *i;
    first_writen = true;
    }
    «Оптимазация» — два «цикла» с общим i.
    td::vector::const_iterator i = v.begin();
    if (i != v.end()) {
    std::cout << *i;
    i++;
    }
    for (; i != v.end(); ++i) {
    std::cout << ", ";
    std::cout << *i;
    }
    Но это, разумеется, нельзя назвать изящьным решением.

    ОтветитьУдалить