将新值放入数组 C++ 时即时排序
Instant sort when put new value in array C++
我有一个动态分配的数组，其中包含具有键值对值的结构。我需要编写一个更新（键，值）函数，将新结构放入数组中，或者如果具有相同键的结构已经在数组中，它需要更新它的值。插入和更新合二为一。
问题是：
在添加结构之前，我需要检查具有此键的结构是否已经存在。
我可以遍历数组的所有元素并比较键（非常慢）
或者我可以使用二进制搜索，但 (!) 数组必须排序。
所以我尝试在每次更新时对数组进行排序 (sloooow) 或在调用二进制搜索函数时对其进行排序.....这是每次更新
最后，我认为必须有一种方法可以将结构插入数组，这样 它会被放置在正确的位置并始终排序。
但是，我想不出这样的算法，所以我来这里寻求帮助，因为 google 拒绝读懂我的想法。
我需要使我的代码更快，因为我的数组接受超过 50 000 个结构并且我正在使用冒泡排序（因为我很笨）。
看看红黑树：http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
他们将确保数据始终排序，并且插入的复杂度为 O ( log n )。
二叉堆是不够的，因为二叉堆没有保证的排序顺序，您唯一的保证是顶部元素是最小或最大。
一种可能的方法是使用不同的数据结构。由于没有真正需要保持结构有序，只需要检测具有相同键的结构是否存在，因此在平衡树中保持顺序的成本过高（例如使用 std::map） .一个更 suitable 的数据结构是散列 table。 C++11 在标准库中以晦涩的名称 std::unordered_map (http://en.cppreference.com/w/cpp/container/unordered_map).
提供了这样的功能
如果您坚持使用数组，可能的方法是结合这些算法：
- 布隆过滤器（http://en.wikipedia.org/wiki/Bloom_filter）
- 部分排序（http://en.cppreference.com/w/cpp/algorithm/partial_sort）
- 二分查找
在数组中维护两个范围 -- 首先进入一个已经排序的范围，然后进入一个尚未排序的范围。插入结构时，首先检查布隆过滤器是否可能已经存在匹配的结构。如果布隆过滤器给出否定答案，则只需在数组末尾插入结构。之后排序范围不变，未排序范围增加一个。
如果布隆过滤器给出肯定的答案，则应用部分排序算法对整个数组进行排序，然后使用二分查找检查是否确实存在这样的对象。如果是这样，请替换此元素。之后排序的范围是整个数组，未排序的范围是空的。
如果二分查找显示布隆过滤器错误，匹配的结构不存在，那么你只需将新结构放在数组的末尾即可。之后排序范围是整个数组减一，未排序范围是数组中的最后一个元素。
每次插入一个元素，二分查找是否存在。如果它不存在，二分搜索会给你一个你可以插入它的索引。
您可以使用 std::set，它不允许重复的元素并将元素放在排序的位置。这假设您将键和值存储在一个结构中，而不是分开存储。为了使排序正常工作，您需要为结构定义一个比较函数。
我有一个动态分配的数组，其中包含具有键值对值的结构。我需要编写一个更新（键，值）函数，将新结构放入数组中，或者如果具有相同键的结构已经在数组中，它需要更新它的值。插入和更新合二为一。
问题是：
在添加结构之前，我需要检查具有此键的结构是否已经存在。
我可以遍历数组的所有元素并比较键（非常慢）
或者我可以使用二进制搜索，但 (!) 数组必须排序。
所以我尝试在每次更新时对数组进行排序 (sloooow) 或在调用二进制搜索函数时对其进行排序.....这是每次更新
最后，我认为必须有一种方法可以将结构插入数组，这样 它会被放置在正确的位置并始终排序。
但是，我想不出这样的算法，所以我来这里寻求帮助，因为 google 拒绝读懂我的想法。
我需要使我的代码更快，因为我的数组接受超过 50 000 个结构并且我正在使用冒泡排序（因为我很笨）。
看看红黑树：http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
他们将确保数据始终排序，并且插入的复杂度为 O ( log n )。
二叉堆是不够的，因为二叉堆没有保证的排序顺序，您唯一的保证是顶部元素是最小或最大。
一种可能的方法是使用不同的数据结构。由于没有真正需要保持结构有序，只需要检测具有相同键的结构是否存在，因此在平衡树中保持顺序的成本过高（例如使用 std::map） .一个更 suitable 的数据结构是散列 table。 C++11 在标准库中以晦涩的名称 std::unordered_map (http://en.cppreference.com/w/cpp/container/unordered_map).
如果您坚持使用数组，可能的方法是结合这些算法：
- 布隆过滤器（http://en.wikipedia.org/wiki/Bloom_filter）
- 部分排序（http://en.cppreference.com/w/cpp/algorithm/partial_sort）
- 二分查找
在数组中维护两个范围 -- 首先进入一个已经排序的范围，然后进入一个尚未排序的范围。插入结构时，首先检查布隆过滤器是否可能已经存在匹配的结构。如果布隆过滤器给出否定答案，则只需在数组末尾插入结构。之后排序范围不变，未排序范围增加一个。
如果布隆过滤器给出肯定的答案，则应用部分排序算法对整个数组进行排序，然后使用二分查找检查是否确实存在这样的对象。如果是这样，请替换此元素。之后排序的范围是整个数组，未排序的范围是空的。
如果二分查找显示布隆过滤器错误，匹配的结构不存在，那么你只需将新结构放在数组的末尾即可。之后排序范围是整个数组减一，未排序范围是数组中的最后一个元素。
每次插入一个元素，二分查找是否存在。如果它不存在，二分搜索会给你一个你可以插入它的索引。
您可以使用 std::set，它不允许重复的元素并将元素放在排序的位置。这假设您将键和值存储在一个结构中，而不是分开存储。为了使排序正常工作，您需要为结构定义一个比较函数。