AK
если только 1М взять за константу, то итерация по вектору константной длины и есть константа, да
Size: a a a
2020 August 17
AS
Чтобы получить и константный доступ по ключу и преимущества локальности при итерировании - это нужно положить хэш таблицу в вектор :) Из очевидных недостатков - вставка/удаление элементов будут дорогими, так что лучше будет сформировать коллекцию как заранее и потом её не модифицировать. Возможно, готовые реализации уже есть, ну или можно свою написать, там не так сложно.
ну вот у меня такая же идея. Пока я делал так: держал и мапу и вектор, элементы - shared_ptr, поэтому можно не сильно дорого держать и там и там. Так себе решение, но быстро и сравнительно удобно
AS
если только 1М взять за константу, то итерация по вектору константной длины и есть константа, да
имелось ввиду просто взять v[1M], это равносильно v.begin() + 1M, тогда как чтобы взять m[1M] придётся бежать от начала до 1М-элемента
AK
Alex Sandrov
имелось ввиду просто взять v[1M], это равносильно v.begin() + 1M, тогда как чтобы взять m[1M] придётся бежать от начала до 1М-элемента
Имелось в виду, что здесь половина людей разговаривают в терминах асимптотической скорости. Одинаково быстро итерироваться по вектору и по мапе — это значит и там, и там, рост времени одинаковый (линейный) с ростом кол-ва элементов, а не то, что итерация по контейнеру займёт одинаковое число машинных тактов.
AS
Имелось в виду, что здесь половина людей разговаривают в терминах асимптотической скорости. Одинаково быстро итерироваться по вектору и по мапе — это значит и там, и там, рост времени одинаковый (линейный) с ростом кол-ва элементов, а не то, что итерация по контейнеру займёт одинаковое число машинных тактов.
Это понятно, хорошо. Мне важен быстрый доступ по порядковому индексу.
AK
ну тогда вектор+мапа, как уже и есть, насколько я понял. норм решение, ничего не "так себе"
AS
Alex Sandrov
Это понятно, хорошо. Мне важен быстрый доступ по порядковому индексу.
Это вектор или дека. Random access O(1). Ну, еще unordered_map с этой же сложностью, но на практике все очень сильно будет зависеть от хеш функции и числа коллизий на реальных данных.
A
Воюю с unique_ptr и incomplete type. Система такая:
a.hpp:
a.hpp:
struct A{};
b.hpp:#include <memory>b.cpp:
struct A;
struct B {
~B();
std::unique_ptr<A> a;
};
#include "a.hpp"B::~B() {}
main.cpp:#include "b.hpp"Получаю ошибку удаления incomplete type
int main(){
B b;
return 0;
}
A в main.cpp. КАК??? Почему?SE
Воюю с unique_ptr и incomplete type. Система такая:
a.hpp:
a.hpp:
struct A{};
b.hpp:#include <memory>b.cpp:
struct A;
struct B {
~B();
std::unique_ptr<A> a;
};
#include "a.hpp"B::~B() {}
main.cpp:#include "b.hpp"Получаю ошибку удаления incomplete type
int main(){
B b;
return 0;
}
A в main.cpp. КАК??? Почему?а что мешает сделать ~B() = default; ?
AK
определение A недоступно из main.cpp
AK
только объявление
AK
#include "a.hpp" надоA
только объявление
Да, в этом и смысл forward declaration. А зачем в main.cpp определение деструктора А, если юник пойнтер разрушается деструктором В, а деструктор В в другом .срр файле и другом TU????
AK
там тоже нет определения
AK
его нигде нет, насколько я вижу