Эффективно найти количество элементов в диапазоне в C ++ set [duplicate]

Question

Эффективно найти количество элементов в диапазоне в C ++ set [duplicate]

Связанный .lib-файл связан с .dll

У меня была такая же проблема. Скажем, у меня есть проекты MyProject и TestProject. Я эффективно связал файл lib для MyProject с TestProject. Однако этот файл lib был создан, так как была построена DLL для MyProject. Кроме того, я не содержал исходный код для всех методов в MyProject, но только доступ к точкам входа DLL.

Чтобы решить проблему, я построил MyProject как LIB и связал TestProject с этим .lib-файлом (скопируйте вложенный файл .lib в папку TestProject). Затем я смогу снова создать MyProject как DLL. Он компилируется, поскольку lib, с которым связан TestProject, содержит код для всех методов в классах MyProject.

4

stl set time-complexity

задан TemplateRex 7 August 2013 в 13:30

3 ответа

Другие вопросы по тегам:

stl set time-complexity

Похожие вопросы:

score 4 · Answer 1

Нет; сбалансированное дерево не нужно хранить количество потомков каждого узла, что требуется для более быстрого вычисления distance( s.begin(), iter ) для std::set s и итератора iter (что, как вы полагаете, означает). Поэтому информация просто не существует, кроме как путем подсчета элементов по одному.

Если вам нужно выполнить много таких вычислений, скопируйте set в отсортированную последовательность случайного доступа, такую как vector или deque, но затем модификация последовательности становится дорогой.

Структура дерева данных, которая делает то, что вы просите, вероятно, существует в свободной библиотеке где-то, но я не знаю об этом.

4

ответ дан Potatoswatter 26 August 2018 в 02:53

1

– user2613413 7 August 2013 в 06:22
2

– Potatoswatter 7 August 2013 в 07:25
3

– TemplateRex 7 August 2013 в 07:43
4

– Potatoswatter 7 August 2013 в 07:54
5

– TemplateRex 7 August 2013 в 08:05

score 2 · Answer 2

То, что вы ищете, называется деревом статистики по порядку . Если вы используете библиотеку GNU C ++, у вас должно быть расширение, доступное для построения статистики статистики заказов. Ниже приведен краткий пример:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <cstdio>
using namespace std;
using namespace pb_ds;

typedef tree<
int, /* key type */
null_mapped_type, /* value type */
less<int>, /* comparison */
rb_tree_tag, /* for having an rb tree */
tree_order_statistics_node_update> order_set;

int main()
{
    order_set s;
    s.insert(10);
    s.insert(20);
    s.insert(50);
    s.insert(25);

    printf("rank of 25 = %d\n", s.order_of_key(25));
}

Выход должен быть rank of 25 = 2. Дополнительные примеры: этот файл .

score 2 · Answer 3

Функциональность сортированного вектора, предложенная @Potatoswatter, обеспечивается flat_set из Boost.Container . В документации перечислены следующие компромиссы

Более быстрый поиск, чем стандартные ассоциативные контейнеры
Гораздо более быстрая итерация, чем стандартные ассоциативные контейнеры
Меньшее потребление памяти для небольших (и для больших объектов, если используется shrink_to_fit)
Улучшена производительность кеша (данные хранятся в непрерывной памяти)
Нестабильные итераторы (итераторы недействительны при вставке и стирании элементов)
Невозможно сохранить не скопируемые и не движимые типы значений
. Слабая безопасность исключений, чем стандартные ассоциативные контейнеры (конструкторы копирования / перемещения могут бросать при сдвиге значений в стираниях и вставках)
Более медленная вставка и стирание, чем стандартные ассоциативные контейнеры (специально для не подвижных типов)