Карта C ++ - самообращающийся итератор - PullRequest
Новая
       18

Карта C ++ - самообращающийся итератор

0 голосов
/ 21 февраля 2019

Есть ли способ объявить std::map, чей тип значения является итератором для себя? 

map<string, map<string, (#)>::iterator> myMap;

Приведенный выше фрагмент кода не будет работать, потому что типу итератора нужно знать второй аргумент шаблона, помеченный как (#).(это было бы само по себе).

Цель состоит в том, чтобы избежать выполнения ненужных операций find для доступа к элементу, на который указывает другой элемент - в отличие от использования map<string, string>.

Ответы [ 2 ]

0 голосов
/ 21 февраля 2019

Только через стирание типа.Например, вы можете использовать std::any

std::map<std::string, std::any> myMap;
auto inserted = myMap.emplace("foo", std::any());

// how it can be populated:
inserted.first->second = inserted.first;
using it_type = decltype(myMap.begin());

// how values can be extracted:
auto it = std::any_cast<it_type>(myMap["foo"]);

РЕДАКТИРОВАТЬ: Кажется, что следующее работает (clang-7.0.0 и gcc-8.2), но это недопустимо (в основномstd::map не указывает, что допускаются неполные типы): 

struct Iter;
using Map = std::map<std::string, Iter>;
struct Iter {
    Map::iterator it;
};
0 голосов
/ 21 февраля 2019

Такое определение невозможно, так как тип значения и тип итератора будут взаимно бесконечно рекурсивными.

Это можно обойти это, используя немного косвенности.Можно даже избежать динамического выделения std::any и того факта, что std::map<K,V> не определено, если не завершено V.

Но решение немного сложное и основано на некоторых предположениях, которыеразумны, но не определены стандартом.Смотрите комментарии в реализации.Основная хитрость заключается в том, чтобы отложить определение типа переменной-члена до определения класса-оболочки.Это достигается путем повторного использования необработанного хранилища.

Первое использование: 

int main()
{
    Map map;
    auto [it, _] = map.emplace("first", iter_wrap{});
    map.emplace("maps to first", conv::wrap(it));
    // erase first mapping by only looking
    // up the element that maps to it
    map.erase(conv::it(map.find("maps to first")));
}

Определение 

struct NoInitTag {} noInitTag;

class iter_wrap
{
public:
    iter_wrap();
    ~iter_wrap();
    iter_wrap(const iter_wrap&);
    iter_wrap(iter_wrap&&);
    const iter_wrap& operator=(const iter_wrap&);
    const iter_wrap& operator=(iter_wrap&&);

private:
    // We rely on assumption that all map iterators have the same size and alignment.
    // Compiler should hopefully warn if our allocation is insufficient.
    using dummy_it = std::map<int, int>::iterator;
    static constexpr auto it_size = sizeof(dummy_it);
    static constexpr auto it_align = alignof(dummy_it);
    alignas(it_align) std::byte store[it_size];

    explicit iter_wrap(NoInitTag){}
    friend struct conv;
};

using Map = std::map<std::string, iter_wrap>;
using It = Map::iterator;

struct conv {
    static constexpr It&
    it(iter_wrap&& wrap) noexcept {
        return *std::launder(reinterpret_cast<It*>(wrap.store));
    }
    static constexpr const It&
    it(const iter_wrap& wrap) noexcept {
        return *std::launder(reinterpret_cast<const It*>(wrap.store));
    }
    template<class It>
    static const iter_wrap
    wrap(It&& it) {
        iter_wrap iw(noInitTag);
        create(iw, std::forward<It>(it));
        return iw;
    }
    template<class... Args>
    static void
    create(iter_wrap& wrap, Args&&... args) {
        new(wrap.store) It(std::forward<Args>(args)...);
    }
    static constexpr void
    destroy(iter_wrap& wrap) {
        it(wrap).~It();
    }
};

iter_wrap::iter_wrap() {
    conv::create(*this);
}
iter_wrap::iter_wrap(const iter_wrap& other) {
    conv::create(*this, conv::it(other));
}
iter_wrap::iter_wrap(iter_wrap&& other) {
    conv::create(*this, std::move(conv::it(other)));
}
const iter_wrap& iter_wrap::operator=(const iter_wrap& other) {
    conv::destroy(*this);
    conv::create(*this, conv::it(other));
    return *this;
}
const iter_wrap& iter_wrap::operator=(iter_wrap&& other) {
    conv::destroy(*this);
    conv::create(*this, std::move(conv::it(other)));
    return *this;

}
iter_wrap::~iter_wrap() {
    conv::destroy(*this);
}

Старый ответ;Предполагалось, что это не было важной возможностью избежать поиска при обходе сохраненных сопоставлений.

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

using Set = std::set<std::string>;
using Map = std::map<Set::iterator, Set::iterator>;

Обратите внимание, что эти две структуры данных автоматически не синхронизируются.Элемент, добавленный в набор, не имеет автоматического сопоставления с другим, а элемент, удаленный из набора, оставляет висячие итераторы на карте.Поэтому было бы разумно написать собственный контейнерный класс, который обеспечивает необходимые инварианты.

...