Концептуальное понимание операций позиционного доступа к контейнерам - PullRequest
Новая
       20

Концептуальное понимание операций позиционного доступа к контейнерам

0 голосов
/ 20 января 2019

Как может выглядеть определение операции позиционного доступа † на контейнере, мне кажется довольно простым, когда дело доходит до std::vector, std::deque, std::list и std::forward_list. То есть доступ к элементу k th в коллекции состоит из получения элемента, хранящегося в положении k th в коллекции X .

Например, выражение vec[k-1] обращается к k th в std::vector, тогда как *std::next(lst.begin(), k-1) соответствует его std::list аналогу.

Однако, когда дело доходит до ассоциативных контейнеров , таких как std::set или std::unordered_set, мне не очень понятно, имеет ли смысл говорить о позиционных операциях доступа на самом деле, так как Я не нахожу простой способ определить местоположение произвольной позиции k th в таких контейнерах.

Тем не менее, мы можем продолжить, как в примере std::list, показанном выше, то есть перенести итератор в «первый» элемент ассоциативного контейнера (например, итератор, возвращаемый функцией-членом begin()) и затем переместите итератор вперед k-1 раз (например, с помощью std::next()).

Я заметил, что контейнеры std::vector, std::deque, std::list и std::forward_list все реализованы с использованием линейных структур данных, тогда как std::set, который обычно реализуется как бинарное дерево, нет. Таким образом, возможно, эта проблема связана с линейностью базовых структур данных, которые реализуют контейнеры.

Есть ли способ четко определить семантику позиционной операции доступа для ассоциативного контейнера? Или такие операции доступа не применимы к ним?

† Не путайте поиск и доступ операции. В операции поиска вы ищете элемент с данным ключом в коллекции.

X Это независимо от времени работы, которое требуется для этого (например, линейное для std::list вместо постоянного времени для std::vector) или от того, не существует выделенной функции-члена ( например, отсутствие оператора индекса в std::list) для достижения этого.

Ответы [ 2 ]

0 голосов
/ 20 января 2019

Как вы указали для списка, можно определить элемент k th , на который указывает указатель, который находится рядом с указателем, указывающим на k th-1 element.

Вы также можете заметить, что в теории чисел число также определяется как последовательность: 1 - это число рядом с 0, 2 - это число рядом с 1 и т. д. *

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

p0:=begin()                               O
  |next                                   |increment
p1:=next(begin())   --isomorphic to-->    1:=increment(0)
  |next                                   |increment
p2:=next(next(begin()))                   2:=increment(increment(0))
  .                                       .
  .                                       .

Этот изоморфизм может бытьиспользуется для любого контейнера, если он обеспечивает указатель начала.Итак, ради концепции положения любые контейнеры STL эквивалентны.

0 голосов
/ 20 января 2019

Большое различие между категориями контейнеров, которые вы упомянули, заключается в том, что первыми являются sequence контейнеры, где пользователь контейнера явно определяет, куда помещать элементы, в то время как последние ассоциативны. контейнеры, в которых результирующий порядок неявно определяется по некоторым свойствам элементов, чтобы обеспечить эффективный доступ к ним по ключу (std::map / std::unordered_map) / значению (std::set / std::unordered_set).

Это не означает, что доступ по "позиции" в таких контейнерах бесполезен - поскольку std::set сохраняет свои элементы отсортированными, элемент k th в std::set являетсяk th наименьший элемент в наборе (хотя действительно я не могу придумать какой-либо цели для доступа к std::unordered_set по позиции - хэши, как правило, не дают какого-либо особенно полезного порядка 1 ).

Помимо этого концептуального различия, я не вижу большой оперативной разницы между доступом к элементу k th в std::list и выполнением одного и того же в течение std::set - в обоих случаяхэта операция не «изначально» поддерживается контейнером (как, например, контейнер не поддерживает O (1) произвольный доступ), и вы должны пройти по одному элементу за раз.Даже в тайне обход бинарного дерева, такого как обычно используемые std::set или std::map, ничем не отличается от перехода по ссылкам в связанном списке (например, в std::list).

  1. Если std::hash был криптографическим хешем, который «отбеливает» исходные данные, это может иметь некоторый слабый смысл как «доступ к некоторому элементу случайной перестановки», но std::hash просто необходим, чтобы быть хорошораспределены по диапазону типов, например, целые числа часто хэшируются как самих себя - не особенно интересная перестановка.
...