Список:: размер () действительно O (n)?
Как насчет чего-то типа:
var lines = System.IO.File.ReadAllLines("...");
System.IO.File.WriteAllLines("...", lines.Take(lines.Length - 1).ToArray());
Объяснение:
Технически вы не удаляете строку из файла. Вы читаете содержимое файла и записываете его обратно, исключая контент, который хотите удалить.
. Что этот код делает, это прочитать все строки в массиве и записать эти строки обратно в файл, исключая только последние линия. (Метод Take () (часть LINQ) принимает количество строк, указанное в нашем случае, length - 1). Здесь var lines можно прочитать как String[] lines.
4 ответа
ПредC++ 11 ответов
Вы корректны, который стандарт не говорит что сложность списка:: размер () должен быть - однако, он действительно рекомендует, чтобы он "имел постоянную сложность" (Примечание A в Таблице 65).
Вот интересная статья Howard Hinnant , который объясняет, почему некоторые люди думают список:: размер () должен иметь O (N) сложность (в основном, потому что они полагают что O (1) список:: размер () входит в список:: соединение встык () имеет O (N) сложность), и почему O (1) список:: размер () быть хорошей идеей (по мнению автора):
я думаю, что основные моменты в газете:
- существует немного ситуаций, где поддержание внутреннего количества так
list::size()может быть O (1) причины операция соединения встык для становления линейным - существует, вероятно, намного больше ситуаций, где кто-то мог бы не знать об отрицательных эффектах, которые могли бы произойти, потому что они называют O (N)
size()(такой как его один пример, гдеlist::size()назван при содержании блокировки). - , что вместо того, чтобы разрешить
size()быть O (N), в интересах 'наименьшего количества удивления', стандарт должен потребовать любого контейнера, который реализуетsize()для реализации его в O (1) вид. Если контейнер не может сделать этого, он не должен реализовыватьsize()вообще. В этом случае пользователь контейнера будет проинформирован, чтоsize()недоступно, и если они все еще хотят или должны получить число элементов в контейнере, они могут все еще использоватьcontainer::distance( begin(), end())для получения того значения - но они будут абсолютно знать, что это - O (N) операция.
я думаю, что я склонен соглашаться с большей частью его обоснования. Однако мне не нравится его предложенное дополнение к эти splice() перегрузки. Необходимость передать в n, который должен быть равен [1 110] для получения корректного поведения, походит на рецепт для трудно для диагностирования ошибок.
я не уверен, что должно или могло быть сделано, продвинувшись, поскольку любое изменение окажет значительное влияние на существующий код. Но как есть, я думаю, что на существующий код уже влияют - поведение могло бы довольно существенно отличаться от одной реализации до другого для чего-то, что должно было быть четко определено. Возможно, комментарий onebyone о кэшировании и маркировке размера, известного/неизвестного, мог бы работать хорошо - Вы амортизируетесь O (1) поведение - единственное время, Вы получаете O (N), поведение состоит в том, когда список изменяется некоторым соединением встык () операции. Хорошая вещь об этом состоит в том, что это может быть сделано конструкторами сегодня без изменения в стандарте (если я не пропускаю что-то).
, Насколько я знаю, C++ 0x ничего не изменяет в этой области.
Я должен был изучить gcc 3.4's список:: размер прежде, таким образом, я могу сказать это:
- это использует станд.:: расстояние (голова, хвост)
- станд.:: расстояние имеет две реализации: для типов, которые удовлетворяют RandomAccessIterator, он использует "хвост-голову", и для типов, которые просто удовлетворяют InputIterator, он использует O (n) алгоритм, полагающийся "на итератор ++", рассчитывая, пока он не поражает данный хвост.
- станд.:: список не делает satsify RandomAccessIterator, таким образом, размер является O (n).
относительно, "почему", я могу только сказать что станд.:: список подходит для проблем, которые требуют последовательного доступа. При хранении размера, поскольку переменная класса представила бы наверху на каждой вставке, удалила бы, и т.д., и что отходы являются большим нет - нет на намерение STL. При реальной необходимости в постоянно-разовом размере (), используйте станд.:: двухсторонняя очередь.
Я лично не вижу проблему с соединением встык, являющимся O (N) как единственная причина, почему размеру разрешают быть O (N). Вы не платите за то, что Вы не используете , важный девиз C++. В этом случае поддержание размера списка требует дополнительного инкремента/декремента на каждом вставляемое/стирать, проверяете ли Вы размер списка или нет. Это - маленькие фиксированные издержки, но ее все еще важный для рассмотрения.
Проверка размера списка редко необходима. Итерация от начинает заканчиваться, не заботясь, что общий размер бесконечно более распространен.
Я перешел бы в источник ( архив ). Страница STL SGI говорит, что разрешено иметь линейную сложность. Я полагаю, что руководство по проектированию, за которым они следовали, должно было позволить реализации списка быть максимально общей, и таким образом позволить больше гибкости в использовании списков.