STL术语一对一关系 [英] One-to-one relation in STL terms

问题描述

据我所知，C ++(STL)甚至C ++ 1y中都没有双向映射datastruct/ADT.但是我需要一个分类的关联容器，该容器可以让我将键集映射到值集，反之亦然.

As I know there is no biunivocal mapping datastruct/ADT in C++ (STL) and even C++1y. But I need a sorted associative container that allows me to map key set into value set and vice versa.

什么是最佳方法或现有解决方案?

What is the best approach or existant solution?

我的建议是:

#!/usr/bin/env bash -vex
# cls ; bash self.bash 2>&1 | tee self.log | less
WARN="-W -Wall -Wextra -Werror"
g++ -x c++ - -std=gnu++1y $WARN -Ofast -o a <<__EOF && ./a && echo -e "\e[1;32msucceeded\e[0m" || echo -e "\e[1;31mfailed\e[0m"
#include <list>
#include <tuple>
#include <map>
#include <functional>

#include <string>

#include <cstdlib>
#include <cassert>

template< typename A, typename B >
class bijection
{

    using data_type = std::list< std::tuple< A const, B const > >;

public :

    using iterator = typename data_type::iterator;
    using const_iterator = typename data_type::const_iterator;

private :

    using direct_mapping_type = std::map< std::reference_wrapper< A const >, iterator, std::less< A const & > > ;
    using inverse_mapping_type = std::map< std::reference_wrapper< B const >, iterator, std::less< B const & > >;
    using direct_iterator = typename direct_mapping_type::iterator;
    using inverse_iterator = typename inverse_mapping_type::iterator;

public :

    auto size() const { return data_.size(); }

    iterator find(A const & a)
    {
        auto const direct = direct_mapping_.find(a);
        if (direct == direct_mapping_.end()) {
            return data_.end();
        } else {
            return direct->second;
        }
    }

    iterator find(B const & b)
    {
        auto const inverse = inverse_mapping_.find(b);
        if (inverse == inverse_mapping_.end()) {
            return data_.end();
        } else {
            return inverse->second;
        }
    }

    auto erase(iterator pos)
    {
        auto const & element = *pos;
        direct_mapping_.erase(std::get< 0 >(element));
        inverse_mapping_.erase(std::get< 1 >(element));
        return data_.erase(pos);
    }

    template< typename X, typename Y >
    std::tuple< iterator, bool, bool > insert(X && x, Y && y)
    {
        direct_iterator direct = direct_mapping_.find(x);
        inverse_iterator inverse = inverse_mapping_.find(y);
        bool const d = (direct != direct_mapping_.end());
        bool const i = (inverse != inverse_mapping_.end());
        if (d && i) {
            iterator ix = inverse->second;
            iterator iy = direct->second;
            inverse_mapping_.erase(inverse);
            direct_mapping_.erase(direct);
            if (ix != iy) {
                inverse_mapping_.erase(std::get< 1 >(*iy));
                direct_mapping_.erase(std::get< 0 >(*ix));
                data_.erase(iy);
                data_.erase(ix);
            } else {
                data_.erase(ix); // iy
            }
        } else if (d) {
            iterator iy = direct->second;
            direct_mapping_.erase(direct);
            inverse_mapping_.erase(std::get< 1 >(*iy));
            data_.erase(iy);
        } else if (i) {
            iterator ix = inverse->second;
            inverse_mapping_.erase(inverse);
            direct_mapping_.erase(std::get< 0 >(*ix));
            data_.erase(ix);
        }
        data_.emplace_back(std::forward< X >(x), std::forward< Y >(y));
        auto const & element = data_.back();
        iterator it = --data_.end();
        direct_mapping_.emplace(std::get< 0 >(element), it);
        inverse_mapping_.emplace(std::get< 1 >(element), it);
        return std::make_tuple(it, d, i);
    }

private :

    data_type data_;
    direct_mapping_type direct_mapping_;
    inverse_mapping_type inverse_mapping_;

};

int main()
{
    using A = std::size_t;
    using B = std::string;
    using M = bijection< A, B >;
    M m;
    assert(1 == (m.insert(A(111), B("111")), m.size()));
    assert(1 == (m.insert(A(111), B("111")), m.size()));
    assert(2 == (m.insert(A(222), B("222")), m.size()));
    assert(3 == (m.insert(A(333), B("333")), m.size()));
    assert(2 == (m.insert(A(222), B("111")), m.size()));
    assert(3 == (m.insert(A(111), B("222")), m.size()));
    assert(2 == (m.insert(A(111), B("111")), m.size()));
    assert(1 == (m.insert(A(333), B("111")), m.size()));
    assert(1 == (m.insert(A(333), B("333")), m.size()));
    assert(1 == (m.insert(A(111), B("333")), m.size()));
    assert(0 == (m.erase(m.find(A(111))), m.size()));
    return EXIT_SUCCESS;
}
__EOF

推荐答案

如果您需要已测试的东西，可以使用

If you need something already tested you can use Boost Bimap library.

这篇关于STL术语一对一关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！