- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
这个问题之前有人问过here我承认,但现在是 4 年前了,所以我敢要求更新:
我需要一种方法来将元组/对添加到容器并有效地搜索左右元素。
Boost 有 bimap
和 multi_index
,它们完全符合我的要求,但我想知道在普通现代 C++-11/14 中推荐的替代方案是什么,以防您不想要引入对 boost 的依赖(无论出于何种原因)。
链接中的一个答案表明不需要 s.th。由于透明比较器,它不再像 bimap 了。接受的答案建议将 std::map
组合到 key1
-> key2
和 key2
-> key1
.
我真的不知道透明比较器如何在这里帮助我,我只是好奇是否有一些你应该这样做以及为什么 - 解决方案。你能提供一些提示/链接吗?
最佳答案
我认为这只是很多繁琐的工作。
为了好玩,我开始在这里实现一个起点。
注意事项:
std::list<tuple<K,V>>
.这确保迭代器/引用失效语义尽可能接近 std::map
尽可能std::reference_wrapper<value_type const>
所以我们只索引第一个容器,真的我只实现了简单的查询( lower_bound
、 upper_bound
、 equal_range
和 find
)。当然有迭代器和 ranged-for。
您还有一些事情要做( erase
、 emplace
、范围插入、初始化列表构造;有状态分配器/比较器支持很粗略(没有构造函数采用相关参数),但作用域分配器已被纳入帐户。)
事不宜迟:
#include <algorithm>
#include <tuple>
#include <list>
#include <functional> // for std::reference_wrapper
#include <cassert>
namespace bimap {
namespace detail {
template <typename Cmp, typename V, size_t I> struct CompareByElement : private Cmp {
bool operator()(V const& a, V const& b) const {
using std::get;
return Cmp::operator()(get<I>(a), get<I>(b));
}
bool operator()(V const& a, V const& b) {
using std::get;
return Cmp::operator()(get<I>(a), get<I>(b));
}
};
namespace tags {
struct left_view;
struct right_view;
}
template <typename ViewTag, typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
struct view_traits;
template <typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
struct view_traits<tags::left_view, Left, Right, LeftCmp, RightCmp, RawAlloc> {
using value_type = std::tuple<Left, Right>;
using allocator_type = typename RawAlloc::template rebind<value_type>::other;
using base_type = std::list<value_type, allocator_type>;
using comparator = CompareByElement<LeftCmp, value_type, 0>;
};
template <typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
struct view_traits<tags::right_view, Left, Right, LeftCmp, RightCmp, RawAlloc> {
using value_type = std::tuple<Left, Right>;
using allocator_type = typename RawAlloc::template rebind<std::reference_wrapper<value_type const>>::other;
using base_type = std::list<std::reference_wrapper<value_type const>, allocator_type>;
using comparator = CompareByElement<RightCmp, value_type, 1>;
};
template <typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
struct bimap_traits {
using left_traits = view_traits<tags::left_view, Left, Right, LeftCmp, RightCmp, RawAlloc>;
using right_traits = view_traits<tags::right_view, Left, Right, LeftCmp, RightCmp, RawAlloc>;
};
template <typename Traits> struct map_adaptor :
private Traits::base_type,
private Traits::comparator // empty base class optimization
{
using value_type = typename Traits::value_type;
using allocator_type = typename Traits::allocator_type;
using base_type = typename Traits::base_type;
using comparator = typename Traits::comparator;
using iterator = typename base_type::iterator;
using const_iterator = typename base_type::const_iterator;
using base_type::cbegin;
using base_type::cend;
using base_type::begin;
using base_type::end;
using base_type::insert;
using base_type::size;
auto lower_bound(value_type const& v) { return std::lower_bound(base_type::begin(), base_type::end(), v, get_comp()); }
auto upper_bound(value_type const& v) { return std::upper_bound(base_type::begin(), base_type::end(), v, get_comp()); }
auto equal_range(value_type const& v) { return std::equal_range(base_type::begin(), base_type::end(), v, get_comp()); }
auto lower_bound(value_type const& v) const { return std::lower_bound(base_type::begin(), base_type::end(), v, get_comp()); }
auto upper_bound(value_type const& v) const { return std::upper_bound(base_type::begin(), base_type::end(), v, get_comp()); }
auto equal_range(value_type const& v) const { return std::equal_range(base_type::begin(), base_type::end(), v, get_comp()); }
auto find(value_type const& v) {
auto er = equal_range(v);
return er.first == er.second? end() : er.first;
}
auto find(value_type const& v) const {
auto er = equal_range(v);
return er.first == er.second? end() : er.first;
}
base_type& base() { return *static_cast<base_type*>(this); }
base_type const & base() const { return *static_cast<base_type const*>(this); }
private:
comparator& get_comp() { return *this; }
comparator const& get_comp() const { return *this; }
};
}
template <typename Left, typename Right,
typename LeftCmp = std::less<Left>, typename RightCmp = std::less<Right>,
typename RawAlloc = std::allocator<void>,
typename Traits = detail::bimap_traits<Left, Right, LeftCmp, RightCmp, RawAlloc>
>
class bimap : private detail::map_adaptor<typename Traits::left_traits> {
public:
using left_type = typename detail::map_adaptor<typename Traits::left_traits>;
using right_type = typename detail::map_adaptor<typename Traits::right_traits>;
using value_type = typename Traits::left_traits::value_type;
using allocator_type = typename Traits::left_traits::allocator_type;
using base_type = left_type;
using const_iterator = typename base_type::const_iterator;
using iterator = const_iterator;
using base_type::cbegin;
using base_type::cend;
auto begin() const { return cbegin(); }
auto end() const { return cend(); }
using base_type::size;
left_type const& left() const { return *this; }
right_type const& right() const { return inverse_index; }
std::pair<const_iterator, bool> insert(value_type const& v) {
auto lr = left().find(v);
auto rr = right().find(v);
bool hasl = lr!=left().end(),
hasr = rr!=right().end();
if (!hasl && !hasr) {
auto lins = mutable_left().insert(left().lower_bound(v), v);
auto rins = mutable_right().insert(right().lower_bound(*lins), *lins);
(void) rins;
return { lins, true };
} else {
return { end(), false };
}
}
private:
detail::map_adaptor<typename Traits::right_traits> inverse_index;
left_type& mutable_left() { return *this; }
right_type& mutable_right() { return inverse_index; }
};
}
#include <iostream>
#define CHECK(cond) do {\
if (cond) { } else { std::cout << "FAILED: " #cond "\n"; } } while(false)
int main() {
using Map = bimap::bimap<int, std::string>;
Map bm;
CHECK(bm.insert(std::make_tuple(1,"three")).second);
// now left 1 and right "three" are taken:
CHECK(!bm.insert(std::make_tuple(1,"two")).second);
CHECK(!bm.insert(std::make_tuple(2,"three")).second);
// unrelated keys insert fine
CHECK(bm.insert(std::make_tuple(2,"aaaa")).second);
// thing contains 2 elements now:
CHECK(bm.size() == 2);
using std::get;
for (Map::value_type const& p : bm) std::cout << get<0>(p) << ", " << get<1>(p) << "; "; std::cout << "\n";
for (Map::value_type const& p : bm.left()) std::cout << get<0>(p) << ", " << get<1>(p) << "; "; std::cout << "\n";
// right view map orders by right index
for (Map::value_type const& p : bm.right()) std::cout << get<0>(p) << ", " << get<1>(p) << "; "; std::cout << "\n";
// you can do find, lower_bound, equal_range etc. on both sides
}
打印:
1, three; 2, aaaa;
1, three; 2, aaaa;
2, aaaa; 1, three;
关于c++ - 没有 Boost 的现代 C++ 中的 bimap 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35521562/
我有一个库(围绕nlohmann / json封装),可以从JSON反序列化: struct MyStruct { int propertyA; std::string propert
如果 的第 1、3、5、7、9、11、13 或 15 位之一,我希望 var 不等于 FALSE输入已设置。 一个似乎相当普遍的解决方案是: int var = 1 & (input >> 1) |
当我说目标类型时,我的意思是使用接收者变量或参数的类型作为信息来推断我分配给它的部分代码。例如,在 C# 中,您会编写类似这样的内容来传递可为 null 的值或 null (空)如有必要: void
我需要从 native 内存读取/写入一堆结构。我想弄清楚我是否应该为结构对齐而烦恼。这是我编写的用于测试的简单代码。它将压缩结构写入未对齐的指针,然后读回该结构: public static uns
采用以下代码: char chars[4] = {0x5B, 0x5B, 0x5B, 0x5B}; int* b = (int*) &chars[0]; (int*) &chars[0] 值将在循环(
因此,当我发现将整个解决问题的方法颠倒过来时,我正在网上搜索最佳实践,以实现使用多个数据存储的存储库模式。这就是我所拥有的... 我的应用程序是一个BI工具,它从四个数据库中提取数据。由于内部限制,我
我想仅使用现代 OpenGL 技术(即没有即时模式的东西)来设置正交投影。我在网络上看到有关如何处理此问题的相互矛盾的信息。 有些人说调用 glMatrixMode(GL_PROJECTION) 然后
我想知道当前的 cpus 是否避免在其中至少一个为零时将两个数字相乘。谢谢 最佳答案 这取决于 CPU 和(在某些情况下)操作数的类型。 较旧/较简单的 CPU 通常使用如下乘法算法: integer
在精美的 OpenGL 新版本(3.0 和 4.0 以上)中,不推荐使用 gl_Vertex 等内置顶点属性 .实际渲染任何东西的“新方法”是为位置、颜色等指定您自己的顶点属性,然后将这些自定义属性绑
在我的 OpenGL 研究(我认为是 OpenGL 红皮书)中,我遇到了一个关节机器人 ARM 模型的示例,该模型由“上臂”、“下臂”、“手”和五个或更多“手指”。每个部分都应该能够独立移动,但受“关
像 Kaby Lake 这样的现代 CPU 如何处理小分支? (在下面的代码中,它是跳转到标签 LBB1_67)。据我所知,分支不会有害,因为跳转低于 16 字节块大小,即解码窗口的大小。 或者是否有
编辑:此问题假设您启用了发生检查。不是关于 setting Prolog flags . 30 年前有很多关于在安全的情况下自动优化发生检查的论文(大约 90% 的谓词,在典型的代码库中)。提出了不同
现在是 2020 年,在 iOS 终于添加了对 Widget 的支持之后,Widget 再次风靡一时。但是,自 2012 年以来,Android 小部件似乎没有更新。 来自 Android docs
我正在看一些关于算法的讲座,教授用乘法作为如何改进朴素算法的例子...... 它让我意识到乘法并不是那么明显,虽然当我编码时我只是认为它是一个简单的原子操作,乘法需要一个算法来运行,它不像求和数字那样
我们将 PIXI.js 用于内部使用 WebGL 进行渲染的游戏。时不时地,我会偶然发现避免 NPOT 纹理(https://developer.mozilla.org/en-US/docs/Web/
我是一名计算机科学专业的学生,即将毕业。我们现在必须用我们选择的语言编写完整的应用程序。我们选择 Objective-C 因为我们都是 Mac 人。 为了让我们的教授高兴,必须做一些事情:-)一项
我正在编写一个带有 x86 后端的 JIT 编译器,并且正在学习 x86 汇编器和机器代码。大约 20 年前,我使用 ARM 汇编程序,并对这些架构之间的成本模型差异感到惊讶。 具体来说,内存访问和分
如果负载与两个较早的存储重叠(并且负载未完全包含在最旧的存储中),现代 Intel 或 AMD x86 实现能否从两个存储转发以满足负载? 例如,考虑以下序列: mov [rdx + 0], eax
http://www.lighthouse3d.com/opengl/glsl/index.php?ogldir2 报告 OpenGL 上下文中的半向量是“眼睛位置 - 灯光位置”,但接着又说“幸运的
在现代 (GL3.3+) GPU 上使用 GLSL 时,在统一上进行分支的可能成本是多少? 在我的引擎中,我已经达到了拥有大量着色器的程度。我为其中的很多预设了几种不同的质量预设。就目前情况而言,我在
我是一名优秀的程序员,十分优秀!