if i understand it correctly, then:
*Its better to use array of vectors if value is int
*Its better to use maps if value is not int, cause indexes wont work without int
#some thoughts about adjacency list
hollow spruce
hazy abyssBOT
hollow spruce
by array of vectors I mean:
const big_num = 10000;
vector<int> v[big_num];
v[node].push_back(node);
by mapping i mean:
map<int, vector<int>> m;
m[node].push_back(node);
remove, insertation, search is better at array of vectors
but it sucks in terms of memory, compared to map
so, if time is in my priority, than i should use array of vectors ?
cedar oyster
if i understand it correctly, then:
*Its better to use array of vectors if value...
This statement is very confusing
Vectors are for contiguous, ordered storage of elements
Maps (unordered or not) are for associative storage of elements
They do two different things
Use the best tool for the job, and profile later. If speed is of concern, you can use more performant map structures from github that say stuff all the nodes into a flat buffer making lookup incredibly fast.
hollow spruce
This statement is very confusing
Well
Best implementation of adjacency list with integer values (1 -> 2, etc) looks like array of vectors, because you can quickly access element (with index) and it's nodes
But when there is no int, you can't use index in order to access element, that's when map is best option
Right?
cedar oyster
firstly, if you're just looking at solutions on things like leetcode or something, they're probably only using standard stuff in the language
secondly, an adjacency list/matrix has different access patterns than what your question was implying
but to answer the question, you could use an index if you hash the string itself
(which is exactly what unordered_map does)
Note that you can store strings by index
you just can't use the string itself to look up
that's why I am making the distinction between associative containers and indexed containers
They do two completely different things so what you want depends on what you're doing
hollow spruce
Well if i want to work with integer graph, than arrays are better because associative container (map) is slower then array
Because I can use index of array, which is faster than hash map
cedar oyster
for graphs, you probably want to use contiguous containers yes. But you can go one step further and flatten the structure into a 1-dimensional array, as well.
hollow spruce
Nah, that's hard, inconvenient
cedar oyster
when optimizing, convenience is usually not a priority 😛
just make a function to convert the indexes for you
hollow spruce
when optimizing, convenience is usually not a priority 😛
Also true
Thanks
But wait
hollow spruce
for graphs, you probably want to use contiguous containers yes. But you can go o...
Contiguous container will take additional space
cedar oyster
Well that's where the concept of sparse vs dense matrices come in
they have tradeoffs
Space is generally expendable fyi
hollow spruce
Well that's where the concept of sparse vs dense matrices come in
In this case, is sparse vs dense most optimal way?
cedar oyster
like, they both have pros and cons
hollow spruce
Oh i thought its some concept 
hollow spruce
Well that's where the concept of sparse vs dense matrices come in
Looks like it's not a major optimisation