g*********s
发帖数: 1782 | 1 I have a the following data structure:
std::vector::iterator> X (x_sz);
Question: what is the initial value for X[0]..X[x_sz-1]? Do we have a "NULL"
iterator here? | p*u
发帖数: 2454 | 2
"NULL"
no. if u use it without setting a valid value it would be undefined
behavior. if u need an initial state u can use pointer to iterator, which
is more convoluted though.
【在 g*********s 的大作中提到】
: I have a the following data structure:
: std::vector::iterator> X (x_sz);
: Question: what is the initial value for X[0]..X[x_sz-1]? Do we have a "NULL"
: iterator here?
| g*********s
发帖数: 1782 | 3 So it seems I have to take the following weird detour?
std::list dummy_queue;
std::list::iterator dummy_it (dummy_queue.end());
X.resize(x_sz, dummy_it);
What if dummy_queue is changed later? That means the value in X is stale and potentially dangerous?
Any better solution? We don't have such headache if we just use self-defined doubly linked list and the initial value NULL for X elements. I expect a stl based solution can achieve similar behaviour.
【在 p*u 的大作中提到】
:
: "NULL"
: no. if u use it without setting a valid value it would be undefined
: behavior. if u need an initial state u can use pointer to iterator, which
: is more convoluted though.
| p*u
发帖数: 2454 | 4
and potentially dangerous?
defined doubly linked list and the initial value NULL for X elements. I
expect a stl based solution can achieve similar behaviour.
first question is why u have to use X, not the list directly? do u want
random access dummy_queue? u can add a X::iterator member to dummy queue
elements; when u delete from dummy_queue, u need to delete the element in
X first through X::iterator( note delete in vector is not very efficient
). but it's convoluted, why do u have to use X?
【在 g*********s 的大作中提到】
: So it seems I have to take the following weird detour?
: std::list dummy_queue;
: std::list::iterator dummy_it (dummy_queue.end());
: X.resize(x_sz, dummy_it);
: What if dummy_queue is changed later? That means the value in X is stale and potentially dangerous?
: Any better solution? We don't have such headache if we just use self-defined doubly linked list and the initial value NULL for X elements. I expect a stl based solution can achieve similar behaviour.
| b******n
发帖数: 592 | 5 end is not null, it points to *after* last item. you have to take care of
iterators when you modify stl container. Why do you need a list of iterators
.
and potentially dangerous?
defined doubly linked list and the initial value NULL for X elements. I
expect a stl based solution can achieve similar behaviour.
【在 g*********s 的大作中提到】
: So it seems I have to take the following weird detour?
: std::list dummy_queue;
: std::list::iterator dummy_it (dummy_queue.end());
: X.resize(x_sz, dummy_it);
: What if dummy_queue is changed later? That means the value in X is stale and potentially dangerous?
: Any better solution? We don't have such headache if we just use self-defined doubly linked list and the initial value NULL for X elements. I expect a stl based solution can achieve similar behaviour.
| g*********s
发帖数: 1782 | 6 It's a long story.
I'm designing a LRU cache. For each char ch being accessed, there's an int
typed time stamp. For example, ('a', 3) means @ time 3 we access char 'a'.
The cache must support fast operations of the following:
query(char ch)
insert(char key, int time_stamp)
get_earliest_time(int time&)
get_latest_time(int time&).
I use a vector X and a sorted doubly linked list Y. The sorted linked list
would keep the latest time stamp of each char, and the vector would keep the
address of each element in the list.
To insert one element, for example, ('a', 3), we do the following:
it = X['a'];
if ( is_valid_iterator(it) ) list.erase(it);
list.push_back(3);
it1 = list.end(); it1 --;
X['a'] = it;
query:
it = X['a'];
if ( is_valid_iterator(it) ) return (*it);
Obviously, get_earliest_time() and get_latest_time() are O(1) too: we just
use list.front() and list.back(). So we have all operations with O(1).
So that's why I want to have a list::iterator vector. I assume iterator is a
smart pointer that can simulate all behaviours of native pointers.
iterators
【在 b******n 的大作中提到】
: end is not null, it points to *after* last item. you have to take care of
: iterators when you modify stl container. Why do you need a list of iterators
: .
:
: and potentially dangerous?
: defined doubly linked list and the initial value NULL for X elements. I
: expect a stl based solution can achieve similar behaviour.
| p*u
发帖数: 2454 | 7
int
'a'.
list
the
what's the point of keeping a sorted linked list if u only need earliest
and latest time stamps? why can't u simply keep 2 integers?
besides, it looks like u r trying to implement a multimap. no need to do
it by urself, if u worry about the performance u can use hash_multimap
【在 g*********s 的大作中提到】
: It's a long story.
: I'm designing a LRU cache. For each char ch being accessed, there's an int
: typed time stamp. For example, ('a', 3) means @ time 3 we access char 'a'.
: The cache must support fast operations of the following:
: query(char ch)
: insert(char key, int time_stamp)
: get_earliest_time(int time&)
: get_latest_time(int time&).
: I use a vector X and a sorted doubly linked list Y. The sorted linked list
: would keep the latest time stamp of each char, and the vector would keep the
| b******n
发帖数: 592 | 8 My suggestion is not to do this, but I think you can use use
your own null:
vector null;
vector::iterator nullIt = null.begin();
since nullIt is pointing to this special vector, it can be used as your
special
value for null for other vectors.
I would use hash to keep my data and use list to keep iterators if I have to
. To me, hash memory layout is more stable (not if it grows).
the
【在 g*********s 的大作中提到】
: It's a long story.
: I'm designing a LRU cache. For each char ch being accessed, there's an int
: typed time stamp. For example, ('a', 3) means @ time 3 we access char 'a'.
: The cache must support fast operations of the following:
: query(char ch)
: insert(char key, int time_stamp)
: get_earliest_time(int time&)
: get_latest_time(int time&).
: I use a vector X and a sorted doubly linked list Y. The sorted linked list
: would keep the latest time stamp of each char, and the vector would keep the
| b******n
发帖数: 592 | 9 I think he may needs to discard element has earliest timestamp, in that case,
the head of the list needs to point to another one. It has to be sorted in
some
way.
【在 p*u 的大作中提到】
:
: int
: 'a'.
: list
: the
: what's the point of keeping a sorted linked list if u only need earliest
: and latest time stamps? why can't u simply keep 2 integers?
: besides, it looks like u r trying to implement a multimap. no need to do
: it by urself, if u worry about the performance u can use hash_multimap
| p*u
发帖数: 2454 | 10
case,
in
well, then it's a std::priority_queue.
【在 b******n 的大作中提到】
: I think he may needs to discard element has earliest timestamp, in that case,
: the head of the list needs to point to another one. It has to be sorted in
: some
: way.
| b******n
发帖数: 592 | 11 the internal structure of priority_queue is tree. Say if you want to insert
("a", 3), you will need to search for item with "a", and if it exists,
delete it, then insert ("a", 3).
With timestamp, the order of insertions has guaranteed the order of items.
list
is actually the most efficient way. No sort needed.
【在 p*u 的大作中提到】
:
: case,
: in
: well, then it's a std::priority_queue.
|
|
