my intent mask implementation details of container such client not permitted rely on implicit insertion order. i'm trying enforce somehow altering order in iteration occurs.
i have container want randomly ordered when iterating. here pseudo code.
namespace abc { template<class t> class randomlist { void insert(t t); t erase(t t); iterator begin(); iterator end(); } } namespace test { int main() { randomlist<int> list; list.insert(1); list.insert(2); list.insert(3); (typename randomlist::iterator iter = list.begin(); iter != list.end(); ++iter) { std::cout << iter << std::endl; } } } output:
3, 1, 2 my question is, best way implement randomlist. naive thought hold member std::list , rand() determine whether insert front inserts or inserts.
any other ideas?
i'm using c++03, have access boost.
i'm not sure if understand aspects of problem. think qualifies solution largely depends on application , type t going in practice. in case, suggest alter interface of randomlist (see below).
first, idea use std::list internally , randomly insert @ front or seems possible solution.
i not think idea use std::vector if aim broad range of applications. reason std::vector implementations lot of stuff internally may harm performance/memory requirements of container type. std::vector uses memory buffer larger actual size of vector avoid allocations on subsequent calls of insertion operations push_back. therefore, performance of insertions may vary on subsequent calls (suddenly vector buffer has increased again...), , container may use more memory necessary. again: might not problem, depends on application , t is. user of randomlist interface, bothered hear uses std::vector internally...
so if asking "another idea" , want allow multiple insertions of same value container - here one: in essence, make randomlist std::map wrapper. randomization should implemented employing map key. iterate container use iterator of std::map. gives references (key,value) pairs. use std::map key implement additional features might interesting. first of all, can hide key type - , therefore hide details of implementation - introducing typedef randomlist::handle. recommend method insert returns randomlist::handle. in way, allow users directly access specific container values adding method access interface. access takes randomlist::handle argument , returns reference corresponding map value. if alter interface in way, consistent randomlist iterator (which map iterator) refers pairs of randomlist::handle , t. whether useful or not largely depends on t going be.
erase should take randomlist::handle argument. again: if multiple insertions not welcome, idea base implementation on std::map problematic, or @ least should approached in different manner.
this approach allows neat control of "randomization implementation". example, if use std::list random insertions @ front or back, implementation of randomization closely tied internal storage/container implementation. implementation on basis of std::map keep details of randomization more seperate rest of implementation, randomization controlled in terms of map key selection. example, if use int key, hold counter internally incremented on subsequent insertions. current value of counter used key next map insertion. lead unbalanced tree structure, randomlist behave ordinary std::list on iterations. suggest choose new key values in such manner tree balanced. in way, direct access feature implemented efficiently (cause search operations fast), , straightforward iteration of randomlist/std::map via begin()/end() should lead sufficiently "random" result.
finally, regarding interface: suggest use perfect forwarding insert operation instead of direct copy. in way, avoid unneccessary copy operations when inserting elements std::map (same story std::list of course), , additionally allow move operations. if not want use perfect forwarding, @ least change t const t&, copy operation required insert object std::list/std::map container.
Comments
Post a Comment