C++ Logo

std-proposals

Advanced search

[std-proposals] New Data structure.

From: organicoman <organicoman_at_[hidden]>
Date: Wed, 03 Jan 2024 23:48:46 +0400
Hello Gents,I would like to suggest a new data structure that combines 'std::unordered_set' and a 'std::stack' behavior.I will refere to it as 'std::hashed_stack'.Important methods of 'std::hashed_stack' container are: -'push': to insert a key, and if it already exists nothing will happen. -'pop': to extract the last key inserted.The nodes of this data structure will have an extra data members ;let's name it "node_type::last_inserted"; which points to the bucket index of the last key inserted. (Single linked list of bucket indexes)."node_type::last_inserted" can self point to the bucket index of its key, if this key's hash is congruent with the bucket index (hash collision)'std::hashed_stack::end()': node will have a garbage key value, but a "node_type::last_inserted" value equal to the bucket index of the last inserted key. Thus, when popping keys, we start from ::end(), we read the bucket index of the last inserted key, we visit that bucket then grab the head of the linked list, we read its "node_type::last_inserted" value, we update our "end" node with this value, then erase that key .i.e poping it.Testing existence of any key, will follow the "std::unordered_set" data structure behavior.(hash->traverse)Only push & pop operations will be allowed to modify this container. All the usual member functions are the same as 'std::stack' with some extra, i.e:std::hashed_stack::size()std::hashed_stack::empty()std::hashed_stack::contains(const T& key)std::hashed_stack::push(const T& key)std::hashed_stack::bucket_index(const T& key)std::hashed_stack::pop()std::hashed_stack::begin() /cbegin()std::hashed_stack::end() / cend()std::hashed_stack::first() -> keystd::hashed_stack::last() -> keystd::hashed_stack::clear()std::hashed_stack::bucket_count()......etcComments and discussions are welcome. RegardsNadir Sent from my Galaxy

Received on 2024-01-03 19:48:54