#include <string>
// структуру ListNode модифицировать нельзя
struct ListNode {
ListNode * prev;
ListNode * next;
ListNode * rand; // указатель на произвольный элемент данного списка, либо NULL
std::string data;
};
class List {
public:
void Serialize (FILE * file); // сохранение в файл (файл открыт с помощью fopen(path, "wb"))
void Deserialize (FILE * file); // загрузка из файла (файл открыт с помощью fopen(path, "rb"))
//not so private:
ListNode * head;
ListNode * tail;
int count;
};
#include <stdio.h>
#include <map>
#include <list>
#include <vector>
#include <memory>
#include <stdexcept>
// should be incremented every time class definition changes to support old serialized versions
static const auto List_version = 0; // could as well be a part of List class
void List::Serialize(FILE* f)
{
fprintf(f, "%d ", List_version);
// enumerate nodes
std::vector<ListNode*> nodes;
std::map<ListNode*, size_t> index;
if (this->count <= 0); // we only use "count" as an optimization guess to limit allocations count to 1
else nodes.resize(this->count);
for (std::list stack = { head, tail }; !stack.empty(); stack.pop_front())
if (auto* node = stack.front(); !node);
else if (auto& ix = index[node]; ix); // already enumerated
else
{ // new node
nodes.push_back(node);
index[node] = nodes.size();
stack.push_back(node->prev);
stack.push_back(node->next);
stack.push_back(node->rand);
}
// serialize nodes
fprintf(f, "%zd ", nodes.size());
for (auto* node : nodes)
fprintf(f, "%zd %zd %zd %zd %s"
, index[node->prev]
, index[node->next]
, index[node->rand]
, node->data.size()
, node->data.c_str());
// serialize *this
fprintf(f, "%zd %zd %d"
, index[this->head]
, index[this->tail]
, count);
}
#ifdef _MSC_VER
# define fscanf fscanf_s
#endif // _MSC_VER
void List::Deserialize(FILE* f)
try
{
if (auto list_version = 0; fscanf(f, "%d ", &list_version) != 1 || list_version != List_version)
// TODO : support deserializing older versions if necessary here...
throw std::runtime_error("Invalid serialized List version. Expected "
+ std::to_string(List_version) + ", got " + std::to_string(list_version));
std::vector<std::unique_ptr<ListNode>> nodes; // who thought it was a good idea to use naked pointers in List implementation?!
// deserialize nodes
if (size_t count = {}; fscanf(f, "%zd ", &count) != 1)
throw std::runtime_error("nodes count read failed");
else if (!count); // TODO : add sanity checks for max count size
else for (nodes.reserve(count); count --> 0 ;)
{
auto&& [prev, next, rand, data] = *nodes.emplace_back(new ListNode { 0, 0, 0, {} }).get();
if (fscanf(f, "%p %p %p ", &prev, &next, &rand) != 3)
throw std::runtime_error("node pointer content read failed");
// yes, we just read stored integers to pointers! beware not to dereference them until we're done with them
if (size_t size = {}; fscanf(f, "%zd ", &size) != 1)
throw std::runtime_error("node data read failed");
else if (!size); // TODO : add sanity checks for max data string size
else
{
data.resize(size);
if (fread(&data[0], 1, size, f) != size)
throw std::runtime_error("node data content read failed");
}
}
// get nodes pointers done
std::vector<bool> used(nodes.size()); // just to be sure we'll check all deserialized nodes are actually used
for (auto& node : nodes)
for (auto& ptr : { &ListNode::prev, &ListNode::next, &ListNode::rand })
if (auto& p = (*node).*ptr; (size_t)p > nodes.size())
throw std::runtime_error("node pointer index out of range");
else if (p)
{
used[(size_t)p-1] = true;
p = &*nodes[(size_t)p-1]; // now pointers are valid
}
List tmp; // do not change *this until we're absolutely sure deserialization completed successfully
if (fscanf(f, "%p %p %d", &tmp.head, &tmp.tail, &tmp.count) != 3)
throw std::runtime_error("List content read failed");
else for (auto& ptr : { &List::head, &List::tail })
if (auto& p = tmp.*ptr; (size_t)p > nodes.size())
throw std::runtime_error("List pointer index out of range");
else if (p)
{
used[(size_t)p-1] = true;
p = &*nodes[(size_t)p-1]; // pointers are valid
}
// deserialization completed successfully at this point
// release the nodes actually being used by the List to the wild now
for (auto i = nodes.size(); i --> 0 ;)
if (used[i])
nodes[i].release();
// everything is ready - update *this
this->head = tmp.head;
this->tail = tmp.tail;
this->count = tmp.count;
}
catch (const std::exception& ex)
{ // hail the RAII!
fprintf(stderr, ex.what());
}
int main()
{
List leak; // not even going to attempt at deleting this
leak.head = new ListNode { 0, 0, 0, "omg" };
leak.tail = new ListNode { 0, 0, 0, "wtf" };
leak.head->rand = new ListNode { 0, 0, 0, "brb" };
leak.tail->rand = new ListNode { 0, 0, 0, "bbq" };
// preparing invalid content with cycles is intended. glhf traversing it! xD
leak.head->next = leak.tail;
leak.tail->prev = leak.head;
auto testfile = fopen("C:\\Temp\\test", "wb");
leak.Serialize(testfile);
fclose(testfile);
List leak2; // let it leak leak leak
testfile = fopen("C:\\Temp\\test", "rb");
leak2.Deserialize(testfile);
fclose(testfile);
printf("%s\n", leak.head->data.c_str()); // omg
printf("%s\n", leak.tail->data.c_str()); // wtf
printf("%s\n", leak.head->rand->data.c_str()); // brb
printf("%s\n", leak.tail->rand->data.c_str()); // bbq
printf("%s\n", leak.head->next->data.c_str()); // wtf
printf("%s\n", leak.tail->prev->data.c_str()); // omg
// TODO : if we really want to avoid leaks - we should traverse nodes similar to Serialize() implementation
// TODO : we can also move temporary structures used in Serialize() to class members so ~List() is significantly faster, however additional measures such as subnodes creation via class methods (best), or explicit Sync calls (worst) should be taken to avoid desync'ing between actual nodes structure and internal helper data
return 0;
}
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}