First C++ data structures exam

(You)

profs on suicide watch

delete this

I'm glad that JavaScript programmers doesn't have to deal with linked lists.

how do you make a doubly linked list with constant time access? isn't one of list's caveats that random access is O(n)?
other than that, this is super easy, if only you paid attention in classes

Attached: 45301761_10213514279953662_3099517111127506944_n1.jpg (300x300, 26K)

>JavaScript programmers
No such thing.

This sounds stupid but tie your doubly linked list it with a hashmap for constant time.

How about JavaScript scripters, or JavaScripters if that would be acceptable?

It's constant access once you found the element :^)

you would get a 0, comp sci might be the only field outside of humanities so detached from reality that the fact it's not considered a scam is beyond me.

Wtf do you mean by constant access

std::such>

He's correct, though, he literally made an array, that has constant time access and modification, of doubly linked lists of strings.

Access to the element, to read or modify it. In array there's a constant access by the index, in list there's a constant access by the iterator(it doesn't get invalidated when you insert/delete from std::list unlike some other data structures).

Is it even possible to not have this?

This

It's basically a hash table, but if it's your first DS exam then it's pretty fucked up.

C++ programmers hate using declarations for some reason. You could just as easily have Vector>

Because std has many defined names that you're likely to unknowingly define yourself. I was scratching my head for a long time figuring out why my max function doesn't work the way I wrote it.

That's an argument against using namespace std;, not using String = std::string; You won't get any unintentional collisions if you merely declare what you use.

>using String = std::string
Is this even legal in C++? I've only seen stuff like that in C#.

Yes. You could shorten it to simply using std::string; if you're happy with the lowercase form.

It's frankly astonishing to me that this isn't standard practice in C++ even though it's standard practice everywhere else.

Hash table to each node.

That's not standard practice? Do C++ programmers just love typing std:: constantly?

>legacy pointers
3/10 see me after class

i like where this is going

Why is university so autistic
WHY don't they just ask you to build something that actually serves a function or ask you to contribute to opensource software

There's literally nothing wrong with raw pointers when used correctly. Read Herb Sutter.

It's either that or they do using namespace std; which is even worse in my humble opinion.

>There's literally nothing wrong with smart pointers. Period.

unique_ptr is inappropriate and unwieldy here because no element in a doubly linked list has exclusive ownership over any other and shared_ptr incurs an overhead that is entirely unnecessary.

Go back to java, you fucking retard.

>linked lists
>constant time access and modification
u wut m8?

How about a stack of hashmaps of dynamic arrays of linked lists of min heaps?

Because a data structures class is likely the second programming class you take. You barely have any experience with programming at all, and can hardly be expected to do serious work. What they give you instead is exercises. In later classes, you may be expected to work on projects that will be developed over the course of the semester.

Gotta learn to walk before you can run.

sweetie…

>WHY don't they just ask you to build something that actually serves a function
are you saying data structures don't serve a function?

> v;

Don't all arrays have this?

Lists don't though. The OP's problem is too vaguely worded.

>WHY don't they ask 2nd year students with CS 101 knowledge to contribute to open source
Fuck so that's why Linux still sucks?

yo what did jibberish mean haha

>What is std::shared_ptr

>I can't read

Arrays don't have constant access if you don't know where the element you want to access is

>he fell for CS college degree
user, studying CS in college is waste of time, you can learn everything you need on the internet, slap few projects and get a well paying job
t. regretting CS graduate

This is exceedingly trivial
Kill yourself.

Upgrade your compiler
Spacing your arrows is no longer required

C++ template errors gave me PTSD.

You get the hang of it.

>get an iterator from the collection
>write iturns out it's not a random access iterator
>3 pages of irrelevant errors

The constant time access obviously applies to the array.

If the program have to run on a real computer this is impossible due to caches and virtualization of memory.

>Make an array of doubly linked lists of strings with constant time access and modification
So a hash table?

>how do you make a doubly linked list with constant time access?
Assuming OP means a hash table, it's only not-constant in the case of collisions.

This is why I need 1GB of RAM to open your shitty webpage

Skiddies.

Why not use just the things that you actually repeat a lot? It beats repeating std:: a milion times or clobbering the namespace.
using std::foo;
using std::bar;

That's exactly what I'm advocating.

oh, carry on then

IMO anyone who gets butthurt over namespaces in C++ hasn't worked with a huge code base. Out of C++'s many, often horrific, flaws, namespaces aren't really one of them. Headers can die in a fucking fire though.

This is the difference between junior and full performance programmers. Understanding how design impacts performance. Constant time means whichever array element you want to access takes the same number of CPU operations. In a simple linked list you have 'random access time' of o(n) meaning the fastest element select time you can count on is the size of the list, since the element you want might be at the end.

I'm perfectly in agreement with you.

Constant access by which parameter?

Amen. I hate that we had to do it, but we started adding shit tests to our hiring screening because our leads were wasting so much time interviewing 'cs grads' who never took the time to learn fundamentals. The ones that squeezed through would bring asinine memory leaks and bloat to code reviews. There's still hope to save them, but wish they would have learned it in school instead of on the job.

You're part of the problem with computational efficiency

>you can learn everything you need on the internet
Yeah sure

How does it feel to be a brainlet?

I'm a JavaScript programmer and I implement linked lists all the time, usually hashed linked lists.

there are but if you are such a whining faggot just switch out the struct word to class and put public: on the first line and there you go.jesus i fucking hate this generation

anyone have Algorith Design Manual annotated PDF? On libgen there is only 1700 pages long, html-like mess. I cannot use long PDF's without good table of content on the left desu

You cant access anything in a linked list in constant time.

Just implement your code to iterate over the whole list regardless of the access index.
Every access take the same worst case scenario time, every access is constant.

I've only started to learn but love this thread already.

Attached: 630384.gif (100x100, 9K)

It's still O(n) because it will take longer for longer lists.

gotchu
ufile.io/04q8g

>ufile.io/04q8g
perfect, thanks a lot

Whats so bad about headers? You'd rather recompile everything every single time?

Modern languages have module systems. They do not require you to recompile vast swathes of the source code needlessly, and do not require you to duplicate definitions and declarations.

test uself with BASIC programming
if (You) cannot evven BASIC
C++ will be just waste of time

you cant have constant time access for a linked list unless you indexed them and did pointer magic to automatically jump to the Xth element instead of traversing. But then its kinda sorta an array

cont.
2 solutions to this:
Either add an explicit index in the object, which is updated on every add/remove and points directly to each object (like a list wrapper)
Or, just put all the objects right next to eachother in memory and use an inferred index, based on the memory size of each node

ArrayList is a thing.

It's not really a list though.

That's not constant time access. Is it possible to have constant time access in any linked list?

>why do you use c instead of c++ user? C++ is a superset of c!
Its because I don't want to associate with "programmers" like you and the abysmal slop you call code.

The absolute state of c++ pajeets

Attached: thats_some_heresy.png (680x386, 266K)

Is this bait?

>not calling Node Nd
>nt dfnng yr wn str lib w shty vrnms

No the reason for that is the fact that safari exists. Apple doesn't give a shit about standards and thus you need libraries to make stuff that works on basically all other browsers work in safari - the Internet explorer of browsers.

>shared pointers
>nothing can be automatically deleted because of mutual dependency

Kill yourself, cs monkey

onlinegdb.com/B1fFwEY3M

Just replace int with std::string

Here's an outline.
#include
#include

template
class double_linked_list {
private:
struct node{
T data;
node* prev;
std::unique_ptr next;
node(T data, node* prev): data{data}, prev{prev} {}
~node()=default;
};
std::unique_ptr head;
node* tail;

public:
double_linked_list(std::initializer_list list){
if (list.size()==0){
head=nullptr;
tail=nullptr;
return;
}
auto it = list.begin();
head = std::make_unique(*it, nullptr);
auto curr_node = head.get();
while(++it != list.end()){
curr_node->next = std::make_unique(*it, curr_node);
curr_node = curr_node->next.get();
}
tail = curr_node;
}
~double_linked_list()=default;

void add_to_tail(T x){
tail->next = std::make_unique(x, tail);
tail=tail->next.get();
}
void delete_tail(){
tail = tail->prev;
tail->next.reset(); //give up ownership of tail
}
void add_to_head(T x){
auto oldhead=head.release(); //give up ownership of head
head = std::make_unique(x, nullptr);
oldhead->prev=head.get();
head->next.reset(oldhead); //gain ownership of old head
}
void delete_head(){
auto newhead = head->next.release(); //give up ownership of the new head
head.reset(newhead); //delete head and regain ownership of the new head
}
T& operator[](size_t n){
auto curr_node = head.get();
while(n && curr_node!=tail){
--n;
curr_node = curr_node->next.get();
}
return curr_node->data;
}
};

>arrows

>It's frankly astonishing to me that this isn't standard practice in C++ even though it's standard practice everywhere else.

Maybe because it only works for non-template types in this form. Anything else will have a slightly different and more verbose syntax.