本文介绍了STL术语一对一关系的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
据我所知,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推荐答案
如果您需要已测试的东西,可以使用增强Bimap 库.
If you need something already tested you can use Boost Bimap library.
更多推荐
STL术语一对一关系
发布评论