Write 1 or 2 programs in C++ to perform an experiment in order to discover which

Question

Write 1 or 2 programs in C++ to perform an experiment in order to discover which Data Structure has a faster Delete operation

Note: the data structures to be compared are Linked List and Vectors.

Explanation / Answer

// algorithm to consume the std::list container, // supports: list,list template struct consume_list { groups_type operator()(list& l) { // remove spurious identicals and group the rest // algorithm: // 1. compare the first element with the remaining elements, // pick out all duplicated files including the first element itself. // 2. start over again with the shrinked list // until the list contains one or zero elements. groups_type sub_groups; group_type one_group; one_group.reserve(1024); while(l.size() > 1) { T front(l.front()); l.pop_front(); item_predicate ep(front); list::iterator it = l.begin(); list::iterator it_end = l.end(); while(it != it_end) { if(ep.equals(*it)) { one_group.push_back(ep.extract_path(*(it))); // single it out it = l.erase(it); } else { it++; } } // save results if(!one_group.empty()) { // save one_group.push_back(ep.extract_path(front)); sub_groups.push_back(one_group); // clear, memory allocation not freed one_group.clear(); } } return sub_groups; } }; // type for item-item comparison within a stl container, e.g. std::list template struct item_predicate{}; // specialization for type path_type template struct item_predicate { public: item_predicate(const path_type& base)/*init list*/ {} public: bool equals(const path_type& comparee) { bool result; /* time-consuming operations here*/ return result; } const path_type& extract_path(const path_type& p) { return p; } private: // class members }; };

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.